백준 13565 침투 c++ (dfs)

문제 출처 : https://www.acmicpc.net/problem/13565

13565번: 침투

문제

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

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

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

입력

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

출력

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

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

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

풀이

간단한 그래프 탐색 문제이다.

dfs 혹은 bfs로 풀 수 있는데 본인은 dfs로 풀었다.

문제는 전류가 바깥에서 첫 행(바깥쪽)으로 들어와, 마지막 행(안쪽)을 통해 바깥쪽으로 나갈 수 있는지를 찾으면 된다.

입력이 5,6으로 주어지면 m은 5 n은 6이다. (본인은 n=5, m=6으로 입력받았다.)

전류가 0 행에서 시작해서, 5행으로 갈 수 있다면 YES를 출력하면 끝!

따라서 dfs는 0행의 모든 열에서 아직 방문하지 않은, 전류가 통하는 '0'으로 이루어진 칸에 대해 dfs를 시작해야 한다.

visited 배열은 따로 만들 필요 없고, 0으로 이루어진 칸(전류가 통하는 길)을 방문했다면 2로 바꾸어주면 된다.

 

코드

#include <iostream>
#include <string>
#define MAX 1000
using namespace std;

//2<=n<=1000
int n, m;
string graph[MAX];
bool canFinish = false;
int dirXY[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
void dfs(int r, int c) {
	graph[r][c] = '2';
	for (int dir = 0; dir < 4; dir++) {
		int nr = r + dirXY[dir][0];
		int nc = c + dirXY[dir][1];
		if(nr==n){
			canFinish = true;
			return;
		}
		if (nr < 0 || nc >= m || nc < 0) continue;
		if (graph[nr][nc] != '0') continue;
		dfs(nr, nc);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		cin >> graph[i];
	}
	
	for (int c = 0; c < m; c++) {
		if (graph[0][c] == '0') {
			dfs(0, c);
			if (canFinish == true) {
				cout << "YES";
				return 0;
			}
		}
	}

	cout << "NO";
	return 0;
}