백번 열번 백번 열번

1707

• 백준(BOJ) 1707번 이분 그래프

  알고리즘 풀이/백준(Boj) 2019. 8. 17. 16:29

  문제 : https://www.acmicpc.net/problem/1707 문제그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오. 나의 풀이: 이분 그래프가 되려면 DFS를 했을 시 현재 노드가 0 이라면 인접한 노드들은 1이여야 한다. 따라서 biGraph 배열을 추가로 하나 만들어서 한 노드의 인접한 노드들은 1 - (현재노드의 Bi값) 로 정의해줌으로써 현재 노드의 biGraph 값이 0 이라면 인접한 노드들은1을 1이라면 0을 반환하도록 해 주자 기존 DFS와 동일..

  Read More