Today I Learned

어제 풀었던 문제를 리팩토링을 거쳐 수정을 해봤다.

가장 먼 노드 리팩토링

TIL #143에 풀었던 문제를 리팩토링해봤다.

원래 코드

import java.util.*;

// 노드번호와 깊이를 같이 저장할 자료구조 생성
class Comb{
    private int n; // 노드 번호
    private int d; // 깊이
    
    public Comb(int n, int d){
        this.n = n;
        this.d = d;
    }
    
    public int getD(){
        return d;
    }
    public int getN(){
        return n;
    }
}

class Solution {
// 간선 정보 인접 리스트로 구현
    private static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    // 방문 여부 체크하는 boolean 배열
    private static boolean[] visited;
    
    // edge[]를 인접 리스트의 간선으로 저장하는 메서드
    private static void putEdge(int x, int y) {
        graph.get(x).add(y);
        graph.get(y).add(x);
    }
    
    // bfs로 탐색
    private static int bfs(int v){
    // 방문 체크
        visited[v] = true;
        
        // 큐에다가 comb로 저장
        Queue<Comb> q = new LinkedList<>();
        q.add(new Comb(v,0));
        
        // key가 깊이고 value가 해당 깊이의 노드 개수인 해시맵 생성 
        Map<Integer, Integer> map = new HashMap<>();
        // getOrDefalut로 있으면 get, 없으면 0을 반환하게 함
        int count = map.getOrDefault(0,0);
        // 1 더해서 키값에 넣음
        map.put(0, count+1);
        
        
        while(!q.isEmpty()){
            Comb tmp = q.poll();
            int tmpN = tmp.getN();
            int tmpD = tmp.getD();
            
            // tmpN번 노드와 간선으로 이어진 노드의 리스트 a
            ArrayList<Integer> a = graph.get(tmpN);
            for(int i=0; i<a.size(); i++){ 
                int index = a.get(i);
                if(!visited[index]){
                // 이전 노드보다 1만큼 깊이가 길어졌으므로 +1
                    int depth = tmpD+1;
                    q.add(new Comb(index, depth));
                    visited[index] = true;
                    // 해당 깊이에 대한 개수를 해시맵에 저장
                    int count2 = map.getOrDefault(depth, 0);
                    map.put(depth, count2+1);
                }
            }
        }
        // 해시맵에 저장된 키 값중 가장 큰 값 == 1에서 거리가 가장 먼 값 찾기
        Integer maxKey = Collections.max(map.keySet());
        // 해당 깊이의 노드 개수 반환
        return map.get(maxKey); 
    }
    
    public int solution(int n, int[][] edge) {
        // 0~n까지 graph에 각각의 ArrayList 생성
        for(int i = 0; i <= n; i++){
            graph.add(new ArrayList<Integer>());
        }
        
        // vertex로 그래프 간선 구현
        for(int[] e : edge){
            putEdge(e[0], e[1]);
        }
        // 방문기록용 boolean 배열
        visited = new boolean[n+1];
        
        int answer = bfs(1);
        return answer;
    }
}

발상

• bfs로 구현하긴 했지만 dfs를 써도 구현 자체는 가능할 것 같긴하다. 내 풀이처럼 해시맵으로 해당 깊이에 대한 노드의 개수를 저장한다면 어차피 순회를 다 해야하니 dfs든 bfs든 굳이 상관없을 것 같긴하다.
  하지만 이 케이스에선 bfs가 더 효율적이니 pass

• HashMap까지 안 써도 해결이 될 것 같긴하다. 새로 클래스를 만들어서 큐에 넣은 것도 마음엔 들지 않는다. 큐에 넣을때 마다 new로 객체를 찍어내야 하니까..

• 해시맵 말고 그냥 maxDepth로 변수 만들어서 현재 depth랑 비교하는 방식으로 하면 될듯?

• comb 새 객체보다 그냥 size 2인 배열을 써도 되는 것 같다.

개선

• HashMap 대신 maxDepth 변수를 선언해 이 변수와 tmpD를 비교해서 최대 깊이를 찾게 한다.

• comb가 불필요한 클래스로 느껴져 2차원 int[] 배열로 교체. new는 필연적으로 써야하지만 그래도 클래스를 임의로 생성하는 것 보다 가독성도 좋아지고 활용하기 좋아졌다.

• 불필요한 코드들 삭제하고 ArrayList<ArrayList<Integer>> 를 List<List<Integer>>로 바꿔 유연성을 높였다.

리팩토링 진행 후 코드

import java.util.*;

class Solution {
    private static List<List<Integer>> graph = new ArrayList<>();
    private static boolean[] visited;
    
    private static void putEdge(int x, int y) {
        graph.get(x).add(y);
        graph.get(y).add(x);
    }
    
    private static int bfs(int v){
        visited[v] = true;
        
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{v,0});
        int maxDepth = 0;
        int answer = 0;
        
        while(!q.isEmpty()){
            int[] tmp = q.poll();
            int tmpN = tmp[0];
            int tmpD = tmp[1];
            
            for(int index : graph.get(tmpN)){ 
                if(!visited[index]){
                    int depth = tmpD+1;
                    q.add(new int[]{index, depth});
                    visited[index] = true;
                    if(depth>maxDepth) {
                        answer = 1;
                        maxDepth = depth;
                    } else if(depth == maxDepth){
                        answer++;
                    }
                }
            }
        }
        return answer; 
    }
    
    public int solution(int n, int[][] edge) {
        // 0~n까지 graph에 각각의 ArrayList 생성
        for(int i = 0; i <= n; i++){
            graph.add(new ArrayList<Integer>());
        }
        
        // vertex로 그래프 간선 구현
        for(int[] e : edge){
            putEdge(e[0], e[1]);
        }
        // 방문기록용 boolean 배열
        visited = new boolean[n+1];
        
        int answer = bfs(1);
        return answer;
    }
}