프로그래머스 (Java) 388354 : 홀짝트리

https://school.programmers.co.kr/learn/courses/30/lessons/388354

프로그래머스

---

풀이

위의 문제에서 홀짝을 결정하는 자식의 수는 직접적으로 연결된 자식의 수만 확인한다.

트리의 모양을 바꿔가며 보면 어떤 노드가 루트 노드일 때는 연결된 모든 간선의 수가 자식의 수이고, 루트 노드가 아니라면 (연결된 간선의 수 - 1)가 자식의 개수이다.

 

처음에는 트리 모든 노드를 루트라 가정하고 순회하며 확인했으나 시간초과가 발생했다.

생각해보니 위치에 따라 자식의 수가 바뀌는 건 루트이냐 아니냐의 차이밖에 없었다.

그렇다면 해당 트리를 모두 루트가 아니라 가정했을 때 노드 하나를 제외한 모든 노드가 홀짝/역홀짝이라면 해당 노드를 루트로 지정했을 때 트리 전체가 홀짝/역홀짝이 된다.

 

따라서 트리 내부의 모든 노드를 확인하며 홀짝/역홀짝 노드의 개수를 구해 홀짝/역홀짝이 1개인 경우 해당 트리를 역홀짝/홀짝으로 구분하였다.

이 때 해당 트리가 홀짝 트리와 역홀짝 트리가 모두 될 수 있는 경우가 있다는 걸 주의해야 한다.

따라서 해당 구문을 if - else if가 아닌 if - if로 짜야한다.

 

---

Java 코드

import java.util.*;
class Solution {
    Set<Integer> set = new HashSet<>();
    Map<Integer, List<Integer>> graph;
    int forward = 0, reverse = 0;
    
    public int[] solution(int[] nodes, int[][] edges) {
        int[] answer = new int[]{0, 0};
        
        // 그래프 정보 생성
        graph = new HashMap<>();
        for (int node : nodes) {
            graph.put(node, new ArrayList<>());
        }
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }   

        // 노드 순회
        for (int node : nodes) {
            if (set.contains(node)) continue;
            
            forward = 0;
            reverse = 0;
            bfs(node);
            
            // 역홀짝/홀짝인게 1개만 있다면 해당 노드를 루트로 정해 역홀짝/홀짝 트리로 만들 수 있음
            if (forward == 1) {
                answer[1]++;
            }
            if (reverse == 1) {
                answer[0]++;
            }
        }
        return answer;
    }
    
    // 해당 그래프 순회
    private void bfs(int start) {
        Queue<Integer> q = new ArrayDeque<>();
        
        set.add(start);
        q.add(start);
        while (!q.isEmpty()) {
            int now = q.poll();
            
            // 해당 노드의 홀짝 확인
            int nowCnt = graph.get(now).size() - 1;
            if (now % 2 == 0) {
                if (nowCnt % 2 == 0) forward++;
                else reverse++;
            }
            else {
                if (nowCnt % 2 == 1) forward++;
                else reverse++;
            }
            
            List<Integer> kids = graph.get(now);
            for (int kid : kids) {
                if (set.contains(kid)) continue;
                set.add(kid);
                q.add(kid);
                
            }
        }
    }
}