[백준_그래프] 2178번 - 미로 탐색

문제

 

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

 

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

 

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

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

 

 

입력

 

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

 

출력

 

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

 

 

 

 

예시 입력

 

4 6
101111
101010
101011
111011

 

 

 

예시 출력

 

15

 

 

 

 

풀이

 

미로 탐색 문제는 주어진 미로에서 출발점에서 도착점까지의 경로를 찾는 문제입니다. 

 

이러한 문제를 해결하기 위한 일반적인 접근 방식은 다음과 같습니다.

1. BFS 또는 DFS 선택: 주로 BFS(너비 우선 탐색) 또는 DFS(깊이 우선 탐색) 알고리즘을 사용하여 문제를 해결할 수 있습니다. 두 알고리즘 중 어떤 것을 선택할지는 상황에 따라 다를 수 있습니다. BFS는 최단 경로를 찾을 때 유용하며, DFS는 경로가 깊을 때 유용합니다.

2. 미로 정보 입력: 주어진 미로 정보를 데이터 구조에 저장합니다. 일반적으로 2D 배열이 사용되며, 각 셀은 벽(0) 또는 이동 가능한 경로(1)로 표시됩니다.

3. 시작점과 도착점 설정: 출발점과 도착점을 설정합니다. 출발점은 주로 (0, 0)으로 설정하며, 도착점은 미로의 끝점으로 설정합니다.

4. 탐색 알고리즘 수행: 선택한 BFS 또는 DFS 알고리즘을 사용하여 미로를 탐색합니다. 출발점에서 시작하여 가능한 경로를 따라 미로를 탐색하며, 방문한 셀을 표시하거나 큐 또는 스택에 추가합니다.

5. 경로를 찾았을 때: 도착점에 도착했을 때(도착점의 좌표에 도달했을 때) 경로를 찾았다고 판단하고 알고리즘을 종료합니다.

6. 최단 경로 구하기 (선택 사항): BFS를 사용한 경우 최단 경로를 구할 수 있습니다. 도착점에 도착한 순간의 경로 길이가 최단 경로의 길이가 됩니다.

7. 경로 출력 (선택 사항): 최종적으로 경로를 출력하거나 경로를 따라 이동하는 방법을 표시합니다.

 

미로 탐색 문제를 해결할 때 주의해야 할 점은 미로의 크기, 벽과 이동 가능한 경로의 표시, 시작점과 도착점 설정 등입니다. 

 

선택한 탐색 알고리즘에 따라 경로를 찾을 수 있고, BFS를 사용하면 최단 경로를 찾을 수 있습니다.

 

 

소스 코드

 

from collections import deque

# 미로의 크기와 미로 정보 입력 받기
n, m = map(int, input().split())  # 미로의 행과 열의 크기를 입력받음
maze = [list(map(int, input())) for _ in range(n)]  # 미로 정보를 2차원 리스트로 입력받음

dx = [-1, 1, 0, 0]  # 상하좌우 방향 이동을 위한 x 좌표 변화
dy = [0, 0, -1, 1]  # 상하좌우 방향 이동을 위한 y 좌표 변화

def bfs(x,y):
    queue = deque()  # BFS 알고리즘을 위한 큐를 생성
    queue.append((x,y))  # 시작 지점을 큐에 추가
    
    while queue:
        cx, cy = queue.popleft()  # 큐에서 현재 위치를 꺼냄
        
        for i in range(4):  # 상하좌우 4방향에 대해 확인
            nx, ny = cx + dx[i], cy + dy[i]  # 다음 위치 계산
            
            if nx < 0 or ny < 0 or nx >= n or ny >= m:  # 미로 범위를 벗어나면 무시
                continue
            if maze[nx][ny] == 1:  # 벽이 아닌 경우
                maze[nx][ny] == maze[cx][cy] + 1  # 이동 횟수를 1 증가시키고
                queue.append((nx, ny))  # 다음 위치를 큐에 추가
                
    return maze[n-1][m-1]  # 미로의 오른쪽 아래에 도착한 지점의 이동 횟수를 반환

result = bfs(0,0)  # 시작 위치 (0,0)에서부터 BFS 실행
print(result)  # 결과 출력