[백준/Python] 2178번 미로 탐색

---

문제

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

---

문제이해

문제 이해는 꽤 쉬웠다. 1을 따라 최단 경로로 도착지까지 도착하면 되는 문제였다.

이것 역시 너비우선탐색(BFS)로 푸는 문제이다.

---

문제풀이(정답)

from collections import deque

n, m = map(int, input().split())

lines = [list(map(int, input().strip())) for _ in range(n)]

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

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

def bfs(x,y):

    queue = deque([(x,y)])

    while queue:

        x, y = queue.popleft()      # 방문 좌표 제거

        for i in range(4):

            nx = x + dx[i]

            ny = y + dy[i]

            if nx < 0 or nx >= n or ny < 0 or ny >= m: # 좌표 상 없는 좌표

                continue

            if lines[nx][ny] == 0: # 벽으로 막혀있는 곳

                continue

            if lines[nx][ny] == 1:

                lines[nx][ny] = lines[x][y] + 1

                queue.append((nx,ny))

    return lines[n-1][m-1]

print(bfs(0,0))

 

먼저 lines를 입력받을 때 보통은 split()함수를 사용하는데 이 문제에서는 strip() 함수를 사용했다.

strip() 함수 : 공백 제거 함수

• split()을 사용하면 공백이 없는 숫자 문자열 (101111)을 나누지 못해서 잘못된 입력 처리가 됨.
• list(input().strip())을 사용하면 각 숫자가 한 자리씩 리스트로 변환됨.
• 공백이 있는 숫자라면 split()을 사용하고, 공백 없이 붙어 있는 숫자라면 list()를 사용해야 한다!

 

dx, dy 테크닉

dx와 dy 변수를 이용해 좌표를 상하좌우로 움직이는 코드에 사용했다.

# 우 → 하 → 상 → 좌
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

 

처음에는 이해가 되지 않았지만 좌표를 그려 생각하고 dx는 행 dy는 열이라 생각을 하면 이해가 쉽게 된다.

그리고 밑에 그림처럼 좌표를 그려 생각을 하면 위의 코드가 이해가 될 것이다.

if문을 이용해 갈 수 있는 경로 찾기

첫 번째 if문은 좌표상 없는 곳으로 간다면 무시하고 계속하라는 코드이다.

두 번째 if문은 문제에서 0으로 있는 곳은 가지 못하기 때문에 벽으로 막혀 있다면 무시하고 계속하라는 코드이다.

세 번째 if문은 이동을 할 수 있다면, 큐에 좌표를 추가하라는 코드이다.

 

좌표가 끝 지점에 도달하면 최단 경로를 구할 수 있다.