[코드트리 챌린지] 2주차 DFS - DFS / 두 방향 탈출 가능 여부 판별하기

https://www.codetree.ai/missions/2/problems/determine-escapableness-with-2-ways/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

코드:

#include <bits/stdc++.h>
using namespace std;

int n, m;
int arr[105][105]; 
int visited[105][105]; // 방문 판단
int dx[2] = { 1,0 }; // 아래, 우측 순 탐색
int dy[2] = { 0,1 };

// 배열 범위 내 인지 판단
bool InRange(int nx, int ny) {
    return (0 <= nx && nx < n && 0 <= ny && ny < m);
}

// 갈 수 있는지 판단
bool Cango(int nx, int ny) {
    if (!InRange(nx, ny)) return false;
    // 뱀이 존재하는 경우
    if (arr[nx][ny] == 0) return false;
    if (visited[nx][ny]) return false;

    return true;
}

void DFS(int x, int y) {
    // 아래 우측 순으로 탐색함
    for (int i = 0; i < 2; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        // 갈 수 있는 경우 true, dfs
        if (Cango(nx, ny)) {
            visited[nx][ny] = true;
            DFS(nx, ny);
        }
    }
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

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

    visited[0][0] = true;
    // (0,0)에서 dfs 시작
    DFS(0, 0);

    // 끝에 도달할 수 있는지 판단
    if (visited[n - 1][m - 1])
        cout << 1;
    else
        cout << 0;

}

(0,0)에서 DFS를 시작하도록 합니다.

dx,dy 배열을 통해 아래, 우측 순으로 탐색을 진행하도록 합니다.

Cango()함수를 통해 배열 내 존재, 뱀이 존재하지 않음, 방문한 적 없음 위 세가지를 만족할 경우
visited[nx][ny]를 true로 만들고 갈 수 있는 방향을 통해 DFS를 재귀적으로 진행합니다.

모든 DFS를 진행한 이후 visited[n-1][m-1] 즉 우측 하단을 방문했는지 확인하면 탈출구가 있음을
판단할 수 있으므로 그에따라 출력을 달리하도록 합니다.