-
https://www.acmicpc.net/problem/1707
https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%201707
해당 문제는 간선수와 정점의 연결 정보가 주어졌을 때
이분 그래프인지 아닌지를 구하는 문제다.
위의 그래프 모양이 이분 그래픈데
예를 들어 왼쪽 파란색 점에서 시작했다면 해당 파란색 점을 기준으로
다음으로 갈 수 있는 점들은 모두 빨간색이어야 하고
빨간색에서 갈 수 있는 점은 모두 파란색이어야 한다
즉 내가 방문할 수 있는 정점이 만약 자기와 색이 같다면 해당 그래프는 이분 그래프가 아니다.
간선의 정보를 ArrayList를 배열로 사용하여 저장하였다
list[1] 번째 배열에는 1과 연결된 모든 정점을 저장하고
2 , 3 ... 간선 수만큼 반복하면서 저장한 다음 bfs를 해준다.
이때 모든 간선에 대해서 bfs를 돌려주며 조건으로 방문하지 않았을 때만 bfs 하도록 하였다.
bfs는 일반 bfs 돌리듯이 돌려주었으며, 처음 q에 넣은 값의 방문 체크 배열에는 1이라는 값을 넣어주고
해당 값을 통해서 갈 수 있고 방문하지 않은 값들은 이전 값 +1 즉 짝수 -> 홀수 -> 짝수 이런 순으로
값이 들어가도록 하고 q에 넣어주었고
만약 해당 값이 이미 방문했다면 이전 값과 방문할 수 있는 값에 대해서 둘 다 짝수인지
홀수인지를 구분해서 같으면 ans에 -1을 주고 리턴하는 식으로 해서
문제를 출력하였다.
728x90'알고리즘 > Baekjoon' 카테고리의 다른 글
Baekjoon 17244 아맞다우산 JAVA (0) 2021.11.13 Baekjoon 1194 달이 차오른다, 가자. JAVA (0) 2021.11.13 Baekjoon 4485 녹색 옷 입은 애가 젤다지? JAVA (0) 2021.11.13 Baekjoon 12738 가장 긴 증가하는 부분 수열 3 JAVA (0) 2021.11.13 Baekjoon 1755 숫자놀이 JAVA (0) 2021.11.13 댓글