백준 13565번. 침투

백준 13565번. 침투

1. 문제

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

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

예를 들어, Figure 1(a) 에서는 바깥쪽에서 공급된 전류가 안쪽까지 침투하지만, Figure 1(b)에서는 그렇지 못한다.

2. 입력

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

3. 출력

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

4. 풀이

• main()함수에서 첫 줄 중에서 전류가 흐르는 곳만 DFS를 시작했다.
• DFS가 다 끝나고 마지막 줄을 방문한 적 있으면 전류가 흐른 것이고 흔적이 없으면 전류가 흐른 적 없는 것이다.

5. 처음 코드와 달라진 점

• 문제는 금방 풀었는데 시간이 오래 걸린 게 두 개 있었다.
  1. 0과 1을 헷갈림
2. 숫자를 공백없이 받아서 int tmp에 한줄이 통채로 들어감
• 1번은 비교적 금방 알았는데 2번 때문에 노트북 뿌실 뻔했다.
• string으로 한 줄을 다 받고 하나씩 int로 바꿔서 집어 넣었다.

6. 코드

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

int n, m;
bool visited[1000][1000];
int circuit[1000][1000];
int dx[] = { 0,0,-1,1 };
int dy[] = { 1,-1,0,0 };

void dfs(int x, int y) {
	visited[x][y] = true;

	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
		if (!visited[nx][ny] && circuit[nx][ny] == 0) dfs(nx, ny);
	}
}

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> m >> n;
	for (int i = 0; i < m; i++) {
		string number;
		cin >> number;
		for (int j = 0; j < n; j++){
			circuit[i][j] = number[j] - '0';
		}
	}

	for (int i = 0; i < n; i++) {
		if (!visited[0][i] && circuit[0][i] == 0) dfs(0, i);
	}

	string answer = "NO";

	for (int i = 0; i < n; i++){
		if (visited[m - 1][i]) {
			answer = "YES";
			break;
		}
	}

	cout << answer << endl;
}