[백준] 1707번 이분 그래프 JAVA (자바) 풀이
문제 1707
- 그래프의 정점의 집합을 둘로 분할
- 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할
- 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph)
- 이 그래프가 이분 그래프인지 아닌지 판별해라
이분그래프란?
- 모든 정점을 두가지 색으로 표현
- 인접한 정점을 연결할 때에는 무조건 다른 색상의 것을 연결
(예시)
[입력]
: 첫째 줄에 테스트 케이스의 개수 K
: 각 테스트 케이스, 첫째 줄에는 정점의 개수 V와 간선의 개수 E (공백으로 구분)
(각 정점 = 1 ~ V까지 차례로 번호 부여)
: 각 테스트 케이스, 둘째 줄부터 연결된 정점 u, v
2
3 2
1 3
2 3
4 4
1 2
2 3
3 4
4 2
→ 테스트 케이스 2개
→ 1번 케이스) 정점 3개 / 간선은 2개
→ 정점 = 1, 2, 3
→ 간선 => 1 - 3 연결 / 2 - 3 연결
[출력]
: 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력
YES
NO
[문제접근]
- 모든 정점에게 서로 다른 색깔을 부여
→ color = 1 / -1 로 서로 다르게 구분
→ color = 0 은 아직 색 미정 (초기엔 모두 0이다)
- arraylist로 연결된 노드 모두 입력
→ 예) 1 - 2 / 2 - 3 연결이라면
connect[1] = 2
connect [2] = 1, 3
connect [3] = 2 - 색깔이 같은 경우 이분그래프가 아님을 알 수 있으므로 빠른 종료를 위해 bfs로 진행
→ 초기 색은 0
→ 입력 들어온 색은 1로 지정
→ 색이 같다면 바로 NO 출력
→ 색이 다르고 아직 색 미정이라면 *-1해서 색 반대로 바꿔주기 - bfs를 true / false 로 구분하기 위해 boolean 타입 사용
[참고]
| Array | ArrayList | |
| 사이즈 | 초기화시 고정 int[] arr = new int[3]; |
초기화시 사이즈를 표시하지 않음. 크기가 가변적임 ArrayList<Integer> arrList = new ArrayList<>(); |
| 속도 | 초기화시 메모리에 할당되어 ArrayList보다 속도가 빠름 |
데이터 추가 삭제시 메모리를 재할당하기 때문에 속도가 Array보다 느림 |
| 크기 변경 | 사이즈 변경 불가 | 추가, 삭제 가능 add(), remove() |
| 다차원 | int[][][] multiArr = new int[3][3][3]; | 불가능 |
| ArrayList | |
| get() | add() |
|
|
[코드]
import java.io.*;
import java.util.*;
public class Main{
static int K, V, E, u, v;
static int color[];
static ArrayList<ArrayList<Integer>> connect;
static String answer;
public static void main(String[] args)throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
K = Integer.parseInt(br.readLine());
for(int i =0; i<K;i++){
answer ="YES";
st = new StringTokenizer(br.readLine());
V = Integer.parseInt(st.nextToken());
E = Integer.parseInt(st.nextToken());
connect = new ArrayList<>();
for(int j=0; j<=V; j++){
connect.add(new ArrayList<>()); //초기화
}
for(int j =0; j< E; j++){
st = new StringTokenizer(br.readLine());
u = Integer.parseInt(st.nextToken());
v = Integer.parseInt(st.nextToken());
connect.get(u).add(v);
connect.get(v).add(u);
}
color = new int[V+1];
for(int j =1; j<=V; j++){
if(color[j]==0){
if(!bfs(j))
break;
}
}
System.out.println(answer);
}
}
public static boolean bfs(int node){
Queue<Integer> q = new LinkedList<>();
q.add(node);
color[node] =1;
while(!q.isEmpty()){
int now = q.poll();
for(Integer i: connect.get(now)){
if(color[now]==color[i]){
answer="NO";
return false;
}
if(color[i]==0){
color[i]=color[now]*-1;
q.add(i);
}
}
}
return true;
}
}
[해설]
: static int K, V, E, u, v;
static int color[]; 컬러 -1 / 0 / 1 로 구분
static ArrayList<ArrayList<Integer>> connect; 노드 연결 표시
static String answer; 결과 출력
: K = Integer.parseInt(br.readLine()); 테스트 케이스 수
: for(int i =0; i<K;i++){
answer ="YES"; 기본 YES 출력
st = new StringTokenizer(br.readLine());
V = Integer.parseInt(st.nextToken()); 정점 개수
E = Integer.parseInt(st.nextToken()); 간선 개수
connect = new ArrayList<>(); 연결관계 관련 배열 생성
for(int j=0; j<=V; j++){ 정점 수랑 연결관계 인덱스 똑같이 맞춰주기 위해서 V포함
connect.add(new ArrayList<>()); 케이스 마다 초기화
}
for(int j =0; j< E; j++){
st = new StringTokenizer(br.readLine());
u = Integer.parseInt(st.nextToken()); 연결 노드 A
v = Integer.parseInt(st.nextToken()); 연결 노드 B
connect.get(u).add(v); u 인덱스에 v 값 추가
connect.get(v).add(u); v 인덱스에 u 값 추가
}
color = new int[V+1]; 컬러 초기화
for(int j =1; j<=V; j++){
if(color[j]==0){ 컬러가 0이면서 bfs false면 바로 종료
if(!bfs(j))
break;
}
}
System.out.println(answer); 답변 출력
}
: public static boolean bfs(int node){ 노드 입력받으면 바로 큐에 추가하고 색 1로 지정
Queue<Integer> q = new LinkedList<>();
q.add(node);
color[node] =1;
while(!q.isEmpty()){ 큐가 빌 때까지 실행
int now = q.poll(); 큐에서 하나씩 빼서 보기
for(Integer i: connect.get(now)){ 현재 노드랑 연결된 다른 노드 가져와 비교
if(color[now]==color[i]){ 연결된 노드끼리 색깔 같으면 NO 출력하고 bfs false 처리하고 종료
answer="NO";
return false;
}
if(color[i]==0){ 연결된 다른 노드의 색이 0이면
color[i]=color[now]*-1; 현재 노드 색이랑 반대로 만들어주기
q.add(i); 비교된 정점 큐에 추가
}
}
}
return true; 큐 비었고 색이 같지도 않고 그렇다고 0도 아니라면 bfs true 처리하고 종료
}
이제 풀어보러 갈께요 :)
* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *