[Python] 14940번 쉬운 최단거리

✏️ 문제

 

문제 파악

짧은 거리를 출력해야 하므로 BFS를 사용해서 풀었다.

 

visited 배열을 도달할 수 있는 거리를 저장하는 배열로 설정해서 출발지점이 거리가 0이므로 이걸 기준으로 나머지 거리를 구했다.

 

이때 입력으로 주어진 0은 갈 수 없는 땅이므로 초기에는 갈 수 없는 땅임을 구분하기 위해 visited 배열에서 -1로 주었다.

그리고 원래 갈 수 있지만 도달할 수 없는 땅은 BFS가 실행된 후에도 visited 배열의 값이 0(방문 X)이고 입력으로 주어진 값은 1인 땅이므로 이를 -1로 출력하도록 조건문을 처리했다.

 

다음과 같다.

if 갈 수 없는 땅이면:
	visited[갈 수 없는 땅] = -1

def bfs:
	...
    
    if 이동한 땅이 방문하지 않았다면:
    	visited[이동한 땅] = 이전까지 움직인 거리 + 1
        # 이 과정에서 출발지점의 값도 0이 아닌 다른 값으로 들어갈 수 있음
        
visited[출발지점] = 0 # bfs 돌고 난 후에 0 처리해줘야 함

if 해당 땅이 -1이라면:
	# 위에서 갈 수 없는 땅이라 -1 처리해준 땅
	0 출력
elif 해당 땅이 0이고 입력 받았을 때 해당 땅이 1이면:
	# 땅이 있으나 방문하지 않은 땅
	-1 출력
else:
	# 방문한 땅이라 저장한 거리 값 출력
	저장한 배열의 값 출력

 

알고리즘

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

 

 

코드

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

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

for i in range(n):
  line = list(map(int, input().split()))
  for j in range(m):
    graph[i][j] = line[j]

    if line[j] == 0:
      visited[i][j] = -1
    if line[j] == 2:
      goal_x, goal_y = i, j

def bfs(x, y):
  q = deque([(x, y)])

  while q:
    x, y = q.popleft()

    for i in range(4):
      dx = x + d[i][0]
      dy = y + d[i][1]

      if 0 <= dx < n and 0 <= dy < m and visited[dx][dy] == 0:
        q.append((dx, dy))
        visited[dx][dy] = visited[x][y] + 1

bfs(goal_x, goal_y)

visited[goal_x][goal_y] = 0
for i in range(n):
  for j in range(m):
    if visited[i][j] == -1:
      print(0, end=' ')
    elif visited[i][j] == 0 and graph[i][j] == 1:
      print(-1, end=' ')
    else:
      print(visited[i][j], end=' ')
  print()

 

 

---

 

⭐️ DFS와 BFS에 대해서 아직 잘 모른다면?

[알고리즘] DFS와 BFS