[BOJ/C++] 2178 미로 탐색 : BFS

문제

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

풀이

⭐전형적인 BFS 문제 | 최단 경로
⚠️2차원 배열 좌표: arr[행][열]로 생각하기 (x축, y축으로 생각하지 말기)

Queue만 pair 형태로 만들어주면 됨

코드

#include <iostream>
#include <queue>

using namespace std;

int N, M;
int map[100][100];
bool visited[100][100];
int cnt[100][100];

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

void bfs(int x, int y) {
	visited[x][y] = true;
	cnt[x][y]++; //시작 좌표 cnt 지정

	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() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%1d", &map[i][j]); //정수 1자리씩 입력 받기
		}
	}

	bfs(0, 0);
	cout << cnt[N - 1][M - 1];

	return 0;
}