문제 URL : https://www.acmicpc.net/problem/1938
1938번: 통나무 옮기기
첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4<=N<=50) 주어진다. 이어서 그 지형의 정보가 0, 1, B, E로 이루어진 문자열로 주어진다. 한 줄에 입력되는 문자열의 길이는 N이며 입력 문자 사
www.acmicpc.net
문제 접근법 :
통나무가 생길수있는 모양은 단 두가지 밖에없습니다.
가로 모양과 세로모양 아래 그림들처럼
그렇다면 이두가지모양으로 EEE가 있는곳까지 가야합니다.
그렇다면 어떻게 움직일까요?
회전을 중심점에서 해야한다는 말을 듣고 저는 중심점을 선택해서 가로모양이나 세로모양일때 그위치를 금방구할수있있습니다.
가로모양일경우 중심점 좌표가 (y,x)일경우 왼쪽은 (y,x-1), 오른쪽은 (y,x+1)이 될겁니다.
세로모양일경우 중심점 좌표가 (y,x)일경우 위쪽은 (y-1,x) 아래쪽은 (y+1,x)가 됩니다.
그렇다면 3개를 다같이 움직일필요없이 움질일때만 3개가 아무런 문제없이 움직이는지만 확인하고 정작 움직이는건 중심점 이면 되겠지요?
그리고 회전입니다.
이그림을 잘보시면 ?표가 하나라도 1이라면 회전자체가 불가능할겁니다. 그렇다면 전부 0이라면 회전이 가능하다는것은
아는데 다르게 생각해보면 위쪽으로 이동과 아래쪽 이동도 가능하다는것을 알수있습니다.
즉 현재 가로모양일때 위쪽이동과 아래쪽이동 둘다 가능하다면 회전이 가능하다는 뜻이됩니다.
이그림도 마찬가지로 세로모양일때 왼쪽과 오른쪽 이동 둘다 가능하다면 회전이 가능하여 가로모양이 될수있고
?가 1이 최소 1개만 있을때 왼쪽과 오른쪽 둘중하나 움직임은 가능하지만 회전은 불가능합니다 즉
왼쪽오른쪽 둘다 이동 가능할때만 회전이 가능하다는것을 알수있습니다.
소스코드 :
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
|
//By 콩순이냉장고
#include <bits/stdc++.h>
using namespace std;
#define v vector
#define vi v<int>
#define vvi v<vi>
#define vvvi v<vvi>
int n;
vvi board;
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,-1,0,1 };
struct point {
int y, x;
bool operator <(point& a) { return this->y < a.y ? true : this->x < a.x; }
friend bool operator ==(const point& a,const point& b) {
return a.y == b.y && a.x == b.x;
}
};
v<point> sv, fv;
void input() {
cin >> n;
board = vvi(n, vi(n));
char c;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> c;
if (c == '1') {
board[i][j] = 1;
}
else if(c=='B') {
sv.push_back({ i,j });
}
else if (c == 'E') {
fv.push_back({ i,j });
}
}
}
}
bool isgo(int y, int x) {
if (!(0 <= y && y < n && 0 <= x && x < n)) return false;
return board[y][x] == 0;
}
int whatshape(vector<point> &vp) {
for (int i = 0; i < 4; i++) {
if (vp[1].y - vp[0].y == dy[i] && vp[1].x - vp[0].x == dx[i])
return i % 2;
}
return -1;
}
void maketree(v<point>& vp,int shape) {
for (int i = 0; i < 3; i += 2) {
vp[i].y = vp[1].y + dy[(shape + i) % 4];
vp[i].x = vp[1].x + dx[(shape + i) % 4];
}
}
v<point> nexttree(v<point>& vp, int idx) {
v<point> np(3);
for (int i = 0; i < 3; i++) {
np[i].y = vp[i].y + dy[idx];
np[i].x = vp[i].x + dx[idx];
}
return np;
}
int bfs() {
vvvi check(2, vvi(n, vi(n)));
queue<tuple<int, int, int>> q;
int shape, y, x;
tie(shape, y, x) = make_tuple(whatshape(sv), sv[1].y, sv[1].x);
q.push({ shape,y,x });
check[shape][y][x] = 1;
int cnt = 0;
while (!q.empty()) {
int qsize = q.size();
while (qsize--) {
int shape, y, x;
tie(shape, y, x) = q.front();
q.pop();
v<point> vp(3);
vp[1] = { y,x };
maketree(vp, shape);
if (vp == fv)
return cnt;
for (int i = 0; i < 4; i++) {
v<point> np = nexttree(vp, i);
bool flag = true;
for (int j = 0; j < 3; j++)
flag &= isgo(np[j].y, np[j].x);
if (flag == false)continue;
if (check[shape][np[1].y][np[1].x])continue;
check[shape][np[1].y][np[1].x] = 1;
q.push({ shape,np[1].y,np[1].x });
}
//회전
int arr[] = { 1,3 };
int gocnt = 0;
int nshape = (shape + 1) % 2;
for (int r : arr) {
int ndir = (shape + r) % 4;
v<point> np = nexttree(vp, ndir);
bool flag = true;
for (int i = 0; i < 3; i++) {
flag &= isgo(np[i].y, np[i].x);
}
gocnt += flag;
}
if (gocnt == 2 && check[nshape][vp[1].y][vp[1].x] == 0) {
q.push({ nshape,vp[1].y,vp[1].x });
check[nshape][vp[1].y][vp[1].x] = 1;
}
}
cnt++;
}
return 0;
}
void solve() {
cout << bfs() << "\n";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//freopen("input.txt", "r", stdin);
input();
solve();
}
|
cs |
궁금한점 혹은 모르는점 논리적인 오류등 어떤질문이든 댓글은 언제나 환영입니다.
공감 눌러주실꺼죠?
'백준' 카테고리의 다른 글
| 백준 11066 파일 합치기 (0) | 2021.09.29 |
|---|---|
| 백준 6324 URLs (0) | 2021.09.01 |
| 백준 2842 집배원 한상덕 (0) | 2021.08.31 |
| 백준 2505 두 번 뒤집기 (0) | 2021.08.26 |
| 백준 17267 상남자 (0) | 2021.08.26 |
