[백준/C++] 13565 침투

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

코드

#include <iostream>
using namespace std;

#define MAX 1001
#define FASTIO ios::sync_with_stdio(false); cin.tie(NULL);

int m, n, arr[MAX][MAX];
int dx[4] = { 1, -1, 0, 0 }, dy[4] = { 0, 0, 1, -1 };
bool visit[MAX][MAX];

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

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

        if (nx >= 0 && nx < m && ny >= 0 && ny < n) { 
            if (!visit[nx][ny] && arr[nx][ny] == 0) { 
                dfs(nx, ny);
            }
        }
    }
}

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

    for (int i = 0; i < n; i++)
        if (arr[0][i] == 0 && !visit[0][i])
            dfs(0, i);

    for (int i = 0; i < n; i++) {
        if (visit[m - 1][i]) {
            cout << "YES";
            return 0;
        }
    }

    cout << "NO";
    return 0;
}

설명

첫 번째 줄에서 출발했을 때 마지막 줄에 도달할 수 있는지를 확인하면 됩니다. 이를 위해 첫 번재 줄 내에서 방문하지 않았고, 값이 0인 좌표마다 dfs를 돌려줍니다. 

 

마지막 줄에 대해서 방문 여부를 확인하고 방문한 좌표가 있을 경우에 YES를, 아니면 NO를 출력하면 됩니다.

느낀 점

dfs를 이용해 풀이했습니다.