[Algorithm/C++17] 백준 10552 DOM

문제

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

10552번: DOM

풀이 방법

싫어하는 채널을 좋아하는 채널로 변경하는 걸 하나의 간선으로 본다.

가장 어린 사람이 채널을 바꾸기 때문에, 이미 간선을 만들었으면 그 이후에는 더 만들지 않아도 된다.

그래프를 만들었으면 P부터 탐색을 시작한다.

1. 더 이상 탐색할 곳이 없으면 사람들을 모두 만족시킨 것이다.
2. 이미 방문한 곳을 또 탐색한다면 사이클이 발생한 것이다.
3. 탐색이 끝나면 탐색 횟수를 출력한다.

코드

#include <cstdio>
#include <vector>
using namespace std;
int dfs(vector<int> &graph, vector<bool> &visited, int idx)
{
	visited[idx] = true;
    int next = graph[idx];
    // 1. 더 이상 탐색할 곳이 없으면 탐색 종료.
    if(next == -1) return 0;
    // 2. 이미 방문한 곳을 또 탐색한다면 사이클이 발생한 것
    if(visited[next]) return -1;
  
    // 다음 노드 탐색
    int result = dfs(graph, visited, next);
    if(result == -1) return -1;
    // 3. 탐색이 끝났을 때 결과가 사이클이 아닐 경우 탐색 횟수를 반환
    else return result + 1;
}
int main()
{
    int N, M, start, a, b;
    scanf("%d %d %d", &N, &M, &start);
    vector<int> graph(M+1,-1);
    vector<bool> visited(M+1, false);
    for(int i=0; i<N; i++)
    {
        scanf("%d %d", &a, &b);
        if(graph[b] == -1) graph[b] = a;
    }
    int answer = dfs(graph, visited, start);
    printf("%d", answer);
    return 0;
}

고찰

어린 사람이 채널을 먼저 변경한다는 것을 잊고 간선을 입력이 들어오는 만큼 다 저장했다가 삽질했던 문제이다. 저장만 잘해주면 나머지는 노드를 탐색해서 이미 방문한 노드일 경우 사이클 판단, 아닐 경우 탐색 횟수를 출력하면 된다.