알고리즘 문제풀이/백준
[백준 16946번] 벽 부수고 이동하기 4
슥지니
2022. 3. 11. 23:37
반응형
문제 링크: https://www.acmicpc.net/problem/16946
16946번: 벽 부수고 이동하기 4
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이
www.acmicpc.net
<문제 풀이>
각각의 벽에 대해서 BFS를 호출하면 벽 찾는데 O(N * M), BFS 호출하는데 O(N + M) 이므로 총 O( (N+M) * N*M )이 걸리게 된다.
벽을 부수었을 때 이동할 수 있는 곳은 벽을 기준으로 상하좌우의 0으로 이루어진 영역들이므로 0에 대해서 BFS를 1회 호출해서 영역을 구하고, 각 벽에 대해서 상하좌우 영역의 크기만 계산하면 O(N * M)에 해결할 수 있다.
<C++ 소스 코드>
|
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
|
#include<iostream>
#include<queue>
#include<utility>
using namespace std;
#define X first
#define Y second
int N, M;
int board[1000][1000];
int visited[1000][1000];
int res[1000][1000];
int connected[1000001];
bool useC[1000001];
const int dx[4] = { 0, 0, 1, -1 };
const int dy[4] = { 1, -1, 0, 0 };
void bfs() {
int flag = 1;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (board[i][j] || visited[i][j]) continue;
queue<pair<int, int> > Q;
Q.push({ i, j });
visited[i][j] = flag;
int cnt = 1;
while (!Q.empty()) {
auto cur = Q.front(); Q.pop();
for (int dir = 0; dir < 4; dir++) {
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if (nx < 0 || ny < 0 || nx >= N || ny >= M)continue;
if (board[nx][ny] || visited[nx][ny])continue;
Q.push({ nx, ny });
visited[nx][ny] = flag;
cnt++;
}
}
connected[flag] = cnt;
flag++;
}
}
}
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> N >> M;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
char c; cin >> c;
board[i][j] = c - '0';
}
}
bfs();
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (board[i][j] == 1) {
res[i][j] = 1;
for (int dir = 0; dir < 4; dir++) {
int nx = i + dx[dir];
int ny = j + dy[dir];
if (nx < 0 || ny < 0 || nx >= N || ny >= M)continue;
if (board[nx][ny] || useC[visited[nx][ny]]) continue;
useC[visited[nx][ny]] = true;
res[i][j] = (res[i][j] + connected[visited[nx][ny]]) % 10;
}
for (int dir = 0; dir < 4; dir++) {
int nx = i + dx[dir];
int ny = j + dy[dir];
if (nx < 0 || ny < 0 || nx >= N || ny >= M)continue;
useC[visited[nx][ny]] = false;
}
}
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cout << res[i][j];
}
cout << '\n';
}
return 0;
}
|
cs |
반응형