[백준 2178] 미로 탐색

🍎 [백준 2178] 미로 탐색

문제 링크

⚾ 코드

    from collections import deque

    N, M = map(int, input().split())
    grid = []
    visited = [[False]*M for _ in range(N)]

    for _ in range(N):
        grid.append(list(map(int, input())))

    q = deque()

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


    def check_range(x, y):
        if x >= 0 and x < N and y >= 0 and y < M:
            return True
        return False


    def bfs(a, b):
        visited[a][b] = True
        q.append([a, b])

        while q:
            x, y = q.popleft()
            for i in range(4):
                nx = x+dx[i]
                ny = y+dy[i]

                if check_range(nx, ny) and grid[nx][ny] == 1 and visited[nx][ny] == False:
                    q.append([nx, ny])
                    visited[nx][ny] = True
                    # 이전 방문 기록 + 1
                    grid[nx][ny] = grid[x][y]+1


    bfs(0, 0)
    print(grid[N-1][M-1])

 

🔔 해결과정 & 깨달은 점

• BFS의 아이디어를 활용해 풀었다.
• 아직 방문하지 않았다면, 전의 경로에 + 1
• 띄어 쓰기가 되어 있지 않은 grid를 받을 때는 list(map(int,input())) 해주기
• grid를 활용하면 따로 경로 리스트를 만들지 않아도 된다!