[백준] 1707번 이분 그래프 JAVA (자바) 풀이

문제 1707

 

• 그래프의 정점의 집합을 둘로 분할
• 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할
• 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph)
• 이 그래프가 이분 그래프인지 아닌지 판별해라

이분그래프란?

• 모든 정점을 두가지 색으로 표현
• 인접한 정점을 연결할 때에는 무조건 다른 색상의 것을 연결

 

(예시)

https://pangtrue.tistory.com/m/98?category=695894

 

 

[입력]

 :  첫째 줄에 테스트 케이스의 개수 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()
get명령어는 해당 번지의 값을 가져오는 명령어 get(i) 로 인덱스 안 데이터 출력 가능	add명령어는 해당 배열안에 값을 넣는 명령어  list.add()명령어를 쓰면 objec t명령어를 넣어줘야 한다

 

 [코드]

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 처리하고 종료 
    }

 

 

이제 풀어보러 갈께요 :)

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *

1707번: 이분 그래프