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

문제

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

---

문제 요약

M × N 크기의 격자로 표현되는 섬유 물질이 있다.

 

각 격자는 0이라면 전류가 잘 통하고, 1이라면 전류가 통하지 않는다.

 

위쪽을 바깥쪽, 아래쪽을 안쪽이라고 생각했을 때, 바깥쪽에서 흘려 준 전류가 안쪽까지 침투될 수 있는지를 출력한다.

---

코드

#include <iostream>
#include <string>

#define MAX 1000

using namespace std;

int n, m;

char board[MAX][MAX];
bool check[MAX][MAX];

bool flag = false;

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

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

	for (int d = 0; d < 4; d++) {
		int nx = x + dx[d];
		int ny = y + dy[d];

		// 이미 탐색했거나, 범위를 벗어났거나, 전류가 통하지 않는 격자라면
		if (check[nx][ny] || nx < 0 || nx >= n || ny < 0 || ny >= m || board[nx][ny] == '1') continue;

		// 안쪽까지 전류가 흐른다면
		if (nx == n - 1) {
			cout << "YES";
			exit(0);
		}

		dfs(nx, ny);
	}
}

int main() {
	cin >> n >> m;

	// 섬유 물질 정보 입력
	for (int i = 0; i < n; i++) {
		string str;
		cin >> str;

		for (int j = 0; j < m; j++) {
			board[i][j] = str[j];
		}
	}

	// 섬유 물질의 바깥쪽에서 DFS 탐색
	for (int i = 0; i < m; i++) {
		if (board[0][i] == '1') continue;
		dfs(0, i);
	}

	// DFS를 모두 진행했음에도 YES 출력과 함께 종료되지 않았다면, NO 출력
	cout << "NO";

	return 0;
}

---

코드 설명

1. 섬유 물질 정보를 2차원 배열에 저장한다.

 

2. 섬유 물질 바깥쪽(첫 줄)의 모든 격자에서 DFS 탐색을 진행한다.

 

3. 탐색 중, 안쪽(마지막 줄)을 방문한다면 "YES"를 출력하고 프로그램을 종료한다.

 

4. 모든 탐색이 끝났는데, 프로그램이 종료되지 않았다면 "NO"를 출력한다.