백준 2178(파이썬):미로 탐색

in CS study / Baekjoon

백준 2178번 문제 정리글 입니다.

문제 출처-https://www.acmicpc.net/problem/2178

문제 내용

백준 2178번

나의 풀이

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

    def bfs():
        global minimum

        queue=deque()
        queue.append((0,0,1))
        while queue:
            x,y,temp=queue.popleft()
            for i in range(4):
                rx,ry=x+dx[i],y+dy[i]
                if 0<=rx<n and 0<=ry<m and visited[rx][ry]==0 and maze[rx][ry]==1:
                    if rx==n-1 and ry==m-1:
                        temp+=1
                        minimum=min(minimum,temp)
                    visited[rx][ry]=1
                    queue.append((rx,ry,temp+1))

        return print(minimum)
        
    n,m=map(int,input().split())
    maze=[list(map(int,input())) for _ in range(n)]
    visited=[[0]*m for _ in range(n)]
    dx=[1,-1,0,0]
    dy=[0,0,1,-1]
    minimum=1e9

    bfs()
  1. 우선 미로를 통해 오른쪽 끝 아래로 도달하는 문제라 BFS로 접근하여 해결하려했다.
  2. 큐에 좌표값과 탐색시 깊이(레벨)의 값도 넣어서 목표지점에 도달할 때마다 최소값과 비교하여 최소값을 갱신했다.

처음에는 맨 처음으로 목표지점에 도달하는 경우가 최소일것이라고 생각했다… 그게 아니라 목표지점에 도달하는 경우들 중에서 최소거리를 구하도록 해야 제대로된 값을 구할 수 있다…(제일 먼저 도달했다고 해서 최소 값이 아닐 수도 있다)

풀이를 본 후

따로 방문 배열을 만들지 않고 주어진 미로 좌표값을 더하면서 BFS로 진행한 풀이도 있었다…

해결한 후

이 문제 또한 DFS로도 해결할 수 있으므로 DFS의 방식도 알고있어야한다… 문제 해결시 신중하게 생각후 문제를 풀도록 한다…