BOJ 25015번 - 아이싱

25015번: 아이싱

notorious coincidence 문제집에서 찾은 문제이다.

19862번과 동일한 문제인데 아쉽게도 19862번은 작성 일자 기준으로 레이팅을 주지 않는다.

하지만 루비 문제 치고 풀이가 간결하다기에 아래 블로그에서 풀이를 공부하고 풀어 보았다.

• https://dsstar.tistory.com/49
• https://justicehui.github.io/ps/2020/09/16/BOJ19862/

그런데 코드가 전혀 이해되지 않았다.

심지어 두 번째 블로그는 코드에 사소한 오류가 있는데 복붙 방지용인 듯 하다.

 

몇 시간 동안 생각해보아도 이해가 되지 않아서 다른 글을 찾아보았다.

다행히 코포 블로그에서 도움이 될 만한 글을 찾을 수 있었다.

• https://codeforces.com/blog/entry/68138

글의 제목은 "The DFS tree and its applications"이다.

dfs 트리에 대하여 이미 잘 알고 있다면 "Removing edges to form a bipartite graph" 문단만 읽어도 충분하다.

Observation 7 8에 코드를 접목하면 원리가 바로 보일 것이다.

 

결론은 dfs 트리 지식이 부족한 나의 잘못이었다.

풀이는 위의 두 블로그에서 자세히 설명하고 있어서 따로 남기지 않는다.

 

끝