주말엔 프로그래머스를 하기로 하였다.
문제 소개
- N : 마을 수
- road[,0] : 출발지
- road[,1] : 도착지
- road[,2] : 걸리는 시간
- K : 최종 시간
- 1마을에서 출발할 때, 최종 시간안에 도착할 수 있는 마을의 수를 구하라.
힌트
감이 안잡혀서 Gemini에게 도움을 요청했다. 2레벨 부터는 벽이 느껴져서 정말 많이 풀어봐야 할 것 같다.
- 음 학과에서 네트워크 배울 때, 다익스트라 배웠던거 같은데... 코드로 구현해본 적은 없어서 아직도 어떻게 구하는지 모르겠다.
- 그냥 모르는거 적극적으로 도움을 받아보기로 했다.
| PriorityQueue |
|---|
 |
- 다익스트라 알고리즘을 위해선 우선순위 큐가 필요하다길래 일단 개념부터 물어봤다.(기초 자료구조 밖에 모르는데;;)
- 일단 기존 Queue와 달리 우선순위 값이 있어서 그 우선순위 값으로 자동 정렬되는 Queue인 듯하다.
- 우선순위는 숫자가 작은거 우선.
| 시간 복잡도 |
|---|
 |
- 그리고 여러모로 시간 복잡도도 빠른 듯 하다.
| 활용 분야 |
|---|
 |
- 다익스트라(지금 이거 공부할거임)
- 최소 신장 트리
- 스케줄링
- 데이터 스트림 처리
| 없음 |
|---|
 |
- 그딴건 없다고 하신다...
- 이제 그래서 대체하는 방법에 대해서 물어봤다.
| SortedSet 쓰라네요 |
|---|
 |
- SortedSet으로 구현 가능하다고 하신다.
- 일단 SortedSet은 이름만 봤을 때, 정렬되는 Set인듯 하다.
- 그래도 일단 특징을 물어보았다.
| SortedSet |
|---|
 |
- 이진 탐색 트리는 알겠는데 레드 블랙 트리는 머여.. 암튼 시간 복잡도가 좋은 듯하다.
| SortedSet의 특징 |
|---|
 |
- 역시 자동 정렬되는 Set이 맞았다.
- 클래스에 경우, IComparable 을 사용해서 정렬 규칙을 정해두면, 해당 규칙으로 정렬되는 Set이다.
- Set의 특징인 중복도 없다.
| SortedSet의 시간 복잡도 |
|---|
 |
- 속도는 PriorityQueue와 비슷한 듯 하다.
코딩 선생님(Gemini)의 풀이
최대한 해석하면서 코드를 작성했다.
| Edge |
|---|
 |
- node : 마을 번호
- weight : 걸리는 시간
- CompareTo는 비교 방식인데 걸리는 시간을 기준으로 정렬했다.
- 우선순위에 같은 값은 존재할 수 없다고 하여 같을 경우는 마을 번호로 정렬을 하였다.
| adj List 생성 |
|---|
 |
- adj 셋팅인데 adj는 Adjacency (인접)의 약자라고 한다.
- DFS, BFS에서는 방향 값을 설정했다면, 다익스트라에서는 adj를 설정하는 듯하다.
- u : 출발지
- v : 도착지
- w : 걸리는 시간
- 여기서는 양방향 통행이 가능하기 때문에 u와 v 리스트에 추가하였다.
| 예시 |
|---|
 |
| adj | list[0] | list[1] | list[2] |
|---|
| adj[1] | {2,1} | {4,2} | |
| adj[2] | {1,1} | {3,3} | {5,2} |
| adj[3] | {2,3} | {5,1} | |
| adj[4] | {1,2} | {5,2} | |
| adj[5] | {2,2} | {3,1} | {4,2} |
| distance와 SortedSet 생성 |
|---|
 |
- distance는 마을마다 계산된 거리(최솟 값)이 저장될 배열이다.
- ex) 마지막줄에 추가된 값처럼
distance[1] = 0 (1->1은 시간이 0이 들기 때문)
- SortedSet에다가는 시작 지점인 1을 넣어준다
| 계산 시작 |
|---|
 |
- current는 현재 마을.
- u : 현재 마을 번호
- d : 현재 마을까지 걸린 시간
if(distance[u] < d) continue; 를 하는 이유는 이미 최소 값이면 무시하기 위해서- adj[현재 마을 번호]를 통해서 연결된 마을 번호와 걸리는 시간을 추출
- v : 다음 마을 번호
- weight : 다음 마을까지 걸리는 시간
- 이제 distance[v](다음 마을까지 걸리는 총 시간) 보다 weight + distance[u](다음 마을까지 걸리는 시간 + 현재 마을까지 걸리는 총 시간)이 작다면
- 다음 마을까지 걸리는 총 시간에 최소 값을 저장.
- SortedSet에 다음 마을 번호와 걸리는 총 시간을 넣어준다.
| 예시 설명 |
|---|
 |
| 반복 횟수 | u | d | v | weight | distance[u] | distance[v] | ss.Count |
|---|
| 1 | 1 | 0 | 2 | 1 | 0 | MaxValue | 1 |
| 2 | 1 | 0 | 4 | 2 | 0 | MaxValue | 2 |
| 3 | 2 | 1 | 3 | 3 | 1 | MaxValue | 2 |
| 4 | 2 | 1 | 5 | 2 | 1 | MaxValue | 3 |
| 5 | 4 | 2 | 5 | 2 | 2 | 3 | 2 |
| 6 | 5 | 3 | 3 | 1 | 3 | 4 | 1 |
| 7 | 3 | 4 | | | | | 0 |
- 1마을에서 3이하에 갈 수 있는 마을을 총 4개이다.
| 결과 출력 코드 |
|---|
 |
소감
머리아퍼
