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

[Silver I] 쉬운 최단거리 - 14940

문제 링크

성능 요약

메모리: 39688 KB, 시간: 480 ms

분류

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

제출 일자

2024년 4월 5일 18:36:03

문제 설명

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

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

입력

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

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

출력

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

풀이

 n, m = map(int, input().split())
 ground = [[] for _ in range(n)] # 지도 리스트
 visit = [[-1] * m for _ in range(n)] # 이동 거리값 저장 리스트, 0은 갈 수 없는 곳으로 쓰기 위해 -1로 초기화

 for i in range(n):
    temp = list(map(int, input().split()))
    for j in range(m):
        if temp[j] == 2: # 입력받은 수중 목표지점이 있으면,
            start = (i, j) # 시작점으로 지정
            break
    ground[i].extend(temp) # 지도 생성

먼저 목표 지점을 찾기 위해서 입력을 받은 값중에 값이 2인 인덱스를 찾아내고 start변수에 저장해준다.

d = [(1,0), (0,1), (-1,0), (0,-1)] # 4방향 이동

def BFS(start):
    q = deque([start]) # 목표 지점 추가
    visit[start[0]][start[1]] = 0 # 목표 지점은 이동거리0 

    while q: # 이동할 곳이 있을 때까지,
        x, y = q.popleft() # 탐색할 지점 변수 할당

        # 1칸 이동
        for dx, dy in d:
            nx, ny = x+dx, y+dy

            # 범위를 벗어나지 않는 곳이고, 아직 방문하지 않은 곳(-1)이면,
            if 0<=nx<n and 0<=ny<m and visit[nx][ny] == -1:
                
                # 갈 수 없는 땅이면
                if ground[nx][ny] == 0:
                    visit[nx][ny] = 0 # 0으로 처리

                # 갈 수 있는 땅이면,
                elif ground[nx][ny] == 1:
                    visit[nx][ny] = visit[x][y] + 1 # 이전 값에 1을 더하여 이동 거리값 저장
                    q.append((nx, ny)) # 다음 탐색 위치 추가

입력을 다 받고 목표지점 인덱스를 찾아낸 후에 본격적으로 너비우선탐색을 수행한다. 일반적인 BFS알고리즘에 1칸씩 이동할 수 있는 반복문을 추가하고, 그 안에 갈 수 있는 땅과 갈 수 없는 땅을 조건문으로 판단하여 이동거리의 누적값을 저장하며 이동해나간다.

BFS(start) # 너비우선탐색 수행

for i in range(n):
    for j in range(m):

        # 현재 위치에서 갈 수 없는 곳이면,
        if ground[i][j] == 0:
            print(0, end=' ') # 0을 출력
        else: # 현재 위치에서 갈 수 있는 곳이면,
            print(visit[i][j], end=' ') # 그 위치에서의 최단거리값을 출력
    print()

BFS함수로 최단 거리값 저장이 모두 끝나면 이중 반복문으로 갈 수 있는 곳과 갈 수 없는 곳을 판단하여 결과를 출력한다.

전체 코드

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

d = [(1,0), (0,1), (-1,0), (0,-1)]

def BFS(start):
    q = deque([start])
    visit[start[0]][start[1]] = 0

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

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

            if 0<=nx<n and 0<=ny<m and visit[nx][ny] == -1:
                if ground[nx][ny] == 0:
                    visit[nx][ny] = 0
                elif ground[nx][ny] == 1:
                    visit[nx][ny] = visit[x][y] + 1
                    q.append((nx, ny))      

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

for i in range(n):
    temp = list(map(int, input().split()))
    for j in range(m):
        if temp[j] == 2:
            start = (i, j)
            break
    ground[i].extend(temp)

BFS(start)

for i in range(n):
    for j in range(m):
        if ground[i][j] == 0:
            print(0, end=' ')
        else:
            print(visit[i][j], end=' ')
    print()