백준 16946 - 벽 부수고 이동하기 4 (Python)

https://acmicpc.net/problem/16946 

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

문제를 푸는 발상은 바로 할 수 있었으나 시간복잡도 줄이는 방법을 한참을 고민한 문제였다.

문제를 보자마자 떠올린 문제는 단지번호붙이기(https://acmicpc.net/problem/2667)였다.

쉽게 말해 그룹을 나누는 것인데, 이런 알고리즘을 flood-fill algorithm이라고 한다고 하는 것을 나중에 알았다.

​

문제를 푸는 방법은, 벽이 아닌 칸을 만나면 그 칸과 이어져 있는 벽이 아닌 칸들을 세어 하나의 group으로 모은다.

그 후 다시 한 번 그래프를 순환하며 벽을 만나면 그와 인접한 그룹을 찾아 그 그룹의 개수를 더한다.

그러나 이 때 신경써주어야 하는 것을 그룹이 ㄱ처럼 꺾여 있는 모양이면 한 번에 한 그룹의 개수를 두 번 더할 수 있다는 점이다. 이를 해결하기 위해 나는 처음에 단순히 해당 그룹을 돌며 내가 과연 이 그룹에 왔었는지를 visited에 기록하는 방법을 택했다. 그러나 당연히 시간 초과가 나고 말았다.

또다시, dictionary를 잘 써야 한다는 사실을 알게 되었다. 애초에 dictionary에 몇 번째 그룹인지를 넣어둔다면 바로 그 좌표를 통해 방문한 그룹이었는지를 알 수 있지 않은가. 그 부분만 바꿔 코드를 작성했더니 통과할 수 있었다.

bfs 함수는 그대로 썼으니 아래 부분만 올린다.