[백준] 1707번 : 이분 그래프

1707번: 이분 그래프

# 문제

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

# 입력

입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 E(1≤E≤200,000)가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호가 빈 칸을 사이에 두고 주어진다.

# 출력

K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.

# 예제 입력 1

2

3 2

1 3

2 3

4 4

1 2

2 3

3 4

4 2

# 예제 출력 1

YES

NO

# 알고리즘 분류

• 그래프 탐색
• 그래프 이론
• BFS
• DFS

---

BFS 혹은 DFS를 이용해도 되는 것 같다. 필자는 DFS를 이용해서 해결하였다. 우선 이분 그래프가 무엇인지 모른 상태에서 해결하려고 하여 조금 막막하였으나 생각보다 그리 어렵지 않은 이론이었다. 이분 그래프란 간단히 말하자면

 

각 정점을 Red와 Blue의 집합으로 나눈다. 모든 간선들은 반드시 Red와 Blue 정점을 이어야 한다. 간선 기준 양쪽에 동일한 색을 가진 정점이 있으면 그것은 이분 그래프가 아니다.

 

위 그림처럼 Red정점은 다른 Red정점과 인접하지 않아야하고, Blue정점은 다른 Blue 정점과 인접하지 않아야한다.

 

우선 정점을 Class로서 만들었다.

static Class Vertex
{
    int index; // n번 째 정점
    int state = 0; //초기값 : 0, 추후 1 또는 -1을 부여받게 됨
    List<Integer> list = new ArrayList<>(); //인접리스트
    
    public Vertex(int index){
    	this.index = index;
    }
}    

각 정점은 어디로 연결되는지, 자신이 몇 번째 정점인지, 자신의 색깔이 Red(1)인지 Blue(-1)인지 정보를 갖는다.

다음은 DFS 함수와 정답을 결정 짓는 전역변수 bipartite이다.

static boolean bipartite; //이분 그래프의 조건에 적합하지 않으면 false

static void DFS(int start){

  //start번 째 정점 방문
  visit[start] = true;
  //System.out.println(start+" 방문 & state: " + vertices[start].state);

  //start번째 정점의 인접리스트 순회
  vertices[start].list.stream().forEach(i->{
    
    //방문하지 않음 & 색깔을 갖지 않았다면
    if(!visit[i] && vertices[i].state == 0){
      vertices[i].state = vertices[start].state * (-1); //start번 째 정점과 다른 색
      DFS(i);
    }
    //인접리스트에 연결된 다른 정점이 나와 같은 색깔이라면
    //이분 그래프가 아님
    else if(vertices[i].state == vertices[start].state)
      bipartite = false;
  });
}

 

bipartitie의 값에 따라 답이 "YES" or "NO"로 결정된다. 모든 정점을 방문할 때 까지 bipartite가 true를 유지하면 이분 그래프라는 뜻이다.

 

추가)

1 ㅡ 2

ㅣ

3     4

 

같은 그래프도 이분 그래프이다.

 

# Whole Code </>

public class Main {

    static class Vertex{
        int index; //1~v
        int state = 0;//-1, 0, 1
        List<Integer> list = new ArrayList<>();

        public Vertex(int index){
            this.index=index;
        }
    }
    static Vertex[] vertices;
    static boolean[] visit;
    static boolean bipartite; //이분 그래프의 조건에 적합하지 않으면 false

    static void DFS(int start){

        visit[start] = true;
        //System.out.println(start+" 방문 & state: " + vertices[start].state);

        vertices[start].list.stream().forEach(i->{
        
            if(!visit[i] && vertices[i].state == 0){
                vertices[i].state = vertices[start].state * (-1);
                DFS(i);
            }
            
            else if(vertices[i].state == vertices[start].state)
                bipartite = false;
        });
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

        int k = Integer.parseInt(br.readLine()); //test case 개수

        for(int i=0; i<k; i++){
            bipartite = true;
            st = new StringTokenizer(br.readLine());
            int v = Integer.parseInt(st.nextToken()); //정점 개수
            int e = Integer.parseInt(st.nextToken()); //간선 개수

            visit = new boolean[v+1]; //1~v
            vertices = new Vertex[v+1];

            for(int j=1; j<=v; j++)
                vertices[j] = new Vertex(j);

            for(int j=1; j<=e; j++){
                st = new StringTokenizer(br.readLine());
                int left = Integer.parseInt(st.nextToken());
                int right = Integer.parseInt(st.nextToken());

                vertices[left].list.add(right);
                vertices[right].list.add(left);
            }
            vertices[1].state = 1;
            DFS(1);

            for(int j=1; j<=v; j++)
                if(!visit[j]) {
                    vertices[j].state = 1;
                    DFS(j);
                }

            if(bipartite) System.out.println("YES");
            else System.out.println("NO");
        }
    }
}