[BOJ] 13565번_침투_DFS (C++)

[문제]

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

전류가 침투할 수 있는 섬유 물질을 개발하고 있다. 이 섬유 물질은 2차원 M x N 격자로 표현될 수 있다. 편의상 섬유 물질의 위쪽을 바깥쪽, 아래쪽을 안쪽이라고 생각한다. 또한 각 격자는 검은색 아니면 흰색인데, 검은색은 전류를 차단하고 흰색은 전류가 통한다. 전류는 섬유 물질의 가장 바깥쪽 흰색 격자들에 공급되고, 이후에는 상하좌우로 인접한 흰색 격자들로 전달될 수 있다.

이 섬유 물질이 바깥쪽에서 흘려 준 전류가 안쪽까지 침투될 수 있는지 아닌지 판단하는 프로그램을 만드는 문제이다.

*0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않는 검은색 격자이다.

[사용 알고리즘]

DFS(깊이 우선 탐색)

[풀이 핵심]

• graph[0][0]부터 graph[0][M](바깥쪽)을 DFS로 탐색하며, N(안쪽)에 도착하면 탐색을 중지하고 "YES"를 출력하고, 모든 경우에서 안쪽에 도착하지 못하면 "NO"를 출력하면 된다.

[코드]

//boj13565번_침투_그래프

#include<iostream>

using namespace std;

char graph[1001][1001];
bool visited[1001][1001];

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

int N, M;

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

	for (int i = 0; i < 4; i++) {
		int next_x = x + dx[i];
		int next_y = y + dy[i];

		if (next_x == N) {
			cout << "YES";
			exit(0);
		}

		if (next_x >= 0 && next_x < N && next_y >= 0 && next_y < M && !visited[next_x][next_y] && graph[next_x][next_y] == '0') {
			DFS(next_x,next_y);
		}
	}
}

int main() {
	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> graph[i][j];
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (graph[0][j] == '0' && !visited[i][j]) {
				DFS(0, j);
			}
		}
	}

	cout << "NO";
	return 0;
}