2178. 미로 탐색

문제 링크

2178. 미로 탐색

문제 코드

from collections import deque

num_list = list(map(int,input().split()))

row = num_list[0]
col = num_list[1]

maze = [[0 for c in range(col)]for r in range(row)]
visited =[[0 for c in range(col)]for r in range(row)]

for i in range(row):
    num_list = input()
    for j in range(col):
        maze[i][j] = int(num_list[j])

#print(maze)
que = deque()

que.append([0,0,1]) #x,y,count
visited[0][0]=1
while len(que)>0:
    x,y,count = que.popleft()

    if x == row - 1 and y == col-1 :
        print(count)
        break

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

    for i in range(4):
        next_x = x+dx[i]
        next_y = y+dy[i]
        if 0<=next_x<row and 0<=next_y<col and visited[next_x][next_y] == 0 and maze[next_x][next_y] == 1:
            que.append([next_x,next_y,count+1])
            visited[next_x][next_y] = 1

문제 풀이

• 기본적인 BFS 문제
• 4방향으로 가고 visited 0, maze 1이면 방문하도록