[백준] 2178번: 미로 탐색 [C++]

 

알고리즘 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색

문제 링크: https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

 

 

 

【 풀이 】

 

모든 인접 정점을 방문해야하는 문제라면 DFS와 BFS 둘 다 사용해도 무방하다.

이 문제는 최단 거리를 구해야하기 때문에 BFS 가 적합하다. (모든 가중치가 1이기에, BFS 로 구하면 최단 거리가 된다.)

 

즉 한칸 움직일 때마다 목적지 까지의 거리가 +1 씩 더해지는 것이다.

 

 

【 코드 】

#include<iostream>
#include<queue>
#define MAX 101
using namespace std;

// 현재 위치 구조체
struct Pos { int y, x; };

// 나아갈 방향
Pos front[4] = {
	Pos {-1,0},	// UP
	Pos {0,-1},	// LEFT
	Pos {+1,0},	// DOWN
	Pos {0,+1},	// RIGHT
};

int N, M;				// 미로 크기
bool discovered[MAX][MAX];		// 위치 발견(방문) 여부
char miro[MAX][MAX];			// 미로
int dist[MAX][MAX];			// 목적지 까지의 거리
queue<Pos>q;					

void Bfs(int y,int x) {
	// 현재 위치
	Pos pos;
	pos.y = y;
	pos.x = x;

	discovered[y][x] = true;
	q.push(pos);
	dist[y][x] = 1;

	while (q.empty() == false) {
    	// 현재 위치
		pos = q.front();
		q.pop();

		if (pos.y == N && pos.x == M)
			break;
		
		for (int dir = 0; dir < 4; dir++) {
        	// 다음에 가야할 위치
			Pos nextPos;
			nextPos.y = pos.y + front[dir].y;
			nextPos.x = pos.x + front[dir].x;
			
            		// 다음에 가야할 위치가           	
			if (nextPos.y < 1 || nextPos.x < 1)	// 1. 미로 범위 안에 있는지
				continue;
			if (nextPos.y > N || nextPos.x > M)	
				continue;
			if (miro[nextPos.y][nextPos.x] == 48)	// 2. '1'에 해당하는지(나아갈 수 있는지)
				continue;
			if (discovered[nextPos.y][nextPos.x])	// 3. 이미 발견(방문)했던 곳인지 체크한다.
				continue;

			discovered[nextPos.y][nextPos.x] = true;
			q.push(nextPos);
            
          	 	 // 전에 있었던 정점에서 +1 씩 더해진다.
			dist[nextPos.y][nextPos.x] = dist[pos.y][pos.x] + 1;
		}
	}
}

int main() {
	cin >> N >> M;

	for (int y = 1; y <= N; y++)
		for (int x = 1; x <= M; x++)
			cin >> miro[y][x];

	Bfs(1, 1);
	cout << dist[N][M];
	
	return 0;
}