[BOJ 백준] 13565번 침투

문제

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

13565번: 침투

접근

석교수가 만든 섬유가 outer side부터 inner side까지 전류가 침투할 수 있는지 알아보는 문제이다.

전류가 통하는 격자는 0으로 통하지 않는 격자는 1로 나타낸다.

따라서 outer side와 닿는 부분인 0번째 격자들을 시작으로 dfs를 돌아 inner side와 닿는 n - 1번째 격자까지 도달할 수 있는지를 알아보면 답을 찾을 수 있다.

이때 방문을 체크하는 visit는 dfs를 새로 시작할 때마다 초기화해주지 않아도 된다. 이미 방문한 격자라는 뜻은 그 격자를 통해 출구까지 갈 수 없음을 의미하니까.

또한 대체로 arr[n][m]의 형태로 주어지는 데 반해 이 문제는 arr[m][n]으로 주어졌다. 습관적으로 m과 n을 바꿔쓰는 경우가 많다. 이 부분을 실수하지 않도록 유의하자.

코드

// algorithm study
// BOJ_13565_침투

#include <iostream>
#include <vector>

using namespace std;

int m, n, visit[1010][1010] = {0}, chk = 0;
char arr[1010][1010];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

void dfs(int x, int y) {
    visit[x][y] = 1;
    if (x == m - 1) {
        chk = 1;
        return;
    }
    for (int i = 0; i < 4; i++) {
        int newx = x + dx[i];
        int newy = y + dy[i];
        if (newx < 0 || newx >= m || newy < 0 || newy >= n || visit[newx][newy] == 1 || arr[newx][newy] == '1')
            continue;
        dfs(newx, newy);
        if (chk == 1)
            return;
    }
}

int main() {
    cin >> m >> n;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> arr[i][j];
        }
    }

    for (int i = 0; i < n; i++) {
        if (arr[0][i] == '0' && visit[0][i] == 0) {
            dfs(0, i);
            if (chk == 1) {
                cout << "YES";
                return 0;
            }
        }
    }
    cout << "NO";
    return 0;
}

 

깃 허브 주소 : https://github.com/algoribi/algorithm-study