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

 

 

문제 2178번

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

2178번: 미로 탐색

 

흑흑... 또 까먹었다...

이것도 예전에 풀었던 건데...

다시 그걸로 공부하고 작성해 보았다.

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

using namespace std;

int map[100][100];
int n, m, k;
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};

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

			if (nx < 0 || ny < 0 || nx >= n || ny >= m) {
				continue;
			}	
			if (map[nx][ny] == 0) {
				continue;
			}
			if (map[nx][ny] == 1) {
				map[nx][ny] = map[x][y] + 1;
				q.push({ nx,ny });
			}
		}
	}
	return map[n - 1][m - 1];
}

int main(void) {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%1d", &k);
			map[i][j] = k;
		}
	}
	cout << bfs(0, 0) << endl;
}

 

 

 

이제는 잊어버리지 말자...

계속계속 생각날 때마다 풀어봐야겠어...