백준 2178 미로탐색 - C++ BFS

 

해당 문제는 Breadth-first-search(BFS) 방식으로 풀었다.

문제는 c언어로 해결하려할 시 BFS에 거의 필수적인 queue 를 구현해야한다는 것이었다.

근데 거기까진 아직 안배우고 익혀보지 않았기 때문에 우선 문제풀이를 위해 c++ 의 <queue> 라이브러리를 이용해

문제 해결에 집중했다. 

 

BFS 방식은 너비우선탐색으로 가장 기초적인 탐색법으로 많은 경우에 사용된다.

특히 가장 빨리 탈출하는 문제에 특화되어 있는데, 내가 서있는 위치 기준으로 몇 번만에 목표지점까지 

이동할 수 있느냐를 구하는데 아주 유용하다.

 

BFS 의 작동 방식은 위의 그림과 같다.

현재 위치 기준으로, 과거에 방문하지 않은 곳, 갈 수 있는 곳을 기준으로 점차 넓혀가며 탐색한다.

이 때도 2가지 방식이 있는데, 만약 내가 END 에 도착하는 시간만이 중요하다면 위의 그림과 같이 

딱히 칸마다 숫자를 저장하지 않고 단순히 방문했다를 기록하는 정도로만 수행해도 충분하다.

 

만약 갈 수 있는 모든 곳에 가장 빨리 도착하는 시간을 알고 싶다면 모든 칸에서 현재 횟수를 저장하면서 가면 된다.

이 경우 다음 가려는 칸의 횟수가 현재 횟수보다 적다면 가지 않는 식으로 구현하면 된다.

 

벽에 막힐 경우 소멸하게 되고 도착할 수 없는 경우라면 처음 END칸에 저장해놓은 수가 그대로 나온다.

 

졸라맨의 역할을 할 queue 는 다음과 같이 선언한다.

queue<pair<int,pair<int,int>>> s;

 

queue 는 선입선출의 원칙을 가지고 있는데, 먼저 들어온 요소가 가장 앞에 배치되어 있어 다음 호출때 가장 먼저 나가는 것을 의미한다.

여기서 (int, (int, int)) = (횟수 ,  ( y , x) ) 를 의미한다.

 

졸라맨의 다음번 방문할 방향은 다음과 같은 배열 2가지로 조절한다.

int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };

 

dx는 x와 합쳐져 다음 x 위치를 표시하고,  dy는 y와 합쳐져 다음 y 의 위치를 나타낼 수 있다.

 

주어진 맵과 방문 여부를 표시할 배열은 N의 최대값이 100이므로 그것보다 살짝 크게 설정하여 에러를 방지한다.

 

int map[101][101];
bool visited[101][101];

 

BFS 는 다음과 같이 선언한다.

여기선 위에 설명한 것처럼 과거 방문 여부만 체크하고 queue 에 넣느냐 넣지 않느냐를 결정한다.

만약 visited[ny][nx] =1 을 하지 않고 바로 s.push 를 수행한다면, 같은 위치에 같은 시간에 도착하는 큐들이 전부 들어가므로 메모리 초과가 뜰 수 있으므로 주의한다.

위 그림에서 졸라맨끼리 만나는 상황을 의미한다.

 

int BFS(int n, int m) {
	
	while (!s.empty()) {
		int x = s.front().second.second; 
		int y = s.front().second.first; 
		int cnt = s.front().first;
		visited[y][x] = 1;
		s.pop();
		if (x == m && y == n) {
			return cnt;
		}
		for (int i = 0; i < 4; i++) {
			int ny = dy[i] + y;
			int nx = dx[i] + x;
			if (ny <= n && ny > 0 && nx <= m && nx > 0 && map[ny][nx] && !visited[ny][nx]) {
				visited[ny][nx] = 1;
				s.push(make_pair(cnt + 1, make_pair(ny, nx)));
			}
		}
	}
	return 0;


}

 

---

메인함수는 다음과 같다.

int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf("%1d", &map[i][j]);
		}
	}
	s.push(make_pair(1,make_pair(1, 1)));
	cout << BFS(n, m);


}

메인함수에서는 숫자를 한자리씩 입력받는 것과 처음 출발지점을 queue 에 넣어주는 것만을 수행한다.

그후 BFS 함수로 넘어가 전부 수행하고 난 후 도착했을 때의 숫자를 return 하는 것을 받아 출력한다.

여기서 BFS함수가 반드시 도착지점에 도착한다는 조건이 있었으므로 가능한 함수이다.

 

만약 도착할 수 없는 경우가 있었다면 BFS수행결과를 배열에 따로 저장해 얼마나 걸렸는지 기록하는 것이 편하다.

그렇지 않으면 따로 생각해야할 필요가 있으니 (물론 그대로 짜도 문제는 없다.) 횟수를 적어놓는 것을 추천한다.

 

전체코드

#include <iostream>
#include <queue>


using namespace std;

queue<pair<int,pair<int,int>>> s;

int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };


int map[101][101];
bool visited[101][101];
int BFS(int n, int m) {
	
	while (!s.empty()) {
		int x = s.front().second.second; 
		int y = s.front().second.first; 
		int cnt = s.front().first;
		visited[y][x] = 1;
		s.pop();
		if (x == m && y == n) {
			return cnt;
		}
		for (int i = 0; i < 4; i++) {
			int ny = dy[i] + y;
			int nx = dx[i] + x;
			if (ny <= n && ny > 0 && nx <= m && nx > 0 && map[ny][nx] && !visited[ny][nx]) {
				visited[ny][nx] = 1;
				s.push(make_pair(cnt + 1, make_pair(ny, nx)));
			}
		}
	}
	return 0;


}

int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf_s("%1d", &map[i][j]);
		}
	}
	s.push(make_pair(1,make_pair(1, 1)));
	cout << BFS(n, m);


}