뒤죽박죽 코딩 이야기

2023년 01월 11일 수요일 - 오늘은 어려운 문제 푸는 날인가?

오늘 올려볼 문제는 1443번 Minimum Time to Collect All Apples in a Tree 이라는 문제이다.

사진을 클릭하면 해당 문제로 이동합니다.

오늘도 LeetCode 사이트 오늘의 문제를 가지고 왔다.

아니 이거 어려워!! 왜 미디엄이야!!!

입력

사진에서도 볼 수 있듯이 int 값 1개, 2차원 int 배열 1개, boolean 배열 1개가 입력으로 들어온다.

풀이 및 코드

0번 노드에서 출발하여 모든 사과를 따서 0번 노드로 다시 가져온다고 할 때 가장 적게 움직이는 길이가 무엇인지 구하는 문제이다.

오늘은 처음부터 정답을 생각해냈다.

조금 어려웠는데 dp를 어느정도 사용한 것 같다.

먼저 주어진 edges를 기준으로 hashmap에 트리를 구현한다.

이 후 사과가 열린 곳부터 0번 노드까지 dfs를 한다. 이 dfs를 하면서 길이를 잰다.

만약 0번 노드까지 가거나, 이전에 한 번 갔던 노드(이번 dfs에서 탐색한길 말고, 이전 dfs를 통해 사과를 따고 갔던 길)에 도착하면 해당 길이를 리턴한다. (이외는 음수 리턴)

(처음으로 이전에 한 번 갔던 노드가 결국에 다른 사과가 있던 곳과 가장 가까운 공통 조상이므로 해당 거리만 구하면 된다.)

음수가 아니라면 2배를 곱해서 result에 더한다.

이제 코드를 봐보자!

풀이코드

class Solution {
    boolean[] v;
    boolean[] visit;
    HashMap<Integer, ArrayList<Integer>> map;
    public int minTime(int n, int[][] edges, List<Boolean> hasApple) {
        map = new HashMap<>();
        v = new boolean[n];
        visit = new boolean[n];
        
        for(var e : edges) {
            if(!map.containsKey(e[0])) map.put(e[0], new ArrayList<>());
            if(!map.containsKey(e[1])) map.put(e[1], new ArrayList<>());
            
            map.get(e[0]).add(e[1]);
            map.get(e[1]).add(e[0]);
        }
        v[0] = true;
        
        int result = 0;
        
        for(int i = 0; i < n; i++) {
            var apple = hasApple.get(i);
            
            if(!apple) continue;
            
            int length = dfs(i, 0);
            v[i] = true;
            
            if(length > 0) result += length * 2;
        }
        
        return result;
    }
    
    public int dfs(int root, int length) {
        if(v[root]) return length;
        if(visit[root]) return -1;
        
        visit[root] = true;
        
        for(var child: map.get(root)) {
            var l = dfs(child, length + 1);
            if(l > 0) {
                v[child] = true;
                visit[root] = false;
                return l;
            }
        }
        
        visit[root] = false;
        
        return -1;
    }
}

제출 화면

어후 첨 봤을 때는 어떻게 풀어야하나 막막했는데 시작점을 0이 아닌 사과가 있는 곳부터하니까 수월하게 풀렸다.

또 오늘은 오랜만에 표준입출력 사용하는 문제도 풀어봤는데 2시간 넘게 풀면서 오랜만에 옛날 느낌도 나서 좋았다.

내일도 문제를 풀어서 블로그에 글을 쓸 수 있으면 좋겠다.