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

문제 정보

제목 : 쉬운 최단거리

번호 : 14940번

사용 언어 : Python

문제 링크

https://www.acmicpc.net/problem/14940

14940번: 쉬운 최단거리

 

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

 

문제

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

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

 

입력

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

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

 

출력

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

 

입출력 예제

---

나의 풀이

  지도의 크기 n과 m을 입력받습니다. 거리를 저장하는 지도는 n과 m을 이용해 2차원 배열로 선언하고 0으로 초기화합니다. 입력 받은 값을 지도에 저장하는데 이때 한 줄의 문자열을 split()하고 리스트화 한 후 그 리스트에 2가 있는지 확인합니다. 2가 있다면 deque에 2의 위치값을 리스트 형태로 저장합니다. 

  queue가 있는동안 반복하는 while을 이용해 너비 우선 탐색으로 목표지점으로부터 거리를 구합니다. queue의 요소를 하나 popleft()해서 현재 N과 M의 위치값을 저장하는 변수에 저장합니다. 4번 반복하는 for루프를 이용해 다음 위치의 값을 구합니다. 다음 위치에 갈 수 있고 방문 안한 곳이라면 queue에 다음 위치값을 저장하고 거리를 저장하는 지도에 거리를 저장합니다.

  반복이 끝나면 각 지점에서 목표 지점까지의 거리를 출력합니다. n의 길이만큼 반복하는 for루프를 이용합니다. 이때 갈 수 있는 땅인 부분 중 도달할 수 없는 위치를 찾는다면 그 거리를 -1로 저장합니다. 리스트를 문자열로 변환 후 공백으로 나누어 출력합니다.

 

코드

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

n,m = map(int,input().split()) # 세로의 크기 n, 가로의 크기 m
pointMap = [] # 입력 받는 지도
answerMap = [[0 for _ in range(m)] for _ in range(n) ] # 거리를 저장하는 지도
queue = deque()

#이동 가능한 방향
dm = [1,0,-1,0]
dn = [0,1,0,-1]

# 입력 받은 값 지도에 저장함
for i in range(n) :
    tmp = list(map(int,input().split()))
    if( 2 in tmp ) :
        queue.append([i,tmp.index(2)])
    pointMap.append(tmp)

# 너비 우선 탐색으로 목표지점으로부터 거리를 구함
while(queue) :
    currentN, currentM = queue.popleft()
    for i in range(4): 
        nextN = currentN+dn[i] if (0 <= currentN+dn[i] and currentN+dn[i] < n ) else currentN
        nextM = currentM+dm[i] if (0 <= currentM+dm[i] and currentM+dm[i] < m ) else currentM
        if(pointMap[nextN][nextM]==1 and answerMap[nextN][nextM] == 0) : # 다음위치에 갈 수 있고 방문 안한 곳일때 실행됨
            queue.append([nextN, nextM])
            answerMap[nextN][nextM] = answerMap[currentN][currentM] +1

# 각 지점에서 목표 지점까지의 거리를 출력함
for i in range(n) :
    if ( 0 in answerMap[i] and 1 in pointMap[i]) : # 갈 수 있는 땅인 부분 중 도달할 수 없는 위치를 찾음
        for j in range(m):
            answerMap[i][j] = -1  if(answerMap[i][j] == 0 and pointMap[i][j] == 1) else answerMap[i][j]
    print(' '.join(map(str,answerMap[i])))