[BOJ 23818] 백준 23818번 - 원수의 원수
1. 문제
$23818$. 원수의 원수 (2021 POSTECH Programming Open Contest F번)
2. 풀이
$a$와 $b$가 관련이 있는지 없는지를 확인하기 위해서 $a$와 $b$가 동일 그래프에 속하는지 즉, 각 노드가 어떤 그룹에 속해 있는지에 대한 정보가 필요하다. 또한, $a$와 $b$가 친구 관계인지 원수 관계인지 알기 위해 각 노드의 관계 정보가 필요하다.
각 노드가 어떤 그룹에 속하는지는 모든 edge를 저장하고 전체를 DFS로 탐색하여 알아낼 수 있다. 각 노드들의 관계는 친구 관계이면 이전 노드와 관계를 동일하게 맞추고, 원수 관계이면 이전 노드와 관계를 다르게 맞추면 된다.
문제는 사이클이 생겼을 때 발생한다. DFS를 타고 들어가다가 이전에 이미 방문했던 노드(이전 노드 제외)를 방문하게 되면, 해당 노드의 관계(친구인지 원수인지)와 실제 관계를 비교한다. 이것이 어긋나는 경우 지금 탐색하고 있는 그룹의 error_flag를 $1$로 만들면 된다. (코드 27~32줄)
3. 채점 결과
4. 회고
문제를 읽고 당연히 Union and Find 문제라고 생각하여 그쪽으로 접근해서 풀어보았는데 결국 성공시키지 못하고 방향을 틀 수밖에 없었다. 분리집합을 이용하는 방법을 발견한다면, 나중에 따로 공부해봐야겠다.
최대한 효율적으로 수행하기 위해서 그룹확인과 관계확인을 동시에 했고, error 판별을 재탐색해서 노드들에 error를 표시해주는 것이 아니라 그냥 해당 그룹의 error_flag를 확인하는 방식으로 구현하였다.
댓글남기기