내 풀이
|
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
|
from heapq import heappush, heappop
n = int(input())
data = []
for _ in range(n):
data.append(list(map(int, input())))
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
def dijkstra():
q = []
heappush(q, (0, 0, 0))
visited = [[False for _ in range(n)] for _ in range(n)]
while q:
cnt, x, y = heappop(q)
if x == n - 1 and y == n - 1:
print(cnt)
break
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if 0 <= nx < n and 0 <= ny < n and visited[nx][ny] == False:
if data[nx][ny] == 0:
heappush(q, (cnt + 1, nx, ny))
else:
heappush(q, (cnt, nx, ny))
visited[nx][ny] = True
dijkstra()
|
cs |
우선 순위 큐의 우선 순위를 벽을 깬 횟수로 두어 해결하였다.
최단 거리나 가중치 계산이 필요 없이, 그냥 벽을 깬 횟수만 구하면 되니까 이렇게 풀었다.
Why?
Q1. 왜? 어떻게 벽을 깨는 횟수를 우선 순위로 둘 생각을 했을까?
처음에는 dfs를 활용해서 벽을 한 개 세웠을 때의 경우의 수부터 순차적으로 모두 탐색하려고 했었다.(정말 이상한 생각이였다. 조금만 생각하더라도 시간 초과가 날 것이라는 걸 알아서 다행이다.)
시간 초과가 난다는 것은 좀 더 간단하게 or 효율적으로 해결할 수 있는 방법이 있다는 것이고, 다른 방법을 생각해보았다.
해결 방법을 떠올렸던 핵심은 문제에서 찾았다. 다른 조건 없이 그냥 벽을 뚫는 최소 횟수만 구하면 됐다. 어떻게 돌아서가든 상관 없이 벽을 없애는 획수만 세면 되니, q에 들어있는 좌표 중에 벽을 깬 횟수가 가장 적은 것을 기준으로 탐색하면 될 것이다.