[백준] 13565 침투 c++

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

13565번: 침투

 

풀이과정

문제를 잘 읽어야한다. 위쪽을 바깥쪽, 아래쪽을 안쪽이라고 생각한다.  
0이면 전류가 잘 통하는 흰색이고, 1이면 전류가 통하지 않는 검은색 격자이다.

01이 붙어서 입력되므로 scanf("%1d")를 사용해서 입력 받아준다.  
첫번째 줄이고, 전류가 통하는 0일 때 queue에 push를 해주며 방문 표시를 한다.  
bfs 과정에서는 전류가 통하지 않는 1일 때와 방문 했을 때를 제외하고는 상하좌우로 방문을 해주며 전류가 통할 때의 자리를 2로 바꿔준다.  bfs가 끝나고 맨 마지막 줄에 전류가 통했다는 뜻인 2가 있다면 YES, 2가 없다면 바깥쪽에서 흘려준 전류가 안쪽까지 전달되지 않았다는 뜻이므로 NO를 출력해준다.

 

#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;

int M, N;
int num[1001][1001];
bool c[1001][1001];

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

queue <pair <int, int>> q;

void bfs() {
	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 < 1 || nx > M || ny < 1 || ny > N)
				continue;
			if (num[nx][ny] != 1 && !c[nx][ny]) {
				c[nx][ny] = 1;
				num[nx][ny] = 2;
				q.push({ nx, ny });
			}
		}
	}
}

int main() {
	cin >> M >> N;
	for (int i = 1; i <= M; i++) {
		for (int j = 1; j <= N; j++) {
			scanf("%1d", &num[i][j]);
			if (i == 1 && !num[i][j]) {
				q.push({ i, j });
				c[i][j] = 1;
			}
		}
	}
	bfs();

	bool ans = false;
	for (int i = 1; i <= N; i++) {
		if (num[M][i] == 2) ans = true;
	}
	if (ans) cout << "YES";
	else cout << "NO";
}