[C++][백준 2178][BFS DFS] 미로 탐색 - BFS :: seoftware

 문제 

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

2178번: 미로 탐색

 풀이 

• map은 0과 1로 입력을 받을 배열이다. 
• visited는 두 블록 사이를 계속 왔다갔다 하는 것을 막기 위해 갔던 블록은 다시 가지 않도록 하기 위한 배열이다.
• cnt는 (0,0)에서 각 좌표까지의 블록 개수를 기록하는 배열이다. cnt[N-1][M-1]이 답으로 출력된다.
• dx와 dy는 상하좌우를 살피기 위한 좌표 이동 값이다.
• bfs 함수는 (0,0)부터 cnt 배열을 채워주는 함수이다. BFS 알고리즘을 사용하였다. 특별한 점이 있다면 이동하기 직전의 cnt 값(xx,yy)에 +1을 해주며 큐에 새로운 좌표(nx, ny)를 넣어주는 것이다. 

 소스코드 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int N, M;
int map[100][100] = { 0 };
bool visited[100][100];
int cnt[100][100] = { 0 };

int dx[] = { 0, 1, 0, -1 };//12시부터 시계방향
int dy[] = { -1, 0, 1, 0 };

void bfs(int x, int y) {
	visited[x][y] = true;
	cnt[x][y]++;
	queue<pair<int, int>> q;
	q.push({ x, y });
	while (!q.empty()) {
		int xx = q.front().first;
		int yy = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = xx + dx[i];
			int ny = yy + dy[i];

			if (nx >= 0 && nx < N && ny >= 0 && ny < M && !visited[nx][ny] && map[nx][ny] == 1) {
				visited[nx][ny] = true;
				q.push({ nx, ny });
				cnt[nx][ny] = cnt[xx][yy]+1;
			}
		}
	}
}
int main(void) {
	cin >> N >> M;

	//입력
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%1d", &map[i][j]);
		}
	}

	//수행
	bfs(0, 0);

	//출력
	cout << cnt[N - 1][M - 1];
	
	return 0;
}