[C++] 백준(BOJ) - 2178 : 미로 탐색
인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.
문제
N×M크기의 배열로 표현되는 미로가 있다.
미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.
위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.
입력
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
출력
첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.
알고리즘
- 그래프 이론
- 그래프 탐색
- 너비 우선 탐색 (BFS)
풀이
- 네 방향 탐색을 위한 y, x 배열 미리 만들기
const int dy[] = { -1, 0, 1, 0 };
const int dx[] = { 0, 1, 0, -1 };
- 주어진 미로를 미리 만들어진 배열에 담기
- 최단 거리 탐색을 위한 BFS 탐색 진행하기
코드
// BOJ - 2178 : 미로탐색
#include <bits/stdc++.h>
using namespace std;
const int dy[] = { -1, 0, 1, 0 };
const int dx[] = { 0, 1, 0, -1 };
int n, m, x, y;
int a[104][104], visited[104][104];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for (int i = 0; i < n; i++)
{
string str;
cin >> str;
for (int j = 0; j < str.size(); j++)
{
a[i][j] = str[j] - '0';
}
}
queue<pair<int, int>> q; // BFS 탐색을 위해 pair 자료형을 담는 Queue 선언
q.push({ 0,0 });
visited[0][0] = 1; // 최초 방문 지역 1로 카운팅
while (q.size())
{
tie(y,x) = q.front();
q.pop();
for (int i = 0; i < 4; i++)
{
int ny = y + dy[i];
int nx = x + dx[i];
if (ny >= n || nx >= m || ny < 0 || nx < 0 || !a[ny][nx]) continue; // 탐색이 불가능한 지역 걸러내기
if (visited[ny][nx]) continue; // 이미 탐색을 한 지역 제거
visited[ny][nx] = visited[y][x] + 1; // 최단 거리 탐색을 위한 코드
q.push({ ny,nx });
}
}
cout << visited[n - 1][m - 1] << '\n';
return 0;
}
평가
- 최단 거리 탐색을 위한 BFS는 코딩 테스트 단골 문제이다. 그래프 탐색 이론인 BFS와 DFS는 필수적으로 연습이 필요하고, 위 문제와 같이 네 방향 탐색이 아닌 8방향 탐색 등 다양한 응용 문제도 연습하자
