2018. 3. 5. 13:33, 알고리즘/BOJ
https://www.acmicpc.net/problem/15511
주어진 그래프를 이분그래프로 분할할 수 있는지를 묻고 있습니다. 그룹을 A, B라고 할 때 아직 그룹에 편입시키지 못한 임의의 노드에 대해 아래와 같은 작업을 반복합니다.
1) 택한 노드를 A에 편입
2) 그 노드로부터 BFS(혹은 DFS)를 돌면서 노드를 택함
3-1) 택한 노드가 이미 그룹에 편입되어있고, 부모 노드와 같은 그룹에 편입된 경우 불가능
3-2) 택한 노드가 이미 그룹에 편입되어있고, 부모 노드와 다른 그룹에 편입된 경우 일단 계속 진행
3-3) 택한 노드가 그룹에 편입되어있지 않을 경우 부모 노드와 다른 그룹에 편입시킴
이것을 그룹에 편입시키지 못한 노드가 없을 때 까지 반복합니다. 정상적으로 종료될 경우 주어진 그래프는 이분그래프로 분할 가능합니다.
'알고리즘 > BOJ' 카테고리의 다른 글
[BOJ] 1033번: 칵테일 (0) | 2018.03.11 |
---|---|
[BOJ] 6236번: 용돈 관리 (0) | 2018.03.07 |
[BOJ] 15515번: Tap Titanz at Moloco (0) | 2018.03.05 |
[BOJ] 15509번: Xayahh-Rakann at Moloco (0) | 2018.03.05 |
[BOJ] 15549, 15550번 (if, if 2) (0) | 2018.03.05 |
[BOJ] 1030번: 프렉탈 평면 (0) | 2018.02.20 |
Comments