A. 문제설명
16946번: 벽 부수고 이동하기 4
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 �
www.acmicpc.net
문제에 대한 자세한 설명은 링크 참조
1. N*M크기의 배열이 존재
2. 해당 배열 안에는 1:벽, 또는 0:빈칸이 입력으로 주어짐
3. 각 벽이 있는 공간에서 인접한 공간으로 벽을 부수고 이동하려고 함
4. 여기서 벽은 맨 처음 하나만 부술 수 있고, 이동가능한 공간은 빈 공간만
5. 이렇게 해서 각각의 벽인 공간에 총 이동할 수 있는 거리를 구할 것
B. 접근법
Hash + DFS
맨 처음 이 문제를 받아들곤, 정말 간단하게 BFS로 풀 수 있을 거라고 생각하고 바로 구현했다. 그러나, 시간 제약에서 바로 걸려 실패하고 말았다.
실패.
내 처음 접근은 아래와 같은 표가 주어졌다고 했을 때, (0,0)에서 (N-1,M-1)까지 1인 인덱스에서 전부 BFS로 각각의 벽을 부수고 이동하는 거리를 구하는 것이었다.
| 1 | 1 | 0 |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
그러나 이러한 접근은 매 반복마다 중복된 계산(0인 지역의 탐사)을 하기 때문에 최적화를 해 줄 필요가 있었다. 즉, 0인 지점을 먼저 계산해놓고, 1에서는 주변에 계산된 값을 더해주기만 하는 것이다.
개선.
위 풀이를 개선하여 0인 지점들을 먼저 계산해놓고, 해쉬해 놓는 방식으로 재구현하였다. 이 풀이는 REBAS 블로그(rebas.kr/800)의 풀이내용을 참조하여 다시 푼 것이다.
아래와 같은 표가 주어졌을 때 0이 서로 인접한 지역들을 모두 값을 계산해줄 수 있다.
| 1 | 1 | 0 |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
이 값들을 계산하면 아래와 같이 표의 모양이 나오는데, 이는 처음에 딱 한번 만드는 비용만 발생한다.
| 0 | 0 | 1 |
| 3 | 3 | 0 |
| 3 | 0 | 1 |
그리고 이 지역들에 대한 Lookup 비용도 줄이기 위해 거리값을 해쉬해서 배열에 넣고 실제 표에는 배열의 인덱스만 넣어준다.
C. 풀이
1. 0이 서로 인접한 지역들을 모두 값을 계산
2. 지역들에 대한 Lookup 비용도 줄이기 위해 거리값을 해쉬해서 배열에 넣고 실제 표에는 배열의 인덱스만 넣음
3. 각 벽의 부수고 이동하는 Sum 비용 계산을 위해 4방향 주변의 해쉬 인덱스를 구함
4. 여기서, 같은 해쉬 인덱스를 가진 값의 중복계산 방지를 위해 Set 자료구조에 넣고 Set에 들어간 인덱스를 순회하여 전체합을 구함
D. 내 코드
