[백준] 13565 침투 c++

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

문제

인제대학교 생화학연구실에 재직중인 석교수는 전류가 침투(percolate) 할 수 있는 섬유 물질을 개발하고 있다. 이 섬유 물질은 2차원 M × N 격자로 표현될 수 있다. 편의상 2차원 격자의 위쪽을 바깥쪽(outer side), 아래쪽을 안쪽(inner side)라고 생각하기로 한다. 또한 각 격자는 검은색 아니면 흰색인데, 검은색은 전류를 차단하는 물질임을 뜻하고 흰색은 전류가 통할 수 있는 물질임을 뜻한다. 전류는 섬유 물질의 가장 바깥쪽 흰색 격자들에 공급되고, 이후에는 상하좌우로 인접한 흰색 격자들로 전달될 수 있다.

김 교수가 개발한 섬유 물질을 나타내는 정보가 2차원 격자 형태로 주어질 때, 바깥쪽에서 흘려 준 전류가 안쪽까지 침투될 수 있는지 아닌지를 판단하는 프로그램을 작성하시오.

입력

첫째 줄에는 격자의 크기를 나타내는 M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) 이 주어진다. M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않는 검은색 격자임을 뜻한다.

출력

바깥에서 흘려준 전류가 안쪽까지 잘 전달되면 YES를 출력한다.

그렇지 않으면 NO를 출력한다.

풀이 과정

문제를 잘 읽어야한다. 위쪽을 바깥쪽, 아래쪽을 안쪽이라고 생각한다.
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";
}