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

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

14940번: 쉬운 최단거리

 

 

처음에는 

 

 

 

 

import sys




def func(x,y):
    if y+1 < m:
        if l[x][y+1] == 1:
            l[x][y+1] = l[x][y] +1
            func(x,y+1)
        elif l[x][y]+1 < l[x][y+1]:
            l[x][y+1] = l[x][y]+1
            func(x,y+1)

    if x+1 < n:
        if l[x+1][y] == 1:
            l[x+1][y] = l[x][y] +1
            func(x+1,y)
        elif l[x][y]+1 < l[x+1][y]:
            l[x+1][y] = l[x][y]+1
            func(x+1,y)

    if y-1 >= 0:
        if l[x][y-1] == 1:
            l[x][y-1] = l[x][y] +1
            return func(x,y-1)
        elif l[x][y]+1 < l[x][y-1]:
            l[x][y-1] = l[x][y]+1
            func(x,y-1)


    if x-1 >= 0:
        if l[x-1][y] == 1:
            l[x-1][y] = l[x][y] +1
            return func(x-1,y)
        elif l[x][y]+1 < l[x-1][y]:
            l[x-1][y] = l[x][y]+1
            func(x-1,y)

    
def print_l(l):
    for i in l :
        for j in i:
            print(j,end=" ")
        print()
        


n, m = map(int, sys.stdin.readline().split(" "))
l = []
x,y = 0, 0
for i in range(n):
    l2 = list(map(int, sys.stdin.readline().split(" ")))
    if 2 in l2:
        a= i
        b = l2.index(2)
    l.append(l2)

l[x][y] = 2
func(x, y)

for i in range(n):
    for j in range(m):
        if l[i][j] == 1:
            l[i][j] = -1
        elif l[i][j] == 0:
            pass
        else:
            l[i][j] = l[i][j]-2
print_l(l)

 

 

위의 방법처럼 재귀 함수를 통해 한 방향으로 계속 가면서 막힌 경우 다른 곳으로 이동하는 방향으로 생각했다.

 

하지만 이 방법으로 수행하면

 

 

...??

위의 답이 나오게 된다.

재귀함수를 사용하게 되면 각 방향으로 끝까지 가버린다.

 

각 방향의 끝까지 간 후에 막히거나 0을 만나면 그 다음 방향으로 끝까지 가버리게 되는 거다.

 

 

즉 시계방향으로 계속 돌면서 수를 더할 것이다.

 

 

 

우리는 한 점으로 부터 시작해서 각각의 점까지의 최단 거리를 적고 싶다. 

 

즉

만족!

 

위처럼 한칸 옮기기 전에 4방향 모든 곳에 영향을 주어야 한다. 

 

그러려면 어떻게 해야 할까..?

 

 

 

 

한 점을 기준으로 4방향의 좌표를 순서대로 넣고, 먼저 넣은 좌표를 기준으로 또 4방향의 좌표를 넣으면 된다.

 

즉 

 

 

먼저 들어간 좌표에 대해서 4방향을 계산한 뒤 다음 좌표를 순서에 추가하면 된다.

 

 

 

FIFO

 

예를 들어보자

 

시작값 = [0,0] 

[0,0] 에서 4방향의 값을 더해주고 각 좌표를 넣어준다. = [[1,0], [0,1], [-1,0], [0,-1]]

 

 

다음에는 가장 면저 넣은 좌표를 뺀다.

[1,0]   ,  [[0,1], [-1,0], [0,-1]]

 

 

그리고 뺀 값을 기준으로 4방향의 값을 더해주고 좌표를 넣어준다.

기준값 = [1,0]

 

 [[0,1], [-1,0], [0,-1], [2,0], [1,1], [0,0], [1,-1]]

 

리스트를 보면 기준의 방법과는 다른 것을 볼 수 있다.

 

 

처음 내가 작성했던 코드는 한 방향으로만 계속 갈 것이다.

재귀함수로 작성했으니까 더 이상 갈 수 없을 때까지 간 후, 다음 방향으로 계속 갈 것이다.

 

 

하지만 FIFO 방식을 이용한다면..? 

 

 

각각의 좌표에서 한방향이 아니라 4방향 모든 값에 영향을 준 뒤 방향으로 이동하므로 최단 거리를 구할 수 있는 것이다.!

 

 

 

 

 

import sys
from collections import deque
    
def print_l(l):
    for i in l :
        for j in i:
            print(j,end=" ")
        print()
        


n, m = map(int, sys.stdin.readline().split(" "))
l = []
a,b = 0, 0
for i in range(n):
    l2 = list(map(int, sys.stdin.readline().split(" ")))
    if 2 in l2:
        a = i
        b = l2.index(2)
    l.append(l2)



d = deque([[a,b]])

direction = [[0,1], [1,0],[0,-1],[-1,0]]


while d:
    d2 = d.popleft()
    a,b = d2[0], d2[1]

    for dir in direction:
        if 0 <= a+dir[0] < n and 0<= b+dir[1] < m:
            if l[a+dir[0]][b+dir[1]] == 1:
                l[a+dir[0]][b+dir[1]] = l[a][b] + 1
                d.append([a+dir[0], b+dir[1]])


for i in range(n):
    for j in range(m):
        if l[i][j] == 0:
            pass
        elif l[i][j] == 1:
            l[i][j] = -1

        else:
            l[i][j] = l[i][j]-2
        
print_l(l)

 

 

 

 

 

 

 

따라서 위의 방식을 이용하여 bfs 를 구현한 코드이다.

 

 

문제를 구현하면서 도움이 될만한 팁이 있다.

 

 

항상 문제를 구현하면 값을 입력하고, 정답의 형식을 갖춰 제출하는 코드가 있을 것이다.

 

이 코드를 미리 함수로 만들어서 사용한다면 반복되는 과정을 빠르고 정확하게 정리할 수 있다!!