프로그래머스) 가장 먼 노드

문제 설명

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 노드의 개수 n은 2 이상 20,000 이하입니다.
• 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
• vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

입출력 예nvertexreturn

6

[[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]

3

입출력 예 설명

예제의 그래프를 표현하면 아래 그림과 같고, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다.

 

 

내가 프로그래머스 문제를 처음 풀어서 그런지는 모르겠지만, 문제 설명을 잘못읽어서 두시간 넘게 헤맴.  '간선에 대한 정보가 담긴 2차원 배열 vertex'라는 말과,  ' vertex배열 각 행 [a,b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다' 라는 두 말을 보고 나는 당연히 arr[a][b]!=0이면 a와 b를 잇는 간선이 존재한다는 의미로 해석하고 문제를 풀었는데, 알고보니깐 a와 b를 잇는 간선의 정보는 arr[?][0]=a, arr[?][1]=b로 arr[?]번째에 저장되어 있다... 뭔소린지 모르면 나도 계속 ArrayIndexOutOfBoundsException떠서 이게 뜰리가없는데 하고 찾다가 문제 이해가 잘못했단걸 깨달음

 

 풀이

어쨋든간에 그래프 탐색을 위해 DFS나 BFS를 사용해야 한다는 점은 쉽게 캐치할 수 있었다. 다만 모든 탐색 문제가 그렇듯이, 여러가지 조건을 탐색에 추가해주어야 하는데, 이 문제에서는

1)방문 여부를 표시하여 첫 탐색 알림

2)flag를 사용하여 모든 노드의 (최소)depth가 표시되었을때 종료

정도의 조건이 필요하다.

다만 추가로 방문 여부 검사를 처음에는 실제로 방문을 하고 queue에 add하기 전에만 했는데, 그러면 불필요한 반복 탐색이 일어나서 실행시간이 길어짐. 따라서 한번 방문한 노드는 또 방문할 필요가 없으므로 탐색 조건에 방문여부를 같이 검사해주면 됨.

 

1. 케이스 5,7,8 시간초과

for(int i=1; i<=n; i++) { //인접 노드 갱신이 필요하다면 갱신
	if(relative[node][i]==true) {
		if(!visited) {
			len[i] = len[node] + 1;
			visited[i] = true;
		}
		queue.add(i);
	}
}

2. 테스트 통과

for(int i=1; i<=n; i++) { //인접 노드 갱신이 필요하다면 갱신
	if(relative[node][i]==true && !visited[i]) {
		len[i] = len[node] + 1;
			visited[i] = true;
			queue.add(i);
	}
}

 

 

전체 코드

import java.util.*;

class Solution {
    public int solution(int n, int[][] edge) {

        int answer = 0;
        int[] len = new int[n+1]; //최종적으로 노드 0으로부터 최대길이를 저장
        boolean[] visited = new boolean[n+1];
        visited[1] = true;
        boolean[][] relative = new boolean[n+1][n+1];
        for(int i = 0; i < edge.length; i++) {
            int x = edge[i][0];
            int y = edge[i][1];
            
            relative[x][y] = true;
            relative[y][x] = true;
        }
       
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);

        while(!queue.isEmpty()) {
            boolean flag = true;
            int node = queue.remove();
            for(int i=1; i<=n; i++) { //인접 노드 갱신이 필요하다면 갱신
                if(relative[node][i]==true && !visited[i]) {
                    len[i] = len[node] + 1;
                    visited[i] = true;
                    queue.add(i);
                }
            }
            for(int i=1; i<=n; i++) {
                if(!visited[i]) //아직 모든 노드의 거리가 구해지지 않은 경우
                    flag = false;
            }
            if(flag) break; //모든 노드의 최소거리가 구해진 경우 break
        }

        //가장 멀리 떨어진 노드의 개수 구하기
        int m = -1;
        for(int i=1; i<=n; i++) {
            if(m<len[i])
                m = len[i];
        }
        for(int i=1; i<=n; i++) {
            if(len[i]==m)
                answer++;
        }

        return answer;
    }
}