[프로그래머스] 홀짝트리 (java) 그래프

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/388354?language=java

프로그래머스

 

풀이 방법

처음에는 모든 노드를 루투로 설정하고 싹 다 계산하려고 했다.

하지만 시간 복잡도가 10^6 * 10^6 으로 시간이 복잡도를 만족하지 못한다.

이에 다른 사람들의 풀이를 참고했다.

해당 문제의 특징을 파악하는 것이 매우 중요했다.

 

이 문제에서 가장 중요한 부분은 어떤 노드를 루트로 잡느냐였고, 해당 노드가 (루트 -> 루트 아님), (루트 아님 -> 루트) 일 때 이렇게 변경되는 노드만 (짝홀 트리, 역짝홀 트리)로 변경되는 것이 특징이었다.

즉 원래 짝홀 트리였다가 해당 노드가 루트가 되면 역짝홀 트리가 된다. 반대로 역짝홀트리였다가 해당 노드가 루트가 된다면 짝홀 트리가 된다.

 

이런 특징을 바탕으로 모든 노드가 짝홀 트리이거나 역짝홀 트리가 되려면, 모든 노드가 루트가 아니라고 가정하고 푼 이후에 단 한 노드만 짝홀 트리이거나 역짝홀 트리이면 해당 노드를 루트로 변경하게 된다면, 짝홀 트리 또는 역짝홀 트리가 된다.

 

이러한 특징을 이용해서 문제를 풀이할 수 있었다.

 

import java.util.*;
import java.io.*;

class Solution {
    
    public static HashMap<Integer, ArrayList<Integer>> graph = new HashMap<>();
    public static HashMap<Integer, Boolean> visited = new HashMap<>();
    public static int[] answer = {0, 0};
    
    public static void bfs(int node) {
        Queue<Integer> q = new LinkedList<>();
        int A = 0, B = 0; // 짝홀수 노드, 역짝홀수 노드
        q.add(node);
                
        while(!q.isEmpty()) {
            int cur = q.poll();
            ArrayList<Integer> edge = graph.get(cur);
            if ((cur % 2) != ((edge.size() + 1) % 2)) B++;
            else A++;
            
            for (int i = 0; i < edge.size();i++) {
                if (visited.get(edge.get(i)) == false) {
                    visited.put(edge.get(i), true);
                    q.add(edge.get(i));
                }
            }            
        }
        
        if (A == 1) {
            answer[1]++;
        }
        if (B == 1) {
            answer[0]++;
        }
        
    }
    public int[] solution(int[] nodes, int[][] edges) {        
        
        
        for (int i = 0;i < nodes.length;i++) {
            graph.put(nodes[i], new ArrayList<>());
            visited.put(nodes[i], false);
        }
        
        for (int i = 0;i < edges.length;i++) { // 그래프 만들기
            int a = edges[i][0];
            int b = edges[i][1];            
            graph.get(a).add(b);
            graph.get(b).add(a);
        }
        // 모든 노드가 루트가 아니라고 가정하고, 구하기
        
        for(int i = 0;i < nodes.length;i++) {
            if (visited.get(nodes[i]) == false) {
                visited.put(nodes[i], true);
                bfs(nodes[i]);
            }
        }
        return answer;
    }
}