[백준 13565] 침투

그냥 전형적인 BFS 문제

BFS는 재귀보단 내부적으로 queue 써서 돌리는게 더 직관적이다

 

시작점을 희소행렬로 저장해두고 미리 시작점들을 queue에 넣고 BFS 돌려주면 됨

 

---

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

#define SIZE 1001

using namespace std;

bitset<SIZE> map[SIZE];
bitset<SIZE> visited[SIZE];

vector<pair<int,int>> v;

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

int M, N;

void solve() {
	queue<pair<int, int>> q;

	// 시작점 모두 넣기
	for (int i = 0; i < v.size(); i++) {
		q.push(v[i]);
		visited[v[i].first][v[i].second] = 1;
	}

	bool isPossible = false;

	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();

		// 아래까지 도달했으면 종료
		if (y == M - 1) {
			isPossible = true;
			break;
		}

		for (int i = 0; i < 4; i++) {
			int newy = y + dy[i];
			int newx = x + dx[i];

			// 갈 수 없거나 이미 방문했으면 스킵
			if (newy < 0 || newx < 0 || newy >= M || newx >= N || visited[newy][newx]) continue;

			// 아직 방문하지 않은 갈 수 있는 곳이면 가보기
			if (map[newy][newx] == 0) {
				visited[newy][newx] = 1;
				q.push(make_pair(newy, newx));
			}
		}
	}

	if (isPossible) cout << "YES";
	else cout << "NO";
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> M >> N;

	char x;

	// 시작점들 저장
	for (int k = 0; k < N; k++) {
		cin >> x;
		map[0][k] = ((x == '0') ? 0 : 1);
		
		if (x == '0') v.push_back(make_pair(0,k));
	}

	for (int i = 1; i < M; i++) {
		for (int k = 0; k < N; k++) {
			cin >> x;
			map[i][k] = ((x == '0') ? 0 : 1);
		}
	}
		
	solve();

	return 0;
}