Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
Tags
- 11286번
- 10830번
- 냄새와 휴리스틱
- 2206번
- Adapater Pattern
- 클린코드
- springboot
- java
- java의 정석
- 2166번
- DxTrace
- 1300번
- Spring
- 코딩 테스트
- 백준
- Dxerr.h
- 1043번
- 프로그래머스
- Design Pattern
- BOJ
- 자바의 정석
- SerialDate 리펙터링
- 코딩테스트
- 11758번
- 2156번
- programmers
- 가장 긴 증가하는 부분 수열2
- 17장
- 9장
- Design Patterns
Archives
- Today
- Total
Don't give up!
[프로그래머스] 가장 먼 노드(java) 본문
코딩테스트 연습 - 가장 먼 노드 | 프로그래머스 (programmers.co.kr)
어떻게 생각하고 문제를 풀었는가?
Queue를 사용한 BFS를 통해 1번 노드로부터 각 노드로의 최단 경로를 찾을 수 있습니다.
모든 노드까지의 최단 경로를 찾은 후 각 거리의 길이를 계산함으로서 최대 값을 갖고 있는 원소의 수를 알아낼 수 있겠다고 생각하였습니다.
코드
import java.util.*;
class Solution {
private boolean[][] lines;
private int[] dists;
public int solution(int n, int[][] edge) {
lines = new boolean[n][n];
dists = new int[n];
for(int[] line : edge){
lines[line[0]-1][line[1]-1] = true;
lines[line[1]-1][line[0]-1] = true;
}
Queue<Integer> directions = new LinkedList<>();
directions.offer(0);
while(!directions.isEmpty()){
int start = directions.poll();
for(int i=1;i<n;i++){
if(dists[i]==0 && lines[start][i]){
dists[i] = dists[start]+1;
directions.offer(i);
}
}
}
int max=0, count=0;
for(int dist : dists){
if(max<dist){
max=dist;
count=1;
}
else if(max==dist) count++;
}
return count;
}
}
설계를 바탕으로 코드를 작성하였습니다.
주어진 입력은 양방향의 연결을 하나의 배열로 표현한 것이므로 2차원 배열을 선언하여 각 노드에서 갈 수 있는 노드를 표현하였습니다.
또한 BFS에서 먼저 도착한 노드는 최단경로를 갖습니다. 따라서 boolean 배열을 선언하여 방문을 표현하기보다 최단 경로가 정의되어 있다면 Queue에 추가하지 않도록 코드를 작성하였습니다.
'Coding Test > Programmers' 카테고리의 다른 글
[프로그래머스] 단어 변환 (java) (0) | 2021.05.21 |
---|---|
[프로그래머스] 카펫(java) (0) | 2021.05.17 |
[프로그래머스] 쿼드압축 후 개수 세기(java) (0) | 2021.05.16 |