C++ 23일차 (1697, 1992, 2178)

오늘 공부한 백준 (1697, 1992, 2178)

 

2178

미로 탐색

#include <iostream>
#include <queue>
using namespace std;
string map[101];
bool vst[101][101];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int cnt = 0;

void bfs(int n, int m) {
	queue <pair <pair <int, int>, int>> que;
	que.push(make_pair(make_pair(0, 0), cnt));
    vst[0][0] = true;

	while (!que.empty()) {
		int cx = que.front().first.first;
		int cy = que.front().first.second;
		cnt = que.front().second;
		que.pop();

		if (cx == n - 1 && cy == m - 1) return;

		for (int i = 0; i < 4; i++) {
			int nx = cx + dx[i];
			int ny = cy + dy[i];
			if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			if (map[nx][ny] == '1' && !vst[nx][ny]) {
				vst[nx][ny] = true;
				que.push(make_pair(make_pair(nx, ny), cnt + 1));
			}
		}
	}
}

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

    for(int i = 0; i < N; i ++) {
        cin >> map[i];
    }
    bfs(N, M);
    cout << cnt + 1;
}