[백준] 14940번 - 쉬운 최단거리 | 파이썬

SangJin Ham·2023년 8월 19일

BFS 백준 시뮬레이션 알고리즘

백준

목록 보기

41/51

14940번 - 쉬운 최단거리

시간제한 : 1초
메모리 제한 : 128MB

문제

지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라.

문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자.

입력

지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000)

다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다. 입력에서 2는 단 한개이다.

출력

각 지점에서 목표지점까지의 거리를 출력한다. 원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다.

예제 입력 1

15 15
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 0 0 0
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1

예제 출력 1

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
11 12 13 14 15 16 17 18 19 20 0 0 0 0 25
12 13 14 15 16 17 18 19 20 21 0 29 28 27 26
13 14 15 16 17 18 19 20 21 22 0 30 0 0 0
14 15 16 17 18 19 20 21 22 23 0 31 32 33 34

코드

import sys
from collections import deque

# 상우하좌
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]

# N, M 입력
N, M = map(int, sys.stdin.readline().strip().split())

graph = []
Q = deque()
ch = [[0] * M for _ in range(N)]

# 지도 저장
for r in range(N):
  # 한 행 입력
  graph.append(list(map(int, sys.stdin.readline().strip().split())))
  # 해당 행에 목표지점 있나 확인
  for c in range(M):
    # 목표 지점이 있다면 
    # 목표지점 큐에 삽입 / 해당 지점 0으로 변경 / ch에 방문했다고 표시
    if graph[r][c] == 2:
      graph[r][c] = 0
      Q.append([r, c])
      ch[r][c] = 1

# 목표 지점에서부터 갈 수 있는 모든 지점을 방문
while Q:
  # 현재 큐에 삽입되어 있는 지점들만큼 반복
  length = len(Q)
  for _ in range(length):
    # 지점 하나 꺼내기
    r, c = Q.popleft()

    # 현재 지점에서 갈 수 있는 지점 찾기
    for i in range(4):
      nr = r + dr[i]
      nc = c + dc[i]

      # 지도의 범위에서 벗어나거나
      # 갈 수 있는 땅이거나
      # 방문하지 않은 땅인 경우에만
      if 0 <= nr < N and 0 <= nc < M and ch[nr][nc] == 0 and graph[nr][nc] == 1:
        
        # 해당 지점방문했다고 표시
        ch[nr][nc] = 1

        # 움직인 거리 : 현재 지점까지의 거리 + 1
        graph[nr][nc] = graph[r][c] + 1
        
        # 이제 방문했으므로 큐에 삽입
        Q.append([nr, nc])
        
# BFS를 돌고나서도 1인 땅이 있나 확인 후 변경
# 변경되었다면 해당 행 출력
for i in range(N):
  for j in range(M):
    # 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치가 있냐 ?
    if ch[i][j] == 0 and graph[i][j] == 1:
      # 그렇다면 -1로 변경
      graph[i][j] = -1
  # 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치있는지 확인하고 변경한 다음 출력
  print(*graph[i])

풀이

시간 : 740ms
메모리 : 39976KB

이 문제는 BFS와 시뮬레이션 알고리즘을 이용한 문제다.

BFS 알고리즘 부분을 돌리기 전에 변수 초기화 및 설정을 하자.

다른 지점으로 접근하기 위한 dr, dc 정의
N, M 입력
지도 graph 리스트를 생성해 각 행의 지점 정보를 입력
해당 지점에 방문했는지 확인할 수 있는 ch 리스트 생성

그 후 지도에 있는 목표 지점(2)을 Q에 삽입하고 ch에 방문했다고 표시(1)한다.

이제 BFS 알고리즘을 돌려보자
while문은 더이상 방문할 지점이 없을 때까지 반복한다.
for문은 현재 현재 큐에 삽입되어 있는 지점들만큼 반복한다.
for문이 시작되면 지점 하나를 꺼내 r와 c에 좌표를 저장한다.
그리고 상하좌우 방향 좌표 nr, nc를 정의해 인접한 지점에 접근한다.
이때, 지도의 범위에서 벗어나지 않고, 갈 수 있는 땅이고, 방문하지 않은 땅인 경우에만 큐에 삽입하고, 해당 좌표에 목표지점에서부터 해당 좌표까지 접근하는데의 거리를 저장한다.