[C++] 백준 13565번: 침투

문제 링크

13565번: 침투

문제 요약

섬유 물질의 바깥쪽에서 흘려 준 전류가 안쪽까지 침투될 수 있는지 아닌지 판단하는 프로그램을 작성해야 한다. 섬유 물질은 격자로 이루어져 있는데, 격자의 색이 검은색이면 전류를 차단하는 물질이고, 흰색이면 전류가 통하는 물질이다.

접근 방법

간단한 그래프 탐색 문제였습니다. 위쪽 부분을 하나의 정점으로 보고, 아래쪽 부분을 하나의 정점으로 생각할 수 있습니다. 이때, 위쪽에서 그래프 탐색을 시작해서 아래쪽에 도달할 수 있는지만 판별하면 됩니다.

너비 우선 탐색을 구현하고, 초기 큐에는 맨 위쪽 열에서 값이 0인 격자들을 모두 넣어줍니다. 그리고 탐색을 하다가, 만약 가장 아래쪽 열에 속한 원소가 큐의 front에서 발견되면 YES를 출력하고 프로그램을 종료합니다.

만약 탐색이 끝날 때까지 도달하지 못했다면 NO를 출력하고 프로그램을 종료합니다.

코드

#include <bits/stdc++.h>

using namespace std;

const int MAX = 1001;
int dir[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
char b[MAX][MAX];
bool visited[MAX][MAX];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int m, n;
	cin >> m >> n;

	for (int i = 1; i <= m; i++)
		for (int j = 1; j <= n; j++)
			cin >> b[i][j];

	queue<pair<int, int>> q;
	for (int i = 1; i <= n; i++) {
		if (b[1][i] == '0') {
			q.push({ 1, i });
			visited[1][i] = true;
		}
	}

	while (!q.empty()) {
		auto now = q.front();
		q.pop();

		if (now.first == m) {
			cout << "YES\n";
			return 0;
		}

		for (int i = 0; i < 4; i++) {
			int nr = now.first + dir[i][0], nc = now.second + dir[i][1];

			if (nr >= 1 && nr <= m && nc >= 1 && nc <= n && b[nr][nc] == '0' && !visited[nr][nc]) {
				q.push({ nr, nc });
				visited[nr][nc] = true;
			}
		}
	}

	cout << "NO\n";
	return 0;
}