Programmers 가장 먼 노드 - 그래프
https://school.programmers.co.kr/learn/courses/30/lessons/49189
문제 설명
n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.
노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.
제한사항
- 노드의 개수 n은 2 이상 20,000 이하입니다.
- 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
- vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.
예제
아래 그림과 같은 그래프의 경우, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드이고, 따라서 정답은 3이 된다.
잘못된 풀이
삽질
처음 이 문제를 보고 들었던 생각은, 인접행렬을 만들어서 일반적인 BFS로 풀려고 했다. 여기서, 떨어진 거리가 같은 노드들의 갯수를 체크해야 했고, 새로운 어레이리스트에 노드 각각의 위치를 저장하고 가장 먼 거리에 있는 노드들을 세는 식으로 구현하려고 했었다.
하지만, 이렇게 하니 메모리 초과의 문제에 부딪히게 되었고, 제한 사항에서 노드의 갯수가 너무 많아서 문제가 생기는 것 같았고, 다시 다른 방법을 찾게 되었다.
- 삽질 풀이 코드 (메모리 초과)
import java.util.*;
class Solution {
static int[][] map; // 인접행렬 (간선 정보)
static int ans; // 가장 먼 거리(최댓값) 저장
static boolean[] sel; // 방문 배열
static Queue<Pos> q;
static ArrayList<Integer> countArr; // 각 노드의 거리 저장
public static class Pos{ // cnt(거리) 저장하기 위해 Pos 클래스 생성
int idx;
int cnt;
Pos(int idx, int cnt) {
this.idx = idx;
this.cnt = cnt;
}
}
public int solution(int n, int[][] edge) {
int answer = 0;
map = new int[n+1][n+1]; // 인접행렬
sel = new boolean[n+1];
countArr = new ArrayList<>();
for(int i = 0; i < edge.length; i++) { // 인접행렬에 간선 정보 저장.
map[edge[i][0]][edge[i][1]] = 1;
map[edge[i][1]][edge[i][0]] = 1;
}
BFS(n+1); // BFS 실행
return countAns();
}
public static void BFS(int length) {
q = new LinkedList<>();
q.offer(new Pos(1, 1)); // 시작지점은 1과 cnt를 1로 넣어준다.
sel[1] = true; // 방문 한 노드인지 체크
while(!q.isEmpty()) {
Pos now = q.poll();
countArr.add(now.cnt); // 현재노드의 cnt값을 어레이리스트에 add.
ans = Math.max(ans, now.cnt); // 가장 먼 거리 cnt 저장
for(int i = 1; i < length; i++) {
if(map[now.idx][i] == 1 && !sel[i]) {
sel[i] = true;
int Cnt = now.cnt+1; // cnt를 더하고
Pos pos = new Pos(i, Cnt); // q에 추가
map[now.idx][i] = Cnt;
q.offer(pos);
}
}
}
}
public static int countAns() {
int count=0;
for(int i = 0; i < countArr.size(); i++) { //countArr을 돌면서
if(countArr.get(i)==ans) { // 가장 먼거리에 해당되는 노드를 count.
count++;
}
}
return count;
}
}- 위의 코드를 돌려보면 테스트케이스의 경우 통과한다. 테스트케이스에 대해서 countArr에 저장되는 정보를 출력해 보면 아래와 같다.
- 하지만 제출을 해보면 메모리 초과가 뜬다. 7번 케이스 또한 시간이 엄청 많이 걸리고, 잡아먹는 메모리도 많다는 것을 확인할 수 있었다. 아무래도 노드 갯수가 커질 수록 문제가 생기는 것 같았고, 또 countAns()라는 메서드를 실행하면서 결과적으로 계속 탐색을 해야하기 때문에도 시간도 오래걸리는 것 같았다.
풀이
간선정보를 인접행렬이 아닌 LinkedList 배열에 저장을 하기로 했다. 또, 따로 countArr라는 배열을 만들지 않고, Queue의 사이즈를 관리하면서 갯수를 세 주는 식으로 바꿨다.
주의
다만 주의해야할 점은 LinkedList배열의 경우 처음에 배열의 각각의 값이 null로 생성이 되기 때문에, 초기화를 해주어야한다는 것이다. 또한, 배열 각각이 LinkedList이기 때문에, for문을 통해 get()메서드를 수행해 가며 값을 찾기보다, foreach문을 사용하는 것이 좋다.
- 정답 코드
import java.util.*;
class Solution {
static LinkedList<Integer>[] map; // 간선 정보 저장
static int ans; // 결과값 저장
static boolean[] sel; // 방문 체크 배열
static Queue<Integer> q;
public int solution(int n, int[][] edge) {
map = new LinkedList[n+1]; // 간선 정보를 저장할 LinkedList배열 생성
sel = new boolean[n+1];
for(int i = 1; i < n+1; i++) { // LinkedList배열 초기화
map[i] = new LinkedList<>();
}
for(int i = 0; i < edge.length; i++) {
int idx1 = edge[i][0];
int idx2 = edge[i][1];
map[idx1].add(idx2); // LinkedList 해당 위치에 간선 add.
map[idx2].add(idx1); // LinkedList 해당 위치에 간선 add.
}
BFS(); // BFS탐색 시작
return ans;
}
public static void BFS() {
q = new LinkedList<>();
q.offer(1); // 1번부터 시작이기에 1을 넣어준다.
sel[1] = true; // 방문 체크
while(!q.isEmpty()) {
int size = q.size(); // q의 사이즈 관리를 해주면서.
ans = 0;
for(int i = 0; i < size; i++) { // size만큼 돌면서 확인.
int node = q.poll();
ans++; // 갯수 세기
for(Integer nextNode : map[node]) {
if(!sel[nextNode]) {
q.offer(nextNode);
sel[nextNode] = true;
}
}
}
}
}
}- 코드를 실행했을 때 BFS과정을 출력해보면 아래와 같다.
- 결과
느낀 점
-
문제를 잘읽자.. 제한사항 특히.
사실, 인접행렬로 탐색하는 것에 익숙해져서, 항상 간선과 노드가 주어지면 인접행렬을 만들어서 풀려고 해왔었다. 하지만, 갯수가 너무 많아지면, 확실히 많이 비효율적이라는 것을 느꼈고 LinkedList로 풀이하는 방식에 익숙해질 필요가 있다고 느꼈다. -
ArrayList나 LinkedList와 같은 리스트들은 get() 메서드로 탐색할 경우 보다 foreach 나 Iterator를 사용하는 것이 낫다.
LinkedList로 배열을 만들어서 풀이하는 것이 조금 까다롭긴 했지만, 그래도 어찌어찌 잘 푼 것 같다. 아직 갈길이 멀지만... 코딩테스트,, 잘 풀고 싶다 😭😭😭
