백준 13565 - 침투(C++)

문제 링크입니다. https://www.acmicpc.net/problem/13565

13565번: 침투

BFS를 이용해 푸는 문제입니다.

1번째 열에서 N번째 열까지 갈 수 있는지를 물어보는 문제입니다.

 

먼저 1번째 열에서 전기가 통하는 곳을 찾습니다.

전기가 통하는 곳을 찾았다면 해당 부분에서 4방향 탐색을 시작합니다.

4방향 탐색 중에서 N번째 열에 도착했다면? -> 탐색을 종료하고 YES를 출력합니다.

탐색이 끝나고도 N번째 열에 도착하지 못했다면? -> 다시 1번째 열에서 전기가 통하는 곳을 찾습니다.

 

1번째 열에서 전기가 통하는 곳이 모두 N번째 열을 가지 못한다면? -> NO를 출력합니다.

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>

using namespace std;

int N, M;
int map[1001][1001];
int check[1001][1001];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

bool bfs(int X, int Y) {
	queue<pair<int, int >> q;
	q.push({ X,Y });
	check[X][Y] = 1;
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		if (x == N) return true;
		for (int i = 0; i < 4; i++) {
			int xx = x + dx[i];
			int yy = y + dy[i];
			if (xx >= 1 && xx <= N && yy >= 1 && yy <= M) {
				if (check[xx][yy] == 0 && map[xx][yy] == 0) {
					q.push({ xx,yy });
					check[xx][yy] = 1;
				}
			}
		}
	}
	return false;
}

void solve() {
	for (int i = 1; i <= M; i++) {
		if (map[1][i] == 0) {
			if (bfs(1, i)) {
				cout << "YES";
				return;
			}
			memset(check, 0, sizeof(check));
		}
	}
	cout << "NO";
}

int main() {
	cin.tie();
	cout.tie();
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			scanf("%01d", &map[i][j]);
		}
	}
	solve();
	return 0;
}

 

 

자세한 것은 코드를 참고해주세요