[백준 BOJ] 16946. 벽 부수고 이동하기 4
05 Sep 2021난이도
Gold II
문제 풀이
딱 보고 생각나는 풀이는, 벽을 없애고 Flood Fill로 몇개인지 세어서 답을 구하는 풀이이다. 근데, 그렇게 짜면 TLE를 받는다.
5 5
00000
01010
00000
01010
00000
이런식의 데이터가 주어졌다고 해보자. 벽인 부분에서 Flood Fill을 해서 개수를 구하면, 거의 모든 공간에 대해 Flood Fill을 수행하게 됨을 파악할 수 있다. 최악의 경우를 생각해보면, 모든 지점에서 검사하는데에 \(\scriptsize O(NM)\)이고, Flood Fill이 거의 모든 지점에 되어야 하기에 거기서 \(\scriptsize O(NM)\)이다. 따라서, \(\scriptsize O(NM) * O(NM) = O(N^{2}M^{2})\)이다. 최대 \(\scriptsize 10^{12}\)만큼의 연산이 수행될 수 있으니, 직관적인 풀이로는 불가능함을 알 수 있다.
그럼 어떻게 풀면될까? Flood Fill을 수행하는 \(\scriptsize O(NM)\)만큼이 문제이니, 이걸 최대한 줄여보자.
5 5
11111
01110
00100
01110
11111
같은 데이터를 생각해보자. 만약 (2, 2)지점에 있는 벽(정중앙)을 지우고 갈 수 있는 칸의 개수를 센다고 생각해보자. 벽을 지웠으니 먼저 1개이고, 좌측으로는 4개, 우측으로도 4개의 칸이 있음을 알 수 있다. 상하로는 벽이 있어 갈 수 있는 칸이 없기에, 답은 1 + 0 + 0 + 4 + 4(현재 지점 + 상 + 하 + 좌 + 우)임을 알 수 있다. 즉, 벽이 있는 칸에서 상하좌우에 몇개의 칸들이 각각 집합을 이루고 있는지만 알면 되지 않은가? 이걸 그대로 구현해주면 된다. 그런데, 이렇게만 구현하면 상하좌우가 같은 집합에 속하는 경우에 중복으로 카운트하게 된다. 그렇기에 이미 센 집합이면 걸러주어야 함을 유의하며 코드를 작성하면 된다.
집합들을 구해주는 것은 Flood Fill로 해결해주면 된다. 나는 Flood Fill을 BFS로 구현했고, 각 영역에 대해 번호를 붙여 구별되도록 했다. 또한, 그 영역번호를 통해 해당 영역에 얼마만큼의 칸들이 집합을 이루는지도 알 수 있도록 집합 개수를 저장했다.
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int id = 1; //다른 영역을 구분하기 위한 영역번호
vector<int> setCount; //특정 영역에 몇개의 칸들이 집합을 이루는지 저장
vector<vector<bool>> visit; //BFS 방문 여부
vector<vector<int>> sameSet; //어떤 지점이 어느 영역에 속하는지 알기 위한 2차원 벡터
void floodFill(vector<vector<int>>& map, int y, int x) {
int cnt = 1;
queue<pair<int, int>> q;
visit[y][x] = true;
sameSet[y][x] = id; //(x, y)에 해당하는 영역 번호 표시
q.push({x, y});
while(!q.empty()) {
int curX = q.front().first;
int curY = q.front().second;
q.pop();
for(int i = 0; i < 4; ++i) {
int nextX = curX + dx[i];
int nextY = curY + dy[i];
if(nextX < 0 || nextX >= M || nextY < 0 || nextY >= N) continue;
if(visit[nextY][nextX] || map[nextY][nextX] == 1) continue;
cnt++;
sameSet[nextY][nextX] = id; //(nextX, nextY)에 해당하는 영역 번호 표시
visit[nextY][nextX] = true;
q.push({nextX, nextY});
}
}
id++;
setCount.push_back(cnt); //BFS가 끝나면, 해당 집합을 이루는 칸들의 수를 저장함.
}
즉, 위의 코드를 가지고 아래의 데이터에 적용해 나타내본다면 다음과 같다.
3 3 sameSet idx : 0 1 2 3 4 101 -> 010 -> setCount = {-1, 1, 1, 1, 1} 010 203 //0번째 인덱스는 사용하지 않기에 -1로 표시 101 040
모든 빈 칸에서 Flood Fill을 수행하고, 그 이후 모든 벽인 칸들에 대해서 개수를 세면 된다. 자세한 코드는 아래와 같다.
for(int i = 0; i < N; ++i) {
for(int j = 0; j < M; ++j) {
if(map[i][j] == 0 && !visit[i][j]) floodFill(map, i, j); //방문하지 않은 모든 빈칸에서 Flood-Fill수행
}
}
for(int y = 0; y < N; ++y) {
for(int x = 0; x < M; ++x) {
if(map[y][x] == 1) { //모든 벽인 칸들에 대해 개수를 구하기
int cnt = 1; //벽을 빈칸으로 바꾸기에 1부터 시작
vector<int> counted; //중복 카운팅 방지
for(int i = 0; i < 4; ++i) { //상하좌우 체크
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 0 || nx >= M || ny < 0 || ny >= N) continue; //범위 밖이면 건너뛰기
if(map[ny][nx] == 1) continue; //벽이면 건너뛰기
if(find(counted.begin(), counted.end(), sameSet[ny][nx]) != counted.end()) continue; //만약 이미 센 영역번호라면 건너뛰기
cnt += setCount[sameSet[ny][nx]]; //해당 영역번호에 있는 칸들의 개수 더하기
counted.push_back(sameSet[ny][nx]); //중복 카운팅 방지를 위해 이미 센 영역번호 저장
}
cnt %= 10;
cout << cnt; //카운트 출력
}
else cout << 0; //벽이 아니면 0 출력
}
cout << '\n';
}
엄청 어려운 아이디어가 필요한 문제는 아니였으나, 생각나는대로만 풀었다간 TLE받고 의아할 수 있는 문제이다. 나도 그냥 딱 보고는 쉬운 문제같네 싶어서 바로 풀었더니, TLE받고 “왜지??” 하고 한참 생각하고 있었다..