RIEN😚
이상한 나라의 개발자
RIEN😚
전체 방문자
오늘
어제
  • 분류 전체보기 (125)
    • Algorithm (68)
      • 알고리즘 (0)
      • Baekjoon (8)
      • 프로그래머스 (55)
      • HackerRank (5)
    • Android (30)
      • Project (1)
      • Error (2)
      • Studio (1)
      • Android (26)
    • Kotlin (6)
    • CS (4)
      • 네트워크 (2)
      • 데이터베이스 (2)
    • Front End (5)
      • React (1)
      • VUE (3)
      • Project (0)
      • 기타 (1)
    • 기록 (11)
      • 회고록 (6)
      • TIL (5)

블로그 메뉴

  • Github🔥
  • 포트폴리오🌹

공지사항

인기 글

티스토리

250x250
반응형
hELLO · Designed By 정상우.
RIEN😚
Algorithm/프로그래머스

[프로그래머스] Lv 2. 배달

Algorithm/프로그래머스

[프로그래머스] Lv 2. 배달

2022. 5. 25. 11:30
728x90
반응형
 

코딩테스트 연습 - 배달

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

programmers.co.kr

 

문제

마을의 개수 N, 각 마을을 연결하는 도로의 정보 road, 음식 배달이 가능한 시간 K가 매개변수로 주어질 때, 음식 주문을 받을 수 있는 마을의 개수를 return 하도록 solution 함수를 완성해주세요.

 

풀이

문제를 보면 딱 보아도 최단거리 그래프 문제입니다.

최단거리 알고리즘으로는 다익스트라와 플로이드-와샬이 있지만,

출발점이 정해져 있는 상황이라면 다익스트라를 사용하는 것이 좋습니다.🤗

 

해당 문제는 1번 마을이 출발점으로 고정되어 있으므로 다익스트라 알고리즘을 사용하여

최단거리가 K 이하인 마을의 개수를 계산해주면 됩니다.

 

알고가자

Kotlin으로 코딩테스트를 푼지 얼마 되지 않아, 문제를 풀 때 사용한 kotlin 문법에 대해서 잠시 정리해보겠습니다.😪

 

- 2차원 배열 만들기

val maps = Array(N, { IntArray(N, {0}) })

- 우선순위 큐

Pair를 이용한 우선순위 큐 만들기
val queue = PriorityQueue(Comparator<Pair<Int, Int>>{ a, b ->
	// 비교 코드
    return a.second - b.second
})

 

문제 풀이 시, 주의할 점

문제를 다 풀고 다시 테스트 케이스 채점을 해보니, 몇 개 틀린 문제들이 있었습니다.

왜틀??🤔

 

다시 한번 문제를 읽어보니, 1번 마을에서부터 시작해서 다시 1번 마을로 돌아오는 경로를

잘못 계산하고 있었습니다.

1번 마을은 무조건 0시간 이라는 것에 유의해주세요.

 

코드

import java.util.*

class Solution {
    fun solution(N: Int, road: Array<IntArray>, k: Int): Int {
        var answer = 0
        
        val INF = (1e9).toInt()
        // 각 정점까지의 최단거리를 저장할 배열
        val dp = IntArray(N){ INF }
        // 마을간의 연결관계
        val maps = Array(N, { IntArray(N, {INF})})
        road.forEach{ (a,b,c) ->
            if (maps[a-1][b-1] > c) {
                maps[a-1][b-1] = c
                maps[b-1][a-1] = c
            }
        }
        
        val q = PriorityQueue(Comparator<Pair<Int, Int>>{a, b -> a.second - b.second})
        q.add(Pair(0,0))
        
        while(q.isNotEmpty()) {
            val (s, cost) = q.poll()
            
            for ((e,c) in maps[s].withIndex()) {
                if (c != INF) {
                    val nc = cost + c
                    if (dp[e] > nc) {
                        dp[e] = nc
                        q.add(Pair(e,nc))
                    }
                }
            }
        }
        return dp.filterIndexed{ i,x -> if (i==0) true else x<=k}.size
    }
}

 

반응형

'Algorithm > 프로그래머스' 카테고리의 다른 글

[프로그래머스] Lv 2. 모음사전  (0) 2022.05.25
[프로그래머스] Lv 2. 전력망을 둘로 나누기  (0) 2022.05.25
[프로그래머스] Lv 2. 2개 이하로 다른 비트  (0) 2022.05.13
[프로그래머스] Lv 2. 괄호 회전하기  (0) 2022.05.13
[프로그래머스] Lv 2. 피로도  (0) 2022.05.13
  • 문제
  • 풀이
  • 알고가자
  • 문제 풀이 시, 주의할 점
  • 코드
'Algorithm/프로그래머스' 카테고리의 다른 글
  • [프로그래머스] Lv 2. 모음사전
  • [프로그래머스] Lv 2. 전력망을 둘로 나누기
  • [프로그래머스] Lv 2. 2개 이하로 다른 비트
  • [프로그래머스] Lv 2. 괄호 회전하기
RIEN😚
RIEN😚
안드로이드 / 코틀린 독학으로 취업하자!

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.