[Python] 백준 14940 쉬운 최단거리

 

문제 분석

• 주어진 지도의 각 지점에 대해 모든 목표 지점까지의 거리를 구하라
• 0 : 갈 수 없는 땅
• 1 : 갈 수 있는 땅
• 2 : 목표 지점
• 원래 갈 수 없는 땅(0)은 0 출력
• 원래 갈 수 있지만 도달할 수 없는 위치는 -1 출력

 

코드 설계

1. 2에서의 거리를 찾아야하기 때문에 먼저 목표 지점인 2를 찾아야한다.
2. 2를 기준으로 상하좌우 탐색
3. 만약 이동할 수 있다면 해당 위치에 대한 거리로 바꾸고
4. 이동하지 못한다면 0 그대로
5. 도달할 수 없는 위치 == 0으로 둘러쌓인 곳
6. bfs 상하좌우 

• 원래 갈 수 있지만 도달할 수 없는 위치 → 더 이상 갈 수 잇는 곳이 없는데 아직 탐색을 다 하지 않은 경우
• 만약 현재 위치에서 더 이상 이동할 수 없거나 다 확인을 했으면 큐에 넣기
•  

 

정답 코드

1차 - 실패

import sys
from collections import deque
input = sys.stdin.readline

n, m = map(int, input().split())
g = [list(map(int, input().split())) for _ in range(n)]
d = deque()
ans = g
check = [[False] * m for _ in range(n)] # 거리를 또 계산하지 않기 위해

# 2찾기
for r in range(n):
    for c in range(m) :
        if g[r][c] == 2 :
            ans[r][c] = 0
            d.append((r,c,0))
            check[r][c] = True
            break

dh = [-1, 1, 0, 0]
dw = [0, 0, -1, 1]

for r in range(n) :
    for c in range(m) :
        if len(d) == 0 : # 여기에 걸린다는 것은 어딘가에 길이 막혀 더이상 갈 수 없다는 것
            break
        h, w, distance = d.popleft()
        cnt = 0
        for i in range(4) :
            cnt += 1
            nh = h + dh[i]
            nw = w + dw[i]

            if nh < 0 or nh >= n or nw < 0 or nw >= m :
                continue
            if g[nh][nw] == 0 : # 방문할 수 없는 거리
                continue
            if check[nh][nw] : # 방문했던 곳이면 continue
                continue


            # 이동한 자리에 거리에 대한 값으로 바꾸기
            distance += 1
            ans[nh][nw] = distance
            check[nh][nw] = True
            d.append((nh, nw, distance))

# 도달하지 못한부분은 -1
for i in range(n) :
    for j in range(m):
        if not check[i][j] and ans[i][j] != 0:
            ans[i][j] = -1

for i in range(len(ans)) :
    for j in range(len(ans[0])) :
        print(ans[i][j], end = ' ')
    print()

이 코드는 bfs가 아니라 dfs..
0에서 이동할 수 있는 칸이 있으면 이동해서 거기서 거리를 구하는 이슈가 발생

 

2차

• 거리 계산을 이전 위치에 대하여 +1의 거리
• 굳이 한번 싹 돌면서 -1로 바꿔주지 않고 갈 수 있는 길인데 아직 방문하지 않았다면 -1을 출력

import sys
from collections import deque
input = sys.stdin.readline

n, m = map(int, input().split())
g = [list(map(int, input().split())) for _ in range(n)]
q = deque()
visited = [[False] * m for _ in range(n)] # 거리를 또 계산하지 않기 위해
ans = [[0]*m for _ in range(n)]

dh = [-1, 1, 0, 0]
dw = [0, 0, -1, 1]

# 시작점 찾기
for r in range(n) :
    for c in range(m) :
        if g[r][c] == 2 :
            visited[r][c] = True
            q.append((r,c))

while q :
    h, w = q.popleft()

    for i in range(4) :
        nh = h + dh[i]
        nw = w + dw[i]

        if nh < 0 or nh >= n or nw < 0 or nw >= m:
            continue
        if g[nh][nw] != 1 :  # 방문할 수 없는 거리
            continue
        if visited[nh][nw]:  # 방문했던 곳이면 continue
            continue

        q.append((nh, nw))
        visited[nh][nw] = True
        ans[nh][nw] = ans[h][w] + 1 # 이전 거리 +1 ****

for i in range(n) :
    for j in range(m) :
        if not visited[i][j] and g[i][j] == 1 : # ****
            print(-1, end=" ")
        else :
            print(ans[i][j], end = ' ')
    print()