[백준/Python] DFS/BFS-2178번. 미로탐색

📌 문제 설명 

NxM크기의 배열로 표현되는 미로가 있다. 
 
미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1,1)에서 출발하여 (N,M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다. 
아래의 예에는 15칸을 지나야 (N,M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다. N×M크기의 배열로 표현되는 미로가 있다.

# 입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각가의 수들은 붙어서 입력으로 주어진다. 

 

# 출력 

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착 위치로 이동할 수 있는 경우만 입력으로 주어진다. 
 

📌 풀이 코드

# 정답

=> 최단 거리를 탐색하는 문제니까, BFS가 옳다고 생각했다. 

• dx, dy로 현재 (x,y)에 대해 상하좌우에 대해 탐색할 수 있도록 한다. 
• nextX, nextY = (x,y)의 상하좌우 좌표
  • 만약 방문했던 (x,y)이면 continue
  • ✅ 아닌 경우, 그래프 값이 1인지 확인하고
  • ✅ 맞으면 큐에 append하고 해당 위치에 몇번째 방문한 블록인지 저장한다. 
    • => 방문한 이전 좌표 값에 1을 더하면 된다!!!

N, M = map(int, input().split())
graph = []
visited = [[False]*M for _ in range(N)]
for i in range(N):
    graph.append(list(map(int, input())))
# for row in graph: 
#    print(row)
end = [N-1, M-1]
# 상x-1y 하x+1y좌xy-1우xy+1 
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
q = []
# 상 하 좌 우로 움직였을 때, 배열을 벗어나지 않으면 
# 거기에 통로가 있는지 graph == 1 보고 맞으면 bfs 또 수행 
def bfs(x,y):
    q.append((x,y))
    # count = 0
    while q:
        x, y = q.pop(0)
        visited[x][y] = True 
        # print(f"ABOUT (x,y) = {x}, {y}")
        if end == [x,y]: 
            return graph[N-1][M-1]
            # print("END")   
            #return (count) 
        for i in range(4):
            nextX, nextY = x+dx[i], y+dy[i]
            if 0<=nextX<N and 0<=nextY<M:
                # print(f"\tABLE nextX, nextY = {nextX}, {nextY}")
                if visited[nextX][nextY]:
                    #print("\t\t\tALREADY VISITED")
                    continue
                if graph[nextX][nextY] == 1: 
                    q.append((nextX, nextY))
                    graph[nextX][nextY] = graph[x][y] + 1
                    # count += 1
                    # print(f"\t\tPOSSIBLE count = {count} q.append(({nextX}, {nextY}))")
                    
print(bfs(0, 0))

---

#시도1. <실패>

(주석(#)은 테스팅 코드임.)

• 실패한 이유: count가 방문하는 블록마다 1씩 증가되는데, 테스팅 코드를 돌려보면 코드 아래 글과 같다. 
• 이때 (1,4) 방문 이후 (0,5)는 방문할 때 count를 세면 안되는데 count를 안 세게 할 방법이 없음. 
• 따라서, 그래프 내 블록에 방문횟수를 직접 저장하며 가는 게 정답이다. 

N, M = map(int, input().split())
graph = []
visited = [[False]*M for _ in range(N)]
for i in range(N):
    graph.append(list(map(int, input())))
# for row in graph: 
#    print(row)
end = [N-1, M-1]
# 상x-1y 하x+1y좌xy-1우xy+1 
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
q = []
# 상 하 좌 우로 움직였을 때, 배열을 벗어나지 않으면 
# 거기에 통로가 있는지 graph == 1 보고 맞으면 bfs 또 수행 
def bfs(x,y):
    q.append((x,y))
    count = 0
    while q:
        x, y = q.pop(0)
        visited[x][y] = True 
        count += 1
        # print(f"ABOUT (x,y) = {x}, {y}")
        if end == [x,y]: 
            # print("END")
            return (count)
        for i in range(4):
            nextX, nextY = x+dx[i], y+dy[i]
            if 0<=nextX<N and 0<=nextY<M:
                # print(f"\tABLE nextX, nextY = {nextX}, {nextY}")
                if visited[nextX][nextY]:
                    # print("\t\t\tALREADY VISITED")
                    continue
                if graph[nextX][nextY] == 1: 
                    q.append((nextX, nextY))
                    # print(f"\t\tPOSSIBLE count = {count} q.append(({nextX}, {nextY}))")
                    # visited[nextX][nextY] = True
                    # graph[nextX][nextY] = graph[x][y] + 1
print(bfs(0, 0))

=> 테스팅 코드를 포함해 돌려보았을 때, 아래와 같음. 

4 6
101111
101010
101011
111011
[1, 0, 1, 1, 1, 1]
[1, 0, 1, 0, 1, 0]
[1, 0, 1, 0, 1, 1]
[1, 1, 1, 0, 1, 1]
ABOUT (x,y) = 0, 0
        ABLE nextX, nextY = 1, 0
                POSSIBLE count = 1 q.append((1, 0))
        ABLE nextX, nextY = 0, 1
ABOUT (x,y) = 1, 0
        ABLE nextX, nextY = 0, 0
        ABLE nextX, nextY = 2, 0
                POSSIBLE count = 2 q.append((2, 0))
        ABLE nextX, nextY = 1, 1
ABOUT (x,y) = 2, 0
        ABLE nextX, nextY = 1, 0
        ABLE nextX, nextY = 3, 0
                POSSIBLE count = 3 q.append((3, 0))
        ABLE nextX, nextY = 2, 1
ABOUT (x,y) = 3, 0
        ABLE nextX, nextY = 2, 0
        ABLE nextX, nextY = 3, 1
                POSSIBLE count = 4 q.append((3, 1))
ABOUT (x,y) = 3, 1
        ABLE nextX, nextY = 2, 1
        ABLE nextX, nextY = 3, 0
        ABLE nextX, nextY = 3, 2
                POSSIBLE count = 5 q.append((3, 2))
ABOUT (x,y) = 3, 2
        ABLE nextX, nextY = 2, 2
                POSSIBLE count = 6 q.append((2, 2))
        ABLE nextX, nextY = 3, 1
        ABLE nextX, nextY = 3, 3
ABOUT (x,y) = 2, 2
        ABLE nextX, nextY = 1, 2
                POSSIBLE count = 7 q.append((1, 2))
        ABLE nextX, nextY = 3, 2
        ABLE nextX, nextY = 2, 1
        ABLE nextX, nextY = 2, 3
ABOUT (x,y) = 1, 2
        ABLE nextX, nextY = 0, 2
                POSSIBLE count = 8 q.append((0, 2))
        ABLE nextX, nextY = 2, 2
        ABLE nextX, nextY = 1, 1
        ABLE nextX, nextY = 1, 3
ABOUT (x,y) = 0, 2
        ABLE nextX, nextY = 1, 2
        ABLE nextX, nextY = 0, 1
        ABLE nextX, nextY = 0, 3
                POSSIBLE count = 9 q.append((0, 3))
ABOUT (x,y) = 0, 3
        ABLE nextX, nextY = 1, 3
        ABLE nextX, nextY = 0, 2
        ABLE nextX, nextY = 0, 4
                POSSIBLE count = 10 q.append((0, 4))
ABOUT (x,y) = 0, 4
        ABLE nextX, nextY = 1, 4
                POSSIBLE count = 11 q.append((1, 4))
        ABLE nextX, nextY = 0, 3
        ABLE nextX, nextY = 0, 5
                POSSIBLE count = 11 q.append((0, 5))
ABOUT (x,y) = 1, 4
        ABLE nextX, nextY = 0, 4
        ABLE nextX, nextY = 2, 4
                POSSIBLE count = 12 q.append((2, 4))
        ABLE nextX, nextY = 1, 3
        ABLE nextX, nextY = 1, 5
ABOUT (x,y) = 0, 5
        ABLE nextX, nextY = 1, 5
        ABLE nextX, nextY = 0, 4
ABOUT (x,y) = 2, 4
        ABLE nextX, nextY = 1, 4
        ABLE nextX, nextY = 3, 4
                POSSIBLE count = 14 q.append((3, 4))
        ABLE nextX, nextY = 2, 3
        ABLE nextX, nextY = 2, 5
                POSSIBLE count = 14 q.append((2, 5))
ABOUT (x,y) = 3, 4
        ABLE nextX, nextY = 2, 4
        ABLE nextX, nextY = 3, 3
        ABLE nextX, nextY = 3, 5
                POSSIBLE count = 15 q.append((3, 5))
ABOUT (x,y) = 2, 5
        ABLE nextX, nextY = 1, 5
        ABLE nextX, nextY = 3, 5
                POSSIBLE count = 16 q.append((3, 5))
        ABLE nextX, nextY = 2, 4
ABOUT (x,y) = 3, 5
17