[BFS]04-백준 2178 미로탐색

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

2178번: 미로 탐색

 

---

 

#include<iostream>
#include <queue>
using namespace std;

int N, M;						//N :행 개수, M : 열 개수
int arr[101][101];				//칸 정보
bool visit[101][101] = { 0, };	//방문 여부
int cnt = 1;					//최소의 칸 수
int xc[4] = { -1,1,0,0 };
int yc[4] = { 0,0,-1,1 };
bool MNcheck = false;			//도착 시 종료를 위한 bool변수
bool pluscheck =false;			//이동 수를 증가시키는 여부 조사 변수

queue<pair<int, int> > q;


int bfs() {

	//(1,1)에서 출발
	visit[0][0] = 1;			
	q.push(make_pair(0, 0));
	while (!q.empty()) {
		int sx = q.front().first;
		int sy = q.front().second;
		q.pop();

		//인접 칸 조사
		for (int i = 0; i < 4; i++) {
			//칸 크기 초과 여부
			if (sx + xc[i] < N && sx + xc[i] >= 0 && sy + yc[i] < M && sy + yc[i] >= 0) {

				//(M,N)에 도착했을 경우 
				if ((sx + xc[i] == N-1) && (sy + yc[i] == M-1)) {
					MNcheck == true;	//종료를 위한 bool변수
					pluscheck = true;	
					break;
				}
				else {
					//방문안했고 이동 가능한 칸이면
					if (arr[sx + xc[i]][sy + yc[i]] == 1 && visit[sx + xc[i]][sy + yc[i]] == 0) {
						visit[sx + xc[i]][sy + yc[i]] = 1;
						q.push(make_pair(sx + xc[i], sy + yc[i]));
						pluscheck = true;		
						// 4방면이 모두 갈 곳이 없을 경우에만 false
						// 인접 값이 존재하여 queue에 하나라도 push했다면 cnt 증가
					}
				}
			}if (MNcheck)break;		//도착 시 모든 loop를 빠져나간다.

		}

		if (!pluscheck) {
			//4방면이 모두 갈 곳이 없을 경우에만 감소
			cnt--;
		}
		else {
			cnt++;
			pluscheck = false;
		}

		if (MNcheck)break;
	}
	return cnt;
}

int main() {
	
	cin >> N >> M;		//칸수 입력
						/* 미로 데이터 입력 */
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				cin >> arr[i][j];		
			}
		}
		cout<<bfs();
		return 0;
}

 

---

 

문제를 읽고 매우 단순하다고 생각했는데 최소 칸 수를 파악하는데 애를 먹었다.

처음에는 인접 칸을 조사할 때 ↓, → 의 방향만 조사해야 하는지,  인접 칸이 이동할 수 없는 칸이거나 이미 방문한 칸일 때 cnt ( 최소 칸 수를 카운트하는 변수)를 감소해야하는지 매우 헷갈렸다. 그러나 아래와 같은 예시를 두고 BFS과정을 천천히 생각해보니 답을 찾을 수 있었다.

queue의 front 좌표 한번을 조사할 때마다 cnt를 감소 혹은 증가 시키는데, 인접한 칸이 이동 가능하여 queue에 삽입할 경우 ( queue에 삽입되는 그 인접 칸의 개수가 한개이든 두개이든 무관 , 아래 화살표 개수와 동일 ) 무조건 cnt 를 증감시키고, 반대로 조건에 만족하지 못하여 queue삽입을 안하는 경우 cnt를 감소시키면 된다.

마지막의 (N,M)칸에 도달하였을 경우에도 cnt를 증가시켜줘야하고 모든 반복문과 조건문에서 빠져나와 bfs과정을 마친다.

 

4 * 6 의 예시

이동 순서

(M,N)에 도달하기까지 Queue에 쌓이는 순서

 

즉 cnt의 O개수 - X개수 13 - 4 = 9 를 구할 수 있다.

출력 콘솔