오늘의 학습 키워드

• 그래프 - 재귀로 구현
• DFS(O), 백트래킹(X)

[백준] Yes or yes - 25195

• [백준] Yes or yes - 25195
• Gold IV
• C++ 풀이
• 풀이시간: 54m

문제해설

주어진 그래프에서 특정 장애물이 있는 노드를 피해 루트 노드에서 말단 노드까지 도달하는 경로가 있는지를 판단하는 문제이다.
루트 노드 1번에서 시작하여 말단 노드로 가는 길에 장애물을 한 번도 만나지 않고 도달할 수 있다면 "Yes"를, 그렇지 않으면 "yes"를 출력한다.

접근법: 재귀

이 문제는 그래프로 시각화할 수 있으며, DFS를 재귀로 구현하여 경로를 탐색한다.

그래프로 표현하기

입력:

노드: 1, 2, 3, 4, 5, 6, 7
간선:
1 -> 2
2 -> 3
2 -> 4
3 -> 4
1 -> 5
5 -> 7
6 -> 7
장애물 노드: 3, 5

그래프 시각화

           1
          / \
         2   5 (장애물)
       /  \
  3(장애물)  4

출력

답: "Yes"

위와 같은 그래프에서, 장애물 노드를 피해 말단 노드에 도달할 수 있는지를 확인한다. 여기서는 1 -> 2 -> 4의 경로가 장애물을 만나지 않고 말단 노드에 도달할 수 있으므로 답은 "Yes"가 됩니다.

DFS 구현

• dfs(v) 함수에서 방문한 노드 v가 장애물이 있다면 false를 반환한다.

  if (fan[v] == true)

• (조건 t) 방문한 노드 v가 말단 노드라면 true를 반환하여, 최종적으로 dfs가 true를 반환한다.

  if (dfs(next)) return true;) // 조건 t

  최종적으로, dfs에서 true를 반환할 수 있는 유일한 방법이다.

• 연결된 자식 노드를 재귀적으로 탐색하여, 경로에 장애물이 없다면 그 경로를 따라 탐색을 계속한다.
• 탐색 결과 어떤 경로도 조건 t을 만족하지 못하면, 최종적으로 false를 반환한다.

// dfs 마지막까지 온다는 것은 조건이 만족하지 않는다는 것과 같은 말.
return false;

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

int N, M, S;
vector<int> graph[1000002];
int fan[1000002];
int vis[1000002];

bool dfs(int v){
    vis[v] = 1;
    if (fan[v]) return false;
    else if (graph[v].empty()) return true;
    for (int next : graph[v]){
        if (vis[next]) continue;
        if (dfs(next)) return true;
    }
    // vis[v] = 0;
    return false;
}

int main(){
    cin >> N >> M;
    for (int i = 0; i < M; i++){
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
    }
    cin >> S;
    for (int i = 0; i < S; i++){
        int s; cin >> s;
        fan[s] = 1;
    }
    if (!dfs(1)) cout << "Yes";
    else cout << "yes";
}

오늘의 회고

이 문제는 문제를 그래프 구조를 시각화하고, 재귀적으로 DFS를 구현하여 경로를 탐색하는 문제이다.
재귀적 사고가 부족하면 문제를 풀다가 오류를 범하기 쉬운데, 특히 구현 중 발생하는 논리적 오류를 수정하는데 시간이 걸릴 수 있다.
실제 코테에서 구현할 때는, 재귀 대신 while문을 통한 DFS 구현이 덜 직관적이지만 오류 발생 가능성을 줄일 수 있을 것이다.