백준 16946. 벽 부수고 이동하기 4

tose33 2022. 10. 7. 14:07

16946번: 벽 부수고 이동하기 4

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이

www.acmicpc.net

우선 가장 먼저 떠오르는 생각은 그냥 벽을 하나씩 다 부숴보고 bfs를 돌리는 것일 것이다.

하지만 당연히 최대 칸의 갯수가 1000x1000=1000000 이므로 위 방법으론 시간복잡도 빅오 노테이션 O(1000000^2)로 불가능하다.

따라서 시간을 줄일 방법을 생각해봐야 한다.

위 방법으로 했을때 중복되는 연산은 같은 빈 공간을 반복적으로 방문하게 된다는 것이다.

이를 줄이려면 어떻게 해야할까.

떠오른 방법은 모든 빈 공간에 대하여 bfs를 돌려서 모든 빈 공간들의 연결된 공간의 갯수를 미리 구해놓는 것이다.

그리고 각 벽들은 상하좌우에 있는 빈 공간들의 연결된 갯수를 더해주면 해당 벽을 허물었을때 이동할수 있는 공간이 구해진다.

여기서 주의할 점은 그냥 무작정 더해버리면 중복되는 경우가 있다.

예를들어 다음과 같은 맵에서 [2][1] 벽을 허물었을때를 보면

[2][1] 벽 기준 위의 빈공간은 왼쪽 빈 공간과 같은 공간이다. (이어진 공간이다)

따라서 빈 공간들의 연결된 공간의 갯수를 구할때 같은 공간들끼리는 같은 번호를 갖도록 해주고, 벽을 허물고 계산할때 이미 계산한 빈 공간이라면 더해주지 않아야 한다.

또 한가지 주의할점이 있는데 바로 정답을 출력할때 이동할 수 있는 칸의 개수를 10으로 나눈 나머지를 출력한다는 점이다.

모든 빈 공간에 대하여 bfs 연산으로 연결된 공간의 갯수를 구할때 이미 방문한 곳을 방문하지 않도록 해야 하는데, 만약에 그냥 해당 지점의 이어진 공간의 갯수가 0이면 아직 방문하지 않았다고 판단한다면 틀리게 된다.

왜냐면 10칸 % 10 = 0 이기 때문이다.