Today I Learned

오늘은 점심시간에 코테 문제 하나를 풀었다. BFS 문제를 풀었는데 해당 내용을 정리해보려 한다.

가장 먼 노드 (BFS 문제)

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

• 문제
  양방향 가중치x 그래프에서 1번 노드에서 가장 먼 노드들의 개수를 반환하는 문제.
  노드의 개수 n, 간선의 정보가 담긴 2차원 배열 int[][] edge가 주어진다.

• 구현 과정
  가장 거리가 먼 노드의 개수를 찾는 것이기 때문에 dfs와 bfs중 bfs를 선택했다.
  bfs는 깊이가 같은 노드들 끼리 같이 탐색하기 때문에 깊이를 단계적으로 늘려갈 수 있기 때문이다.
  하지만 가장 먼 노드의 깊이를 반환하는게 아니라 가장 먼 노드들의 개수를 반환해야 되기때문에 추가적으로 필요한 정보들이 더 있었다.

1. 우선 기본적으로 bfs 구현에 필요한 것들부터 구현한다.
   간선에 대한 정보가 양방향이 아니라 단방향으로 문제에서 제시되었기 때문에 인접배열이나 인접리스트로 추가적으로 구현해야했다. 이 문제의 경우 같은 깊이의 노드들은 한 회차에 같이 순회하는 것이 좋기 때문에 인접 노드들끼리 순회하기 편한 인접리스트로 구현했다.
   그 외 방문 체크용 boolean 배열과 간선으로 저장하는 메서드도 구현했다.

2. 깊이 정보를 담을 자료구조가 필요했다.
   큐에 담을 때 노드 번호와 같이 저장하면 좋을 것 같아서, int,int 쌍으로 된 자료구조가 뭐가 있을까 생각 하다가 그냥 Comb라고 조합에 대한 클래스를 새로 만들고 생성자와 게터만 추가했다.

3. 같은 깊이의 노드가 몇 개가 있는지 알아야 한다.
   이 부분을 구현하기 위해 key를 깊이, value를 해당 깊이의 노드 개수로 하는 hashMap을 만들어서 구현했다. 뭔가 이 부분은 굳이 해시맵까지 써야하나? 싶긴하다. 다음에 리팩토링을 진행해본다면 없에보고 싶긴하다. 다른 방법이 있긴 할듯..

4. ++tmpD / tmpD++ / tmpD + 1
   이전 노드의 깊이에서 1씩 증가시켜야 했는데 습관적으로 tmpD++을 했다가 실패했다. 생각해보니 증감연산자를 뒤에 붙이면 실행한 뒤에 1씩 늘어나니까 앞에 붙여야하나? 싶어서 앞에다 붙여봤는데도 실패했다. 더 생각해보니 증감연산자를 쓸 경우 tmpD 자체가 1씩 늘어나니까 쓰면 안됐다. 그래서 +1로 수정

• 최종 코드

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든 굳이 상관없을 것 같긴하다.
  HashMap까지 안 써도 해결이 될 것 같긴하다. 새로 클래스를 만들어서 큐에 넣은 것도 마음엔 들지 않는다. 큐에 넣을때 마다 new로 객체를 찍어내야 하니까..
  -> 해시맵 말고 그냥 maxDepth로 변수 만들어서 현재 depth랑 비교하는 방식으로 하면 될듯?
  그리고 comb 새 객체보다 그냥 size 2인 배열을 써도 되는 것 같다.
  다음에 이렇게 리팩토링 한번 진행해보자.