백준/ Gold 4 문제 , 백준 파이썬 1707 , 이분 그래프 [BFS]

백준/ Gold 4 문제 , 백준 파이썬 1707 , 이분 그래프 [BFS]

 

풀이 시간

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
이 문제를 통해서 이분그래프에 대해 좀 더 알게 되었음.
처음에 색변경을 어떤식으로 해야할지 감이 안왔는데 -1 을 곱하면 쉽게 된다는 것을 알았다.
앞으로 요긴하게 써먹을 방법

 

 

문제 출처

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

1707번: 이분 그래프

 

풀이

 

 

1. BFS

 

호출된 i 번을 dq에 넣어준 뒤 색깔을 1로 설정한다.

 

이제 이 i번의 그래프에서 연결된 곳들을 반대 색깔로 할당해주고 만약 이미 같은 색으로 할당이 되어있다면 그 그래프는 이분 그래프가 될 수 없으므로 False를 리턴 시킨다.

 

이어져 있는 그래프는 dq를 통해 색을 반대로 계속 바꿔가면서 할당하며 확인한다.

 

 

 

2. 입력 받기 및 처리 & BFS 호출 및 처리

 

그래프를 무방향 그래프로 입력 받은 뒤 

 

색깔이 설정 안되어있는 번호대로 BFS 를 호출하여 할당해 나간다.

 

이때 False를 한 번이라도 리턴 받을시 이분 그래프가 될 수 없는 그래프이므로 NO를 출력한 뒤에 for 문을 빠져나온다.

 

 

 

정답