99클럽 코테 스터디 11일차 TIL + DFS(C++)

문제

[백준] 25195번: Yes or yes

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

 

코드

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

vector<bool> visited(100001);
vector<int> graph[100001];
bool isPossible;
int N, M, u, v, S, s;

void dfs(int x) {
    visited[x] = true;

    // 더 이상 갈 곳이 없으면(끝까지 다다르면) 종료
    if (graph[x].size() == 0) {
        isPossible = true;
        return;
    }

    for (auto y : graph[x]) {
        if (!visited[y])
            dfs(y);
    }
}

int main() {
    cin >> N >> M;

    while (M--) {
        cin >> u >> v;
        graph[u].push_back(v);
    }

    cin >> S;

    while (S--) {
        cin >> s;

        // 시작점부터 팬클럽 곰곰이가 있는 경우
        if (s == 1) {
            cout << "Yes";
            return 0;
        }

        visited[s] = true;
    }

    dfs(1);

    cout << (isPossible ? "yes" : "Yes");

    return 0;
}

 

풀이

1번 정점부터 DFS를 실행해 방문할 수 없는 정점(팬클럽 곰곰이 노드)를 지나지 않고 마지막 정점까지까지 탐색 가능한지 판단하는 문제이다.

 

1. 팬클럽 곰곰이가 있는 노드인 s를 입력받을 때, s에 대해 visited[s] = true; 로 초기화해 s를 방문처리한다. (예외 처리 - 이때, 1번에 팬클럽 곰곰이가 존재한다면 탐색을 시작하자마 팬클럽 곰곰이를 만나게 되므로, 이런 경우 “Yes”를 출력하고 프로그램을 종료한다.)
2. 팬클럽 곰곰이 노드들을 입력받은 후, 1번 노드부터 DFS를 실행한다. 가장 깊은 노드까지 탐색할 수 있는지 검사해야 하므로 DFS를 사용한다.
3. 방문처리된 노드(팬클럽 곰곰이 노드)들을 건너뛰며 자식 노드들을 차례로 탐색해가다가, 현재 노드가 자식 노드가 없는 노드라면, 즉 더이상 탐색할 노드가 없다면 플래그 변수 isPossible을 true로 저장하고 DFS를 종료한다.
4. DFS 종료 후 isPossible 변수가 true라면 “yes”를, false라면 “Yes”를 출력한다.

 

느낀 점

DFS, BFS 문제 풀이시, 아래와 같이 그래프를 이루는 정점들을 인접리스트로 표현해보면 알고리즘을 코드로 짜기가 훨씬 쉬워지는 것 같다. (아래는 예제1에 대한 그래프를 인접리스트로 나타낸 것이다.)

1: 2, 5
2: 3, 4
3: 4
5: 7
6: 7