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

 

문제

 

 

14940번: 쉬운 최단거리

 

 

 

 

정답 소스코드 (Python)

 

from collections import deque
n,m=map(int,input().split())
field=[]
visited=[[False for j in range(m)]for i in range(n)]
arr=[[-1 for j in range(m)]for i in range(n)]
for i in range(n):
    tmp=list(map(int,input().split()))
    field.append(tmp)
    if 2 in tmp:
        start_point_x=tmp.index(2)
        start_point_y=i

dx=[0,0,1,-1]
dy=[1,-1,0,0]

def bfs(start_point_x,start_point_y):
    queue=deque()
    queue.append([start_point_x,start_point_y,1])
    visited[start_point_y][start_point_x]=True
    arr[start_point_y][start_point_x]=0

    while queue:

        v=queue.popleft()
        distance=v[2]
        for i in range(4):
            nx,ny=v[0]+dx[i],v[1]+dy[i]
            if -1<nx<m and -1<ny<n and visited[ny][nx]==False:
                if field[ny][nx]!=0:
                    visited[ny][nx]=True
                    arr[ny][nx]=distance
                    queue.append([nx,ny,distance+1])

bfs(start_point_x,start_point_y)

for i in range(n):
    for j in range(m):
        if not field[i][j]:arr[i][j]=0
        print(arr[i][j],end=" ")
    print()

 

 

풀이  (Python)

 

 

최단거리 문제이기 때문에 bfs를 활용하여 문제풀이를 진행하였다.

해당문제는  0인 칸은 벽이라고 생각하고 1은 길이라고 생각하면 문제 이해가 쉽다. 단 벽으로 인해 갈 수가 없는 곳은 -1로 처리를 해주어야 한다. 목적지부터의 거리를 구하는 문제이기 때문에 목적지인 2의 값을 가지는 칸에서 출발하는 bfs라고 생각하면 쉽다.

field=[]
visited=[[False for j in range(m)]for i in range(n)]
arr=[[-1 for j in range(m)]for i in range(n)]

 

입력을 받는 리스트인 field와 방문확인용으로 visited, 결과를 출력하는 것으로  arr리스트 총 3개의 리스트를 사용하여 풀이하였다. 왜 arr는 -1로 초기화하였을까? point2에서 설명하도록 하겠다.

 

 

 

Point 1)  BFS( 너비 우선탐색) 활용

 

-초기값 설정

 

for i in range(n):
    tmp=list(map(int,input().split()))
    field.append(tmp)
    if 2 in tmp:
        start_point_x=tmp.index(2)
        start_point_y=i

 

목적지인 filed중 2인 값부터 시작하기 때문에 BFS함수 진입 전 start_point_x와 start_point_y의 값을 설정 후 함수의 매개변수로 전달한다.

 

 

    queue=deque()
    queue.append([start_point_x,start_point_y,1])
    visited[start_point_y][start_point_x]=True
    arr[start_point_y][start_point_x]=0

 

BFS함수 안에서는 처음으로 시작하는 값을 queue에 넣어주고, 방문처리를 해준다.

또한 목적지 부터 BFS를 실행하기 때문에 초기 값을 0으로 설정하여 arr에 넣어준다.

 

 

 

-BFS(너비 우선 탐색) 동작 로직

 

def bfs(start_point_x,start_point_y):
    queue=deque()
    queue.append([start_point_x,start_point_y,1])
    visited[start_point_y][start_point_x]=True
    arr[start_point_y][start_point_x]=0

    while queue:

        v=queue.popleft()
        distance=v[2]
        for i in range(4):
            nx,ny=v[0]+dx[i],v[1]+dy[i]
            if -1<nx<m and -1<ny<n and visited[ny][nx]==False:
                if field[ny][nx]!=0:
                    visited[ny][nx]=True
                    arr[ny][nx]=distance
                    queue.append([nx,ny,distance+1])

 

nx와 ny가 배열 범위내에 있고, 방문하지 않은 함수라면 -> 다음 이동 칸이 0이 아닌 경우

->visited배열 방문처리, arr에 결과 저장, 다음 칸을 queue에 push

 

매 while문 반복마다 queue에 있는 칸을 pop 하여 해당 pop 한 칸으로 위의 로직 다시 진행한다.

 

 

 

 

 

Point 2)  못가는 곳은 -1

문제 조건상 bfs로 방문 처리가 되지않는 곳은 -1이여야 한다 예를 들어 예제 1번 오른쪽 끝 부분이 아래와 같이 수정되어 있다면,

 0 0 0 0 0
 0 1 1 1 1
 0 1 0 0 0
 0 1 1 1 1

 

아래와 같이 출력해야 한다.

 0  0  0  0  0
 0 -1 -1 -1 -1
 0 -1  0  0  0
 0 -1 -1 -1 -1

 

이를 해결하기 위해 0인 곳은 따로 0으로 처리하고 ( 벽이라고 생각), BFS함수가 끝난 후에도 방문 처리가 되지 않는 곳은 -1로 처리를 하면 된다. 그렇다면 BFS가 끝난 후 visited함수와 결과인 arr를 비교하여 -1을 처리를 해야 하나?

 

아니다. 기본 배열을 0으로 초기화하는 것이 아닌, arr를 -1로 초기화하여 생성하면 못 가는 곳의 -1 처리가 간단하게 이루어진다.

 

arr=[[-1 for j in range(m)]for i in range(n)]

 

 

 

 

 

Point 3)  입력배열의 0 예외처리

 

for i in range(n):
    for j in range(m):
        if not field[i][j]:arr[i][j]=0
        print(arr[i][j],end=" ")
    print()

 

0인 경우 BFS로 탐색할 수 없게 구성했지만, 결과를 저장하는 필드인 arr에는  0 체크가 되어 있지 않기 때문에

출력 시에 field의 값이 0인 경우 arr에도 0 처리를 해준다.