[백준] 14940 쉬운 최단거리 (python 파이썬)

14940번: 쉬운 최단거리

---

지도에서 모든 지점의 최단거리를 구하는 문제.

---

아이디어

BFS를 사용했다. 지도에서 최단거리 == BFS 거의 공식처럼 머리에서 나온다...

 

문제를 해결하기 위해 목표 지점(2로 표시)과 갈 수 없는 땅(0으로 표시)의 좌표는 따로 저장해 둔다.

---

전체 코드

from collections import deque

dx = [0, 1,  0, -1]
dy = [1, 0, -1, 0]
start_x, start_y = 0, 0 # 목표 지점(시작 지점)
maze = [] #지도를 담는 배열
wall_list = [] # 갈 수 없는 땅들의 좌표들
que = deque() 

n, m = map(int, input().split())
visited = [[-1] * m for _ in range(n)]

for i in range(n):
    line = [int(x) for x in input().split()]
    for j in range(m):
        if line[j] == 2:
            start_x, start_y = i, j
        elif line[j] == 0:
            wall_list.append([i, j])
    maze.append(line)

visited[start_x][start_y] = 0

for pos in wall_list:
    visited[pos[0]][pos[1]] = 0

que.append([start_x, start_y])

while que:
    x, y = que.popleft()
    for i in range(4):
        nx, ny = dx[i] + x, dy[i] + y
        if 0 <= nx < n and 0 <= ny < m:
            if maze[nx][ny] == 1 and visited[nx][ny] == -1:
                visited[nx][ny] = visited[x][y] + 1
                que.append([nx, ny])

for i in range(n):
    print(" ".join(map(str, visited[i])))

---

코드 설명

for i in range(n):
    line = [int(x) for x in input().split()]
    for j in range(m):
        if line[j] == 2:
            start_x, start_y = i, j
        elif line[j] == 0:
            wall_list.append([i, j])
    maze.append(line)

 

지도를 입력받음과 동시에 목표 지점과 갈 수 없는 땅들의 좌표를 저장해 준다.

 

visited[start_x][start_y] = 0

for pos in wall_list:
    visited[pos[0]][pos[1]] = 0

que.append([start_x, start_y])

while que:
    x, y = que.popleft()
    for i in range(4):
        nx, ny = dx[i] + x, dy[i] + y
        if 0 <= nx < n and 0 <= ny < m:
            if maze[nx][ny] == 1 and visited[nx][ny] == -1:
                visited[nx][ny] = visited[x][y] + 1
                que.append([nx, ny])

 

BFS를 활용해 모든 지점의 최단 거리를 구해준다.