백준 1298 : 노트북의 주인을 찾아서

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

1298번: 노트북의 주인을 찾아서

 

해결 방법 : DFS 응용

• person ~ [1, N]에게 순차적으로 노트북을 배정한다.
• 만약 A가 점유하려는 노트북이 이미 배정되어 있다면, 해당 노트북을 받은 사람(owned[notebook])이 노트북을 양보 할 수 있는지를 DFS로 탐색한다. 
• 고려해야 할 점은, person1이 [1,2,3], person2가 [1,2], person3가 [1]을 원한다고 할 때, person3의 순서에서 person1은 notebook2를, person2는 notebook1을 가지고 있을 것이다. 이런 경우에 person1과 person2가 서로를 무한히 호출할 수 있다.
  • 각 순서(time)에 personX가 이미 호출되었는지를 판단하는 배열 visited를 사용하여, personX가 호출되면 해당 time을 viseted[X]에 갱신, 이후 visted[X]가 time이면 return해주었다.

 

import sys
input = sys.stdin.readline
from collections import defaultdict

def solution(N, G):
    owned = [0] * (N + 1) # index = notebook, value = person
    visited = [0] * (N + 1) # visted[x] = t means, person X가 t번째에 이미 호출되었음.
    
    def dfs(per, time):
        if visited[per] == time: return False # 이미 탐색
        visited[per] = time # time번째에 per 탐색

        for note in G[per]:
            if owned[note] == per: continue
            if owned[note] == 0 or dfs(owned[note], time): # notebook 배정 가능 or 양보 가능
                owned[note] = per
                return True

        return False # 원하는 노트북 배정 불가능

    answer = sum([dfs(p, p) for p in range(1, N + 1)]) # 원하는 노트북을 배정 받은 사람 수

    return answer

if __name__ == '__main__':
    N, M = map(int, input().split())
    G = defaultdict(list)
    for _ in range(M):
        per, note = map(int, input().split())
        G[per].append(note)
    result = solution(N, G)
    print(result)