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는 깊이가 같은 노드들 끼리 같이 탐색하기 때문에 깊이를 단계적으로 늘려갈 수 있기 때문이다.
하지만 가장 먼 노드의 깊이를 반환하는게 아니라 가장 먼 노드들의 개수를 반환해야 되기때문에 추가적으로 필요한 정보들이 더 있었다.
-
우선 기본적으로 bfs 구현에 필요한 것들부터 구현한다.
간선에 대한 정보가 양방향이 아니라 단방향으로 문제에서 제시되었기 때문에 인접배열이나 인접리스트로 추가적으로 구현해야했다. 이 문제의 경우 같은 깊이의 노드들은 한 회차에 같이 순회하는 것이 좋기 때문에 인접 노드들끼리 순회하기 편한 인접리스트로 구현했다.
그 외 방문 체크용 boolean 배열과 간선으로 저장하는 메서드도 구현했다. -
깊이 정보를 담을 자료구조가 필요했다.
큐에 담을 때 노드 번호와 같이 저장하면 좋을 것 같아서, int,int 쌍으로 된 자료구조가 뭐가 있을까 생각 하다가 그냥 Comb라고 조합에 대한 클래스를 새로 만들고 생성자와 게터만 추가했다. -
같은 깊이의 노드가 몇 개가 있는지 알아야 한다.
이 부분을 구현하기 위해 key를 깊이, value를 해당 깊이의 노드 개수로 하는 hashMap을 만들어서 구현했다. 뭔가 이 부분은 굳이 해시맵까지 써야하나? 싶긴하다. 다음에 리팩토링을 진행해본다면 없에보고 싶긴하다. 다른 방법이 있긴 할듯.. -
++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인 배열을 써도 되는 것 같다.
다음에 이렇게 리팩토링 한번 진행해보자.
