[프로그래머스] 등대

 

프로그래머스

처음 풀때는 너무 복잡하게 생각해서 접근도 힘들었던 문제였다. 구글링을 해도 이해하기 쉬운 코드나 블로그가 보이지가 않았고 내 풀이가 조금 특이한 방법이라고 생각해서 공유하면 좋겠다는 생각에 포스팅을 해보았다.

import java.util.*;
import java.util.stream.Collectors;

class Solution {

    Map<Integer, PriorityQueue<Integer>> map = new HashMap<>();

    public void initMap(int[][] lighthouse) {
        for (int[] house : lighthouse) {
            map.computeIfAbsent(house[0], x -> new PriorityQueue<>()).add(house[1]);
            map.computeIfAbsent(house[1], x -> new PriorityQueue<>()).add(house[0]);
        }
    }

    int edgeCount = 0;
    int count = 0;

    public Integer getOnHouseFromLeaf(Integer leafHouse) {
        count++;
        return map.get(leafHouse).peek();
    }

    public void deletePath(Integer turnHouse) {
        for (Integer connectHouse : map.get(turnHouse)) {
            map.get(connectHouse).remove(turnHouse);
            edgeCount++;
        }
        map.get(turnHouse).clear();
    }

    public Collection<Integer> findLeafHouses(Collection<Integer> houses) {
        return houses.stream().filter(house -> map.get(house).size() == 1).collect(Collectors.toList());
    }

    public int solution(int n, int[][] lighthouse) {
        initMap(lighthouse);

        Queue<Integer> leafQueue = new LinkedList<>(findLeafHouses(map.keySet()));

        while (!leafQueue.isEmpty() && edgeCount < n - 1) {
            Integer leaf = leafQueue.poll();

            if (map.get(leaf).size() == 1) {
                Integer house = getOnHouseFromLeaf(leaf);
                List<Integer> leafCandidate = new ArrayList<>(map.get(house));
                deletePath(house);
                leafQueue.addAll(findLeafHouses(leafCandidate));
            }
        }

        return count;
    }
}
/*
1. 리프 등대를 찾는다.
2. 리프 등대와 연결된 등대를 킨다.
3. 킨 등대와 연결된 간선을 제거한다.
4. 제거된 간선 중에 방문하지 않은 등대에서 리프 등대를 찾는다.
5. 리프 등대가 없을 때까지 2의 과정부터 반복한다.
 */

문제를 접근할 때 등대와 연결된 간선을 기준으로 생각했다.

모든 간선에서 한쪽이라도 켜진 등대가 존재하면 문제의 조건에 부합하는 상태인 것이기에 간선을 보고 등대를 켜야하는지 판단하는 방향으로 로직을 짜야겠다고 생각했다.

 

하지만 간선만을 보면 최소한으로 등대를 키는 것을 어렵다.

최소한으로 등대를 켜기 위해서는 반드시 켜야하는 등대만 켜야한다.

이때 반드시 켜야하는 등대는 무엇일까? 그것은 리프 등대와 연결된 등대이다.

트리 자료구조에서 리프 노드와 같은 경우이다.

 

자신과 연결된 등대가 오직 부모 등대 밖에 없기 때문에 자신을 키거나 부모를 키거나 해야한다.

하지만 자신을 키는 것보다 부모를 키는 것이 부모와 연결된 다른 등대와의 연결을 할 수 있기 때문에 효율적이다.

 

연결된 간선을 기준으로 로직을 짜고 켜야하는 등대를 리프 등대와 연결된 부모 등대라는 것을 기초로 알고리즘을 생각했다. 그 결과 코드에 적힌 주석과 같은 과정을 지나면 원하는 답을 얻을 수 있을 것 같다는 생각을 했다.

 

그러나 실행 결과가 다른 사람들의 결과보다 조금 시간이 걸리는 것을 보면 효율성을 생각했을 때는 다른 방식이 좋겠다는 생각을 한다. 그래도 가독성 좋게 코드를 작성해서 다른 코드보다 이해하기 쉽고 구현하기도 좀 더 수월하지 않을까?