https://www.acmicpc.net/problem/1938
1938번: 통나무 옮기기
첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4<=N<=50) 주어진다. 이어서 그 지형의 정보가 0, 1, B, E로 이루어진 문자열로 주어진다. 한 줄에 입력되는 문자열의 길이는 N이며 입력 문자 사이에는 빈칸이 없다. 통나무와 최종 위치의 개수는 1개이다.
www.acmicpc.net
<풀이>
1. 초기 통나무 상태를 구하고, bfs를 시작한다.
2. 조건에 맞춰서 통나무를 움직이고, 도착지점에 도달하면 함수를 종료한다.
3. 움직인 횟수를 출력한다.
<해법>
1. BFS
=> 문제에서 BFS를 이용해야겠다는 것은 알 수 있습니다. 이제 중요한 것은 큐에 담을 자료형과 방문 처리 입니다.
결국, 어떻게 큐에 담아서( = 큐에 담을 자료형) 그 중 의미있는 정보만을 골라서( = 방문하지 않은 정보를 고름) 다시 큐에 담아 탐색을 진행하는 방법을 생각해야 합니다.
- 큐에 담을 자료형
bfs를 동작할 때 필요한 정보들을 담았습니다.
위 문제에서는 가장먼저 통나무 세 개의 좌표들이 필요합니다. 또한 회전을 해야하므로 눕혀있는 상태, 출력할 값인 움직인 횟수가 필요합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
//좌표
struct pos {
int x, y;
};
//움직일 통나무 3개
struct logs {
//각각 통나무 좌표
pos A, B, C;
//통나무가 눕혀있는 상태
int floating;
//움직인 횟수
int moveCnt;
};
|
- 방문 처리
완전 탐색인 bfs를 효율적으로 사용하기 위해서는 필요없는 탐색을 줄이는 것이 중요합니다.
필요없는 탐색이란 탐색할 범위를 넘어섰거나, 이전에 탐색했던 것을 탐색하는 것입니다.
그 중 두번째 비효율 탐색을 줄이는 방법으로, 방문 처리가 있습니다.
위 문제를 예로 들겠습니다.
만약 문제에서 방문처리를 3개 통나무의 좌표로 하게 된다면, 아래와 같은 비효율 탐색이 발생한다.
따라서, 방문처리는 가운데 통나무(B통나무)의 좌표와 눕혀있는 상태로 정해야한다.
|
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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
|
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
//좌표
struct pos {
int x, y;
};
//움직일 통나무 3개
struct logs {
//각각 통나무 좌표
pos A, B, C;
//통나무가 눕혀있는 상태
int floating;
//움직인 횟수
int moveCnt;
};
//앞 4개 : 상하좌우, 뒤 4개 : 대각방향
int di[] = { -1,0,1,0,-1,1,1,-1 };
int dj[] = { 0,1,0,-1,1,1,-1,-1 };
int N;
char map[52][52];
//visited[가운데 통나무 행][가운데 통나무 열][눕혀있는 상태]
bool visited[52][52][2];
queue<logs> q;
int res = 0;
bool inner(int ai, int aj, int bi, int bj, int ci, int cj) {
if (ai <= 0 || aj <= 0 || bi <= 0 || bj <= 0 || ci <= 0 || cj <= 0 || ai > N || aj > N || bi > N || bj > N || ci > N || cj > N) {
return false;
}
return true;
}
void bfs() {
while (!q.empty()) {
logs cur = q.front();
q.pop();
//3개 모두 옮겼을 시 - 종료
if (map[cur.A.x][cur.A.y] == 'E' && map[cur.B.x][cur.B.y] == 'E' && map[cur.C.x][cur.C.y] == 'E') {
res = cur.moveCnt;
return;
}
//상,하,좌,우로 움직일 수 있는지 판단 후 큐에 담기
for (int i = 0; i < 4; i++) {
logs nxt = cur;
nxt.A.x += di[i];
nxt.A.y += dj[i];
nxt.B.x += di[i];
nxt.B.y += dj[i];
nxt.C.x += di[i];
nxt.C.y += dj[i];
//옮긴 3개 통나무의 좌표가 범위 안에 있는지 판단
if (!inner(nxt.A.x, nxt.A.y, nxt.B.x, nxt.B.y, nxt.C.x, nxt.C.y)) {
continue;
}
//옮긴 3개 통나무 좌표에 다른 나무가 있거나, 이전에 같은 모양으로 방문한적이 있는지 판단
if (map[nxt.A.x][nxt.A.y] == '1' || map[nxt.B.x][nxt.B.y] == '1' || map[nxt.C.x][nxt.C.y] == '1' || visited[nxt.B.x][nxt.B.y][nxt.floating]) {
continue;
}
nxt.moveCnt++;
visited[nxt.B.x][nxt.B.y][nxt.floating] = true;
q.push(nxt);
}
//회전할 수 있는지 판단 후 큐에 담기
bool canRotate = true;
logs nxt = cur;
for (int i = 0; i < 8; i++) {
//중간 통나무에서 상,하,좌,우,대각선 4방향 탐색 - 모든 방향이 범위 안에 있거나, 다른 나무가 없다면 회전 가능
int bni = nxt.B.x + di[i];
int bnj = nxt.B.y + dj[i];
if (bni <= 0 || bnj <= 0 || bni > N || bnj > N || map[bni][bnj] == '1') {
canRotate = false;
break;
}
}
//회전할 수 있다면
if (canRotate) {
//통나무가 세로로 있는 경우, 가로로 돌리기
if (nxt.floating == 0) {
nxt.A.x = nxt.B.x;
nxt.A.y = nxt.B.y - 1;
nxt.C.x = nxt.B.x;
nxt.C.y = nxt.B.y + 1;
nxt.floating = 1;
}
//통나무가 가로로 있는 경우, 세로로 돌리기
else {
nxt.A.x = nxt.B.x - 1;
nxt.A.y = nxt.B.y;
nxt.C.x = nxt.B.x + 1;
nxt.C.y = nxt.B.y;
nxt.floating = 0;
}
if (!visited[nxt.B.x][nxt.B.y][nxt.floating]) {
nxt.moveCnt++;
visited[nxt.B.x][nxt.B.y][nxt.floating] = true;
q.push(nxt);
}
}
}
return;
}
int main() {
//시작 통나무
logs st;
vector<pos> startLogs;
int startLogsFloat = 0;
//입력
cin >> N;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
cin >> map[i][j];
if (map[i][j] == 'B') {
startLogs.push_back({ i,j });
}
}
}
//첫번째 두번쨰 통나무 열 비교 - 눕혀있는 상태값 찾기
if (startLogs[1].y - startLogs[0].y == 1) {
startLogsFloat = 1;
}
//시작 통나무 = {A통나무 좌표, B통나무 좌표, C통나무 좌표, 눕혀있는 상태, 옮긴 횟수}
st = { {startLogs[0].x, startLogs[0].y}, {startLogs[1].x, startLogs[1].y}, {startLogs[2].x, startLogs[2].y}, startLogsFloat, 0 };
visited[st.B.x][st.B.y][startLogsFloat] = true;
q.push(st);
bfs();
//출력
cout << res;
}
|
BFS와 시뮬레이션에 대해 알아볼 수 있는 문제였습니다.
'알고리즘 문제풀이 > 백준' 카테고리의 다른 글
| [C++] 백준 2511 - 카드놀이 (0) | 2020.04.30 |
|---|---|
| [C++] 백준 6087 - 레이저 통신 (0) | 2020.04.30 |
| [C++] 백준 2174 - 로봇 시뮬레이션 (0) | 2020.04.30 |
| [C++] 백준 3987 - 보이저 1호 (0) | 2020.04.30 |
| [C++] 백준 2437 - 저울 (2) | 2020.04.30 |
