[탐색/BFS] 백준 14940 쉬운 최단거리 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

14940번: 쉬운 최단거리

 

 

 

2. 문제 풀이

 모든 지점에서 목표지점까지의 거리를 구하는 문제입니다.

 

2022.02.23 - [Algorithm] - [Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자

[Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자

 반대로 해석하면, 목표지점에서의 모든 지점까지의 거리를 구하는 문제가 됩니다. 즉, 목표지점에서 BFS탐색을 시작해서, 거리를 계산하면 됩니다.

 

 

 

3. 코드

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

# 입력
N, M = map(int, input().split())
board = []
queue = deque([])
visit = [[False]*M for _ in range(N)]

for i in range(N):
    row = list(map(int, input().split()))

    # 목표지점 찾기
    for j in range(M):
        if row[j] == 2:
            queue.append((i, j))
            visit[i][j] = True
            row[j] = 0
    board.append(row)

# BFS 탐색
direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]  # 상하좌우
while queue:
    x, y = queue.popleft()

    for dx, dy in direction:
        nx, ny = x+dx, y+dy

        if 0 <= nx < N and 0 <= ny < M and not visit[nx][ny] and board[nx][ny] == 1:
            queue.append((nx, ny))
            visit[nx][ny] = True
            board[nx][ny] = board[x][y] + 1

# 출력
for row in board:
    for i in row:
        print(i, end=" ")
    print()

 맨 처음에는 위와 같이 짰으나, 벽으로 둘러싸인 곳을 -1로 출력하지 못했습니다. 따라서 아래와 같이 수정해서 코드를 작성했습니다.

 

 

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

# 입력
N, M = map(int, input().split())
board = []
queue = deque([])
visit = [[False]*M for _ in range(N)]
res = [[-1]*M for _ in range(N)]

for i in range(N):
    row = list(map(int, input().split()))

    for j in range(M):
        # 목표지점 찾기
        if row[j] == 2:
            queue.append((i, j))
            visit[i][j] = True
            res[i][j] = 0

        # 벽 기록
        if row[j] == 0:
            res[i][j] = 0
    board.append(row)

 총 3개의 리스트를 만듭니다. 입력 값을 저장할 board와, 탐색여부를 저장할 visit, 최종 결과값을 저장할 res를 생성합니다. 이후, board에 입력값을 받고, res에 벽의 위치와 목표지점을 표시합니다.

 

 

# BFS 탐색
direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]  # 상하좌우
while queue:
    x, y = queue.popleft()

    for dx, dy in direction:
        nx, ny = x+dx, y+dy

        if 0 <= nx < N and 0 <= ny < M and not visit[nx][ny] and board[nx][ny] == 1:
            queue.append((nx, ny))
            visit[nx][ny] = True
            res[nx][ny] = res[x][y] + 1

# 출력
for row in res:
    for i in row:
        print(i, end=" ")
    print()

 목표지점부터 BFS탐색을 실시합니다. res에는 이전 값에 +1을 해서 거리를 저장합니다.

 

 

<전체 코드>

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

# 입력
N, M = map(int, input().split())
board = []
queue = deque([])
visit = [[False]*M for _ in range(N)]
res = [[-1]*M for _ in range(N)]

for i in range(N):
    row = list(map(int, input().split()))

    for j in range(M):
        # 목표지점 찾기
        if row[j] == 2:
            queue.append((i, j))
            visit[i][j] = True
            res[i][j] = 0

        # 벽 기록
        if row[j] == 0:
            res[i][j] = 0
    board.append(row)

# BFS 탐색
direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]  # 상하좌우
while queue:
    x, y = queue.popleft()

    for dx, dy in direction:
        nx, ny = x+dx, y+dy

        if 0 <= nx < N and 0 <= ny < M and not visit[nx][ny] and board[nx][ny] == 1:
            queue.append((nx, ny))
            visit[nx][ny] = True
            res[nx][ny] = res[x][y] + 1

# 출력
for row in res:
    for i in row:
        print(i, end=" ")
    print()