- 1은 지날 수 있는 칸, 0은 지날 수 없는 칸
- 이동은 상, 하, 좌, 우 의 인접한 칸으로만 이동 가능.
[ 입력 ]
- 첫째 줄에 미로의 크기 N(가로), M(세로) 입력.
- 다음 N 개 줄에 M 개의 정수로 미로 입력.
- 각각의 수들은 붙어서 입력.
- 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어짐.
[ 출력 ]
- 지나야 하는 최소의 칸 수 출력.
이번 최단 칸수 구하기와 같은 유형의 문제는 그래프 탐색 방법중에서도 BFS 를 사용하면 쉽게 해결이 가능하다.
BFS 는 현재 노드와 연결된 모든 노드 탐색 후 방금 탐색한 노드들을 기준으로 또 연결되어있는 모든 노드 탐색 . . . 해서 모든 노드를 전부 탐색하는 방법이다.
이러한 유형의 문제를 BFS 로 풀면 하나의 노드마다 접근할 수 있는 곳을 알 수 있게 되고, 그 칸은 현재 노드 + 1 의 칸을 추가하면 접근할 때 거치는 최소 칸의 수를 저장할 수 있게 된다.
이번 미로찾기 문제 역시 처음 시작지점부터 BFS 로 탐색을 시작한 후 마지막 최종 노드 위치에 저장된 방문한 칸의 개수를 출력하면 문제가 해결된다.
- 정리하면 아래와 같은 방식으로 해결할 수 있다.
- 입력받은 시작점부터 BFS 탐색을 하는데, 현재 위치에서 상, 하, 좌, 우 를 탐색해 방문 가능하다면 현재 위치에 저장되어있는 방문 칸수 + 1 을 다음위치에 저장해준다.
- 1번의 과정을 모든 노드에 대해서 반복한다. ( BFS 다보니 queue 에 push - pop 을 해주면서 queue 가 빌 때까지 반복 )
- 최종적으로 도착위치 ( N, M ) 의 방문 칸수를 출력하면 해결!
- grid 의 입력이 공백 없이 붙어서 입력
- 이 부분은
scanf("%1d", &graph[i][j]);
와 같이 입력받으면 해결
2. 상, 하, 좌, 우 를 탐색하는 방법
- 이 부분은 dx, dy technique 을 사용해 간단히 해결!
#include <iostream>
#include <queue>
#define N_MAX 100
#define M_MAX 100
using namespace std;
// 전역변수 설정
int N = 0, M = 0; // grid size (N x M)
// grid 선언
int graph[N_MAX][M_MAX] = {0, };
// 지나야 하는 최소의 칸 수 저장 배열
int result [N_MAX][M_MAX] = {0, };
// 상, 하, 좌, 우 를 탐색하기 위한 dx, dy 선언
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
// 방문 확인 배열
bool is_visit[N_MAX][M_MAX] = {false, };
// 가능한 범위인지 확인
bool inRange(int x, int y) {
// grid 를 벗어나지는 않았는지 확인
bool ingrid = (0 <= x && x < N && 0 <= y && y < M);
// 그 위치에 갈수없는 즉, 값이 0인지 확인
bool possible_pos = (graph[x][y] != 0);
return (ingrid && possible_pos);
}
// BFS 에서 사용할 queue
queue< pair <int, int> > q;
// BFS 탐색
void BFS(int x, int y) {
// queue 가 빌 때까지 반복
while(!q.empty()) {
int a = q.front().first;
int b = q.front().second;
q.pop();
// 현재 (a, b) 위치에서 상, 하, 좌, 우 4가지 방향 확인
for(int i = 0; i < 4; i++) {
// 다음 위치의 좌표 구하기
int nx = a + dx[i];
int ny = b + dy[i];
// 가능한 범위라면 방문 확인 후 방문하지 않았다면 queue 에 위치 저장 후
// 이동할 때 지나야 하는 칸을 이전 방문 위치 (a, b) 의 값에 1 추가해 현재 좌표에 저장
if(inRange(nx, ny) && (is_visit[nx][ny] == false)) {
q.push(make_pair(nx, ny));
is_visit[nx][ny] = true;
result[nx][ny] = result[a][b] + 1;
}
}
}
}
int main() {
// grid size 입력
cin >> N >> M;
// grid 입력 (공백없이 붙어서 입력으로 주어지므로 정수 하나씩 받아서 처리)
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
scanf("%1d", &graph[i][j]);
}
}
// 첫번째 위치 queue 에 저장 후 방문 표시
q.push(make_pair(0, 0));
is_visit[0][0] = true;
// 시작위치도 칸을 세므로 시작위치의 결과값 1 저장
result[0][0] = 1;
// BFS 로 방문하며 지나야 하는 최소의 칸수 구하기
BFS(0, 0);
// 도착 위치의 방문 칸 수 출력 (result)
cout << result[N-1][M-1] << endl;
return 0;
}