[python] 백준 - 2178. 미로 탐색

문제 해결

1. BFS 기본 문제. S1

2. 출발점을 1로 만들고 한칸씩 전진하며 1씩 더해준다. - BFS 이용

 (1) 4 방향 탐색을 위해 dx, dy 를 만든다 ( 상하좌우).

 (2) 리스트(여기서는 디큐를 사용함)에 출발점을 넣어준다.

 (3) 탐색이 언제 끝날지 모르니까 while 문을 사용한다.

 (4) 리스트에서 pop(0)(여기서는 popleft())을 이용해 하나씩 꺼내준다. ( 0번을 꺼내는 이유는 BFS 기법을 사용해야 하기 때문에)

 (5) 꺼낸 지점에서 4방향 탐색을 해준다.

 (6) 탐색한 곳(nx, ny)이 '1' 인 경우 그 칸에 현재 칸(x, y) 숫자의 +1을 해주고, 리스트에 append해준다.

 (7) (4)번부터 다시 반복한다.

3. 각 숫자가 이동한 칸의 갯수를 나타낸다.

4. 마지막 칸의 숫자를 답으로 출력한다.

 

🌞 프로젝트를 하나 하느라 바빠서 그 동안 알고리즘 문제를 풀지 못했다. 오랜만에 푸는 문제라 가벼운 문제로 시작했다. 

 

소스 코드

from _collections import deque


def bfs(lst, start):
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]

    q = deque()  # 효율을 위해 deque를 사용
    q.append(start)
    lst[start[0]][start[1]] = 1  # 시작점을 1로 바꿔준다.

    # 모든 지점을 인접한 한칸씩 탐색하기 위해 BFS
    while q:
        x, y = q.popleft()  # q에서 한 지점을 꺼내고
        for k in range(len(dx)):  # 4방향 탐색을 한다.
            nx = x + dx[k]
            ny = y + dy[k]
            if 0 <= nx < len(lst) and 0 <= ny < len(lst[0]):  # 인덱스를 벗어나는 것을 방지
                if lst[nx][ny] == '1':  # 이동할 수 있는 칸('1')이면
                    lst[nx][ny] = lst[x][y] + 1  # 한칸 이동이므로 이전 칸 +1
                    q.append((nx, ny))

    return lst[-1][-1]


#####################################################################
N, M = map(int, input().split())
maze = [list(input()) for _ in range(N)]
print(bfs(maze, (0, 0)))

 

출처: BACKJOON ONLINE JUDGE

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

2178번: 미로 탐색

문제 N×M크기의 배열로 표현되는 미로가 있다. 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다. 위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다. 입력 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. 출력 첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.