최대 1 분 소요

미로 탈출

문제

[백준] [python] 2178번: 미로 탐색

문제와 상동함.

그래서!

위의 문제 풀이와

조금 다르게 구현을 해보았다.

나의 코드

첫 번째 시도.

from collections import deque

n,m = map(int,input().split())
graph = []
for i in range(n):
    graph.append(list(map(int,input())))

#상/하/좌/우
dx = [-1,1,0,0] 
dy = [0,0,-1,1]

def bfs(x,y):
    
    queue = deque([(x,y)])
    while queue:
        x,y = queue.popleft()
           for i in range(4):
               nx = x + dx[i]
               ny = y + dy[i]
               
            if nx < 0 or ny < 0 or nx > n-1 or ny > m-1:
                continue
            if graph[nx][ny] == 0:
                   continue
               if graph[nx][ny] == 1:
                   graph[nx][ny] = graph[x][y]+1
                   queue.append((nx,ny))
    return graph[n-1][m-1]

    print(bfs(0,0))

»input

    5 6
   101010
   111111
   000001
   111111
    111111

»output

   10

🌝 Thinking

백준 2178번 문제를 풀이할때 탐색의 깊이를 이용하여 최단경로의 수를 구하였다.

하지만 이코테에서 제시하는 답안은 위의 문제 풀이와 같이 새로운 길(노드)이 나타날때마다 부모노드의 값에 +1을 해준다.

그렇다면 노드위에 새겨진 숫자가 출발지로 부터 떨어진 거리가 된다. 즉 depth

와…이렇게 생각할 수도 있구나,,,

세상은 넓고 똑똑한 사람 진짜 많다…😓

💡 깨달은 점.

  1. 이동을 구현할때는 상/하/좌/우 움직임을 나타내는 리스트를 활용하는 것이 코드가 훨씬 깔끔해진다.

출처

이것이 코딩 테스트다 - 나동빈 저

댓글남기기

참고