BOJ 13565번: 침투

문제

입력

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

출력

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

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

---

문제 풀이 - 성공

0: 전류 통함 1: 전류 안 통함(방문함)

1. DFS로 연결된 모든 흰색을 방문한다
2. 깊이 우선 탐색을 반복하다 안쪽 격자에 방문하면 탐색을 멈추고 YES를 출력한다.

시간복잡도는 잘 모르겠음. 질문 해봐야지.

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

int n, m, ny, nx;
string map[1000];
bool flag = false;
int dy[] = { -1, 1, 0, 0 };
int dx[] = { 0, 0, -1, 1 }; // 상, 하, 좌, 우

void DFS(int y, int x) {
    map[y][x] = '1'; // 방문함
    if(y == m-1) { flag = true; return; } // 안쪽 격자 방문

    for (int i = 0; i < 4; i++) {
        ny = y + dy[i];
        nx = x + dx[i]; // 상하좌우

        if (ny < 0 || nx < 0 || ny >= m || nx >= n) { continue; }
        if (map[ny][nx] == '0') { DFS(ny, nx); }
    }
}

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

    cin >> m >> n;

    for (int i = 0; i < m; i++) { cin >> map[i]; } // 격자 입력받기

    for (int i = 0; i < n; i++) {
        if (map[0][i] == '0') {
            DFS(0, i);

            if (flag) { cout << "YES"; return 0; }
        }
    }
    
    if (flag) { cout << "YES"; }
    else { cout << "NO"; }

    return 0;
}

for문 안에 YES 출력문이 있으므로 아래에는 cout << "NO"; 만 써도 된다. 수정하는 도중에 빠트렸음.