[백준 BOJ] 1707_이분 그래프

기존의 백준 문제들과는 달리, 테스트케이스의 개수가 주어지다 보니 사용했던 벡터, 배열의 초기화가 필요했다.

코드에는 graph[j].clear()로 되어있지만, 처음에는 graph->clear()로 나와서 어떤게 문제인지 고민했다.

 

이분그래프란 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 2가지 색으로만 칠할 수 있는 그래프이다.

이분 그래프의 예시

 

 

[문제 해결 방법]

• color 배열을 만들어서 방문 정점, 정점과 이어진 정점의 숫자를 다르게 하여 설정하였다.(빨강 = 1, 파랑 = 2)
  
  • 초기화 : 0
  • 첫 정점 방문시 : 1
  • color가 1인 정점과 연결된 정점 : 2
  • color가 2인 정점과 연결된 정점 : 1
• 정점이 100개 이어져 있다고 해도, 1~4번 정점 사이에 이분그래프가 만들어지지 않으면 절대 이분그래프가 될 수 없으므로 flag를 확인하여 이분그래프가 아니면 DFS탐색을 더 하지 않았다.
  • color[현재정점] == color[이어진정점] 일 경우는 이분그래프가 아니므로 flag = false로
• 테스트 케이스의 개수가 주어지므로 graph, color, visited 배열 모두 초기화 필요
  • visited 배열의 초기화를 빼먹어서 틀렸었다
• flag가 true일 경우 YES를, false일 경우 NO를 ans 벡터에 넣는다

 

[좀 더 생각/공부 해볼 점]

• 다른 코드들을 보면 굳이 visit 배열을 안만들고 color 배열만 가지고 풀던데 visit 배열 없이 해결할 방법
• color 배열 말고, 구조체를 만들어 벡터에 넣어서 사용한다면??
• DFS를 완전히 혼자 할 수 있을때까지 연습..

여전히 DFS 구현을 하는게 헷갈린다 ㅠ

 

구현코드:

https://github.com/midaslmg94/Baekjoon/blob/master/1707_%EC%9D%B4%EB%B6%84%20%EA%B7%B8%EB%9E%98%ED%94%84.cpp