[Python] 2178 - 미로 탐색

문제

2178번: 미로 탐색

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

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

N×M크기의 배열로 표현되는 미로가 있다.

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

• 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다.

• 다음 N개의 줄에는 M개의 정수로 미로가 주어진다.

• 각각의 수들은 붙어서 입력으로 주어진다.

출력

• 첫째 줄에 지나야 하는 최소의 칸 수를 출력한다.

• 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

---

풀이

• 경로에서 최솟값을 찾는 문제로 뭔가 DP랑 완전탐색이 생각났는데 BFS로 풀렸다.

• BFS를 잘 안 풀어봐서 나름 colletions패키지에서 deque모듈도 갖다 쓰고 했는데 그냥 list로 풀어도 된다.

• 이런 문제는 두가지를 조심해야한다고 생각한다.
  1. 4방향으로 움직일때 out of range가 발생하지 않도록 주의
  2. 큐에 담은 것을 또 담지 않도록 주의

• BFS나 완전탐색의 개념을 모른다면 먼저 공부하고 코드를 볼 것을 추천한다.

설명

• 큐가 존재하는 동안 돌아가는 반복문은 아래와 같은 순서로 일을 한다.
  1. 큐에서 하나를 꺼낸다.
  2. 꺼낸 값을 방문했다는 의미로 0으로 만든다.
  3. 꺼낸 값 주위의 4방면을 탐색한다.
  4. 아직 방문하지 않은 1인 지점을 찾고 큐에 들어있진 않은지 확인한다.
  5. 큐에도 없으면 큐에 추가한다.
  6. 추가적으로 cost라는 횟수를 저장하는 2차원 배열에서 최솟값을 찾아 +1해서 갱신해준다.

• 6번을 그냥 쉽게 while이 반복되는 횟수를 세는 방식으로 풀기도 하는 것 같은데 조금 더 명확해보이는 방식으로 풀었고 푸는데는 지장이 없다.

답

from sys import stdin, maxsize
from collections import deque

input = stdin.readline


def exploring_labyrinth(l, n, m):
    cost = [[maxsize for _ in range(m)] for _ in range(n)]
    cost[0][0] = 1
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    dq = deque([[0, 0]])
    while dq:
        cur = dq.popleft()
        l[cur[0]][cur[1]] = '0'
        # 4방향 찾기
        for di in range(4):
            # 갈 수 있는 곳이 있으면 큐에 저장
            dxi = cur[0] + dx[di]
            dyi = cur[1] + dy[di]
            if 0 <= dxi < n and 0 <= dyi < m:
                if l[dxi][dyi] == '1' and [dxi, dyi] not in dq:
                    dq.append([dxi, dyi])
                # 최솟값 + 1
                cost[cur[0]][cur[1]] = min(cost[cur[0]][cur[1]], cost[dxi][dyi] + 1)
    return cost[-1][-1]


if __name__ == "__main__":
    N, M = map(int, input().split())
    labyrinth = [list(input().strip()) for _ in range(N)]
    res = exploring_labyrinth(labyrinth, N, M)
    print(res)

볼때마다 느끼는 건데 2년전에 C++로 어케 풀었지,,,? 그리고 C계열은 역시 엄청 빠르고 tiny하네..

Uploaded by Notion2Tistory v1.1.0