처음 문제를 보았을 때, 그냥 BFS로 풀면 되겠다 싶었다.
|
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 _collections import deque
m, n = map(int, input().split())
data = []
for _ in range(n):
data.append(list(map(int, input())))
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
def bfs():
q = deque()
q.append((0, 0))
distance = [[int(1e9) for _ in range(m)] for _ in range(n)]
distance[0][0] = 0
visited = [[False for _ in range(m)] for _ in range(n)]
while q:
pop_x, pop_y = q.popleft()
for i in range(4):
nx, ny = pop_x + dx[i], pop_y + dy[i]
if 0 <= nx < n and 0 <= ny < m and distance[pop_x][pop_y] < distance[nx][ny] and visited[nx][ny] == False:
if data[nx][ny] == 1:
distance[nx][ny] = min(distance[pop_x][pop_y] + 1, distance[nx][ny])
else:
distance[nx][ny] = min(distance[pop_x][pop_y], distance[nx][ny])
visited[nx][ny] = True
q.append((nx, ny))
print(distance[n-1][m-1])
bfs()
|
cs |
이것이 처음 풀었을 때, 틀린 코드이다.
저 코드에서 visited를 빼면 답은 맞지만, 메모리 초과가 나서 오답처리가 된다.
그렇다고 visited을 추가하면 답이 틀린다.
이유는 다음과 같다.
더 짧은 거리가 나와도, 이미 방문 처리를 해버려서 최소 횟수를 구할 수 없다.
그렇다고 visited를 빼버린다면, 이미 처리된 곳도 너무 많이 q에 집어넣게 되어 메모리 초과가 나버린다.
그럼 어떻게 해야할까
|
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
34
35
|
from _collections import deque
m, n = map(int, input().split())
data = []
for _ in range(n):
data.append(list(map(int, input())))
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
def bfs():
q = deque()
q.append((0, 0))
distance = [[int(1e9) for _ in range(m)] for _ in range(n)]
distance[0][0] = 0
visited = [[False for _ in range(m)] for _ in range(n)]
while q:
pop_x, pop_y = q.popleft()
for i in range(4):
nx, ny = pop_x + dx[i], pop_y + dy[i]
if 0 <= nx < n and 0 <= ny < m and visited[nx][ny] == False:
if data[nx][ny] == 1:
distance[nx][ny] = distance[pop_x][pop_y] + 1
q.append((nx, ny))
else:
distance[nx][ny] = distance[pop_x][pop_y]
q.appendleft((nx, ny))
visited[nx][ny] = True
print(distance[n - 1][m - 1])
bfs()
|
cs |
visited로 방문처리는 하되, q에 넣는 방법을 달리 해야 한다.
바로 현재 distance가 0이라면, 큐에 삽입할 떄 가장 우선순위로 넣는 것이다.
이렇게 되면 distance가 큰 것이 먼저 방문할 경우를 제외하게 되어 해결할 수 있다.