백준 1733 등번호

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

1733번: 등번호

백준 13361 최고인 대장장이 토르비욘을 풀었던 기억이 나서, 초기 접근 자체는 쉬웠다. 해당 문제는https://koosaga.com/166에 잘 정리되어있다. 

RUN@KAIST 7/6 방학 연습 풀이

 

 

먼저, 티셔츠의 안쪽 숫자와 바깥쪽 숫자를 간선으로 잇는다. 이제 그래프에서 각각의 간선에 대해 하나씩 정점을 중복 없이 할당해 주어야 하는 문제가 된다. 그렇게 얻어진 그래프의 각 컴포넌트를 생각해보자. 

 

일단, 간선 개수 > 정점 개수 라면 중복 없이 할당하는게 불가능하다. 그러면 남는 경우의 수는 2가지인데, 

 

간선 개수 = 정점 개수 - 1 인 트리 컴포넌트가 나오거나, 간선 개수 = 정점 개수인 사이클이 하나에 트리가 뻗어나오는 그래프가 있겠다. 여기서 관찰을 하나 할 수 있는데, 트리에서의 리프 노드, 즉 이어진 간선이 1개인 정점은 무조건 그 이어진 간선에 해당 정점을 할당해주는 식으로 컴포넌트의 크기를 줄여나갈 수 있다. 정점 개수와 간선 개수가 모두 1씩 감소하기에, 이렇게 해도 여전히 문제 해결이 가능한 컴포넌트가 남는다. 

 

이 컴포넌트의 크기를 줄여나가는 과정은 위상정렬의 아이디어를 빌릴 것이다. 이어진 간선이 1개인 점들을 다 큐에 넣고, 하나하나 pop하면서 그 정점을 제거했을 때 새로 생기는 간선이 1개인 점들을 추가해 주자. 더 이상 큐에 값이 남지 않을 때까지 돌려주면, 트리 컴포넌트의 간선들에는 정점 할당이 끝날 것이고, 간선 개수 = 정점 개수인 컴포넌트에는 사이클 하나가 남을 것이다. 

 

https://6epsilon.tistory.com/10

백준 10265 MT

위상정렬 과정만 보면 이 문제와도 비슷하다. 

 

남은 사이클에서는 DFS같은 방법으로 한 바퀴를 돌면서 간선과 정점을 매칭해주면 된다. 각각의 간선들에 전부 시계방향의 정점을 할당하거나, 전부 반시계방향의 정점을 할당할 방법이 있으면 된다.

 

사실, 토르비욘 생각나자마자 유니언파인드로 코드를 짜다가, 위의 문제를 해결하는 코드를 짜면 결국 필요없어진다는걸 깨달았다. 불가능 판별도 해결하는 과정에서 확인할 수 있었다. 마지막에 남는게 하나의 사이클인지만 확인해주면 되기 때문.