dev-hunmin

www.acmicpc.net/problem/1298 1298번: 노트북의 주인을 찾아서 어느 날 모든 학생들은 한 명이 한개의 노트북을 가지고 공부하던 도중, 자리를 바꾸다가 그만 노트북이 뒤섞이고 말았다. 대다수의 학생들은 자신의 노트북을 잘 알고 있어서 자신의 노트북을 www.acmicpc.net - 접근법 각 노드들이 선호하는 방번호가 있고 최대한 많은 노드들을 각기 다른 방에 1개씩 넣는 법을 묻는 문제이다. 즉, 단순한 이분매칭으로 해결할 수 있다. 문제에서 주어진 노드들의 개수(N)도 100으로 여유있고 간선들의 개수(5000)도 여유있으므로 단순하고 빠른 DFS로 해결할 수 있다. 로직은 간단히 말하면, 탐색하는 노드가 선호하는 방 번호에 '비어'있다면 바로 매칭시켜주고 누가 점거하고 있다면..