[백준] 2178 미로 (파이썬/python)

🎈문제

https://www.acmicpc.net/problem/2178

 

🎁어떤 알고리즘?

1. 지나야하는 최소 칸수를 출력해야 하므로 bfs로 결정. ( bfs 란? )

2. 최적의 루트를 찾을 때는 맵에 이동 횟수를 저장해나가는 것이 좋다.(자주 쓰이므로 꼭 기억)

 

💻코드

from collections import deque

def bfs(x,y):
    deq = deque()
    deq.append([x,y])
    # 상하좌우 이동을 위한 좌표 설정
    dx = [0,0,-1,1]
    dy = [1,-1,0,0]
    while deq:
        x,y = deq.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx  < 0 or nx > (n-1) or ny < 0 or ny > (m-1):
                continue
            if graph[nx][ny] == 1:    # 1을 만나면
                graph[nx][ny] = graph[x][y] + 1
                deq.append([nx,ny])   # 해당 좌표의 상하좌우를 조사해보기 위해 큐에 저장

    return graph[n-1][m-1]

# n: 세로(x), m : 가로(y)
n,m = map(int, input().split())
# graph
graph = []
for i in range(n):
    graph.append(list(map(int,input())))

# 탐색 시작
print(bfs(0,0))

🎄코드 설명

1. 가로 세로 그래프의 크기를 n,m변수로 받아준다.

2. graph 변수에 미로 정보를 받아온다. ( input으로 받아오면 str()형이 되고, 나중에 미로의 각 칸마다 이동 횟수를 저장해 나갈 것을 고려하여 int형으로 변환 후 list형태로 저장 : '10101' -> [1,0,1,0,1] )

3. 문제에서 (1,1)에서 출발하여 (N,M)의 위치로 이동하는데 지나야하는 최소 칸 수를 구하라 했으므로 bfs()에 바로 (0,0)좌표를 넣고 bfs돌리기로 결정 (이때, 문제에서 (1,1)이 내 2차원 리스트에서는 (0,0)임을 써두거나 기억해 둘 것)

4. bfs 함수로 넘어와서, 받은 좌표를 큐에 넣는다.

5. 상하좌우로만 이동할 수 있다고 했으므로 해당 상하좌우에 해당하는 좌표값을 dx,dy에 넣어둔다.

6. while deq:으로 설정함으로써 큐가 모두 빌 때까지 반복하도록 함.

7. 큐에 들어있는 값(0,0)을 빼내어 x,y 변수에 집어 넣고, for문을 통해 상하좌우 4방향으로 이동해보기 시작한다.

8. 좌표 이동을 했을 때, graph를 벗어나면 그 밑의 코드는 수행하지 않는다.

9. 좌표 이동을 했을 때, 해당 좌표값이 1이면 이동할 수 있는 칸이라는 뜻이므로 이전 좌표의 값에서 1을 더해준다.

10. 큐가 모두 비게되어 while문을 벗어나게 되면 bfs()를 반복하며 자신이 갈 수 있는 모든 좌표를 다 돌아보고 나오게 된다.

11. 따라서 (N,M)의 위치인 graph[n-1][m-1]을 return한다.