BOJ 10552 - DOM 링크
(2023.10.11 기준 S2)

문제

N명의 사람들이 TV를 보고 있다. TV에는 M개의 채널이 있는데, 사람들은 각각 가장 좋아하는 채널과 가장 싫어하는 채널 하나씩 가지고 있다.

만약에 TV에서 가장 싫어하는 채널이 나오고 있다면 그 사람은 가장 좋아하는 채널로 바꾼다고 한다. 바꾸려는 사람이 여러 명이라면 가장 어린 사람이 가장 좋아하는 채널로 바꾼다.

나이가 어린 순으로 가장 좋아하는 채널과 가장 싫어하는 채널이 주어질 때, 최소 채널 변경 횟수 출력

알고리즘

DFS

풀이

가장 싫어하는 채널이 나오면 가장 좋아하는 채널로 바꾼다. 즉, 가장 싫어하는 채널 -> 가장 좋아하는 채널인 간선이라는 뜻이다.

그러면 예제 3번을 그래프로 나타내보자.
위 그림처럼 된다.

처음엔 2번에서 3번으로 채널을 바꿀 것이다. 그러면 3번에선 어떻게 될까?
가장 나이가 어린 사람이 채널을 바꾸므로. 즉, 먼저 주어진 간선을 따라가므로 1번 채널로 바꾸게 된다.
그러니깐 각 정점에서 진출하는 유효 간선은 최대 하나라는 것이다. 그러니 각 정점마다 먼저 주어진 진출 간선 하나만 저장하면 된다. 그래서 인접 리스트를 쓰지 않아도 되고 배열 하나만 써도 그래프 표현이 가능하다.

그래프 표현이 끝나면 이제 시작 정점에서 DFS를 돌리자.
만약, 이미 방문한 정점으로 가게 된다면 -1, 더 이상 간선이 없어 DFS가 진행이 불가능하면 (방문 정점의 개수 - 1)을 출력하면 된다.

코드

• C++

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

const int MAXN = 100000;

int adj[MAXN];
bool visited[MAXN];

int dfs(int i){
    visited[i] = true;

    // i번 정점에서 나가는 간선이 없다면 채널 고정된 것이므로 0 반환
    if (!~adj[i]) return 0;

    // 이미 방문한 정점이면 사이클을 이루는 것이므로 -1 반환
    if (visited[adj[i]]) return -1;

    int result = dfs(adj[i]);
    if (~result) return result + 1; // 사이클을 이루지 않는 결과라면 +1을 해서 반환
    return result; // 사이클을 이루는 결과라면 -1 그대로 반환
}

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

    int N, M, P; cin >> N >> M >> P;

    fill(adj, adj + M, -1); // 가장 싫어하는 채널에서 가장 좋아하는 채널로 바꾼다.
    for (int _ = N, a, b; _; _--){
        cin >> a >> b;

        // 이미 더 어린 사람이 해당하는 채널에서 바꿀 채널을 정해놓았다면 continue
        if (~adj[--b]) continue;
        adj[b] = --a;
    }

    fill(visited, visited + M, false);
    int result = dfs(--P);

    cout << result;
}

• Python

import sys; input = sys.stdin.readline
sys.setrecursionlimit(100000)

def dfs(i):
    visited[i] = True

    if not ~adj[i]: # i번 정점에서 나가는 간선이 없다면 채널 고정된 것이므로 0 반환
        return 0

    if visited[adj[i]]: # 이미 방문한 정점이면 사이클을 이루는 것이므로 -1 반환
        return -1

    result = dfs(adj[i])
    if ~result: # 사이클을 이루지 않는 결과라면 +1을 해서 반환
        return result + 1
    return result # 사이클을 이루는 결과라면 -1 그대로 반환

N, M, P = map(int, input().split())
P -= 1

adj = [-1] * M # 가장 싫어하는 채널에서 가장 좋아하는 채널로 바꾼다.
for _ in range(N):
    a, b = map(int, input().split())
    a -= 1; b -= 1

    if ~adj[b]: # 이미 더 어린 사람이 해당하는 채널에서 바꿀 채널을 정해놓았다면 continue
        continue
    adj[b] = a

visited = [False] * M
result = dfs(P)

print(result)