2022. 3. 19. 18:37ㆍ알고리즘/프로그래머스
문제 링크
https://programmers.co.kr/learn/courses/30/lessons/49189
풀이 과정
문제에 주어진 그림을 보자 마자 바로 그래프 자료구조로 접근했다.
https://born2bedeveloper.tistory.com/42
그래프를 구현방식을 모른다면 해당 포스트를 간단히 읽고 오도록 하자. (조회수좀..ㅎㅎ)
인접 리스트를 통해 주어진 그래프를 그림과 같이 구현한다.
문제가 요구하는 것은 "1"번 노드에서 가장 멀리 떨어진 노드의 개수를 구하는 것이다.
따라서 필자는 BFS를 이용하여 모든 노드를 방문하며, 각 노드와 노드 1 사이의 거리를 구할 것이다.
1. distance[n+1]을 선언한다 : 1번 노드와의 거리를 담는 배열
2. BFS : 1번 노드부터 시작해 주위 인접 노드를 방문한다.
3. 방문한 2, 3번 노드는 노드 1에서 1만큼 떨어져 있으므로 distance[2] = 3, distance[3] = 3이다.
이미 방문했으니 해당 노드는 visited[2] = true, visited[3] = true로 방문표시한다.
4. 2번 노드에서 인접한 5번 4번 노드를 탐색한다. 이들은 각각 1에서 2만큼 떨어져있다.
distance[5] = 2, distance[4] = 2로 설정하고 visited 표기
5. 3번 노드에서 인접한 6번 노드를 살펴본다 (4번노드는 이미 방문했으므로 재탐색 x)
distance[6] = 2로 설정한다.
6. distance를 오름차순으로 정렬한다. 가장 맨 끝값 (1과 가장 먼 노드의 거리)을 max로 두고 max와 같은 크기의 distance를 센다.
7. 센 개수를 answer로 반환한다.
코드 구현
import java.util.*;
class Solution {
public int solution(int n, int[][] edge) {
int answer = 0;
ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
int[] distance = new int[n + 1];
for (int i = 0; i < n + 1; i++)
graph.add(new ArrayList<>());
for (int i = 0; i < edge.length; i++) {
graph.get(edge[i][0]).add(edge[i][1]);
graph.get(edge[i][1]).add(edge[i][0]);
}
boolean[] visited = new boolean[n + 1];
visited[1] = true;
Queue<Integer> bfs = new LinkedList<>();
bfs.add(1);
while (bfs.size() != 0) { // 2~n까지 도착하는 경로 구하기
int nowNode = bfs.poll();
ArrayList<Integer> node = graph.get(nowNode);
for(int i = 0; i < node.size(); i++) {
if (visited[node.get(i)] == false) {
bfs.add(node.get(i));
visited[node.get(i)] = true;
distance[node.get(i)] = distance[nowNode] + 1;
}
}
}
Arrays.sort(distance);
int max = distance[distance.length-1];
for(int i = distance.length-1; distance[i] == max; i--)
answer++;
return answer;
}
}
그래프 구현과 BFS를 알고있다면 편하게 풀 수 있는 문제다.
만약 둘 다 익숙하지 않은 개념이라면 먼저 각 방식을 공부하고 다시 오는 것을 추천한다.
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[프로그래머스] 방의 개수-JAVA (2) | 2022.03.23 |
---|---|
[프로그래머스] 순위-JAVA (0) | 2022.03.19 |
[프로그래머스] 징검다리-JAVA (1) | 2022.03.19 |
[프로그래머스] 입국심사-JAVA (0) | 2022.03.19 |
[프로그래머스] 도둑질-JAVA (0) | 2022.03.10 |