다익스트라

[JAVA] Programmers : 등산코스 정하기

문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 오랜만에 글을 작성한다. 그 동안 꾸준히 알고리즘은 학습하고 있었지만 글 작성을 할 여유가 없어서 작성하지 못했는데 이 문제는 해결 방법을 공유해두면 좋을 것 같아서 작성해보려고 한다. 문제읽기 XX산은 n개의 지점으로 이루어져있는데 각 지점은 1 ~ n 까지 번호가 붙어있고 해당 지점들은 출입구, 쉼터, 산봉우리 중 하나이다. 각 지점으로 이동할 때 등산로를 이용해야하는데 이 때 등산로별로 소요되는 시간이 다르다. 이 때 각 지점에 방문할 때마다 휴식을 취할 수 있는데 휴식 없이 이동해야하는 시간 중 ..

[JAVA] Programmers : 배달

문제 코딩테스트 연습 - 배달 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개의 마을이 있고 각 마을을 잇는 도로가 있다. 해당 도로를 건너는데 시간은 도로마다 다르다. 이때 1번 마을에서 각 마을에 배달을 하려고 하는데 K 시간 이하인 곳만 배달이 가능해서 배달 가능한 마을의 수를 구하는 문제이다. 문제를 보자마자 다익스트라가 떠올라서 다익스트라를 이용해서 풀이를 했다. 각 마을의 도로의 정보는 인접 리스트를 이용해서 정리하고, 다익스트라 배열을 마을 개수만큼 생성한 다음 문제에서 나올 수 있..

[JAVA] 백준 1162 : 도로포장

문제 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로가 연결하는 두 도시와 도로를 통과하 www.acmicpc.net 해결방법 1번에서 N번까지 가는 최소 시간을 출력하는 문제인데, 추가적으로 도로포장이라는 조건이 주어져있다. 포장이 가능한 횟수는 K로 주어지고, 포장을 하게 되면 해당 도시를 잇는 도로를 통과하는 시간이 0이 된다. 그래서 기본 다익스트라에 추가적으로 포장횟수를 기록해야 한다. 원래 배열은 dijk[해당 도시까지 최솟값] 을 나타낸다고 하면 이번 문제에서는 dijk[해당 도시까지 최솟값][포장 횟수] 를 사용한 2차원 ..

[JAVA] 합승 택시 요금

문제 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr 해결 방법 요즘 코딩 테스트를 볼 때 프로그래머스를 많이 이용하기에, 적응을 위해 프로그래머스 문제를 조금 풀어보고 있다. 집까지 가는 최소 비용의 길을 찾는 문제인데, 도착 지점..

[JAVA] 백준 11779 : 최소비용 구하기 2

문제 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 해결 방법 다익스트라를 사용해야하는 문제이다. 다익스트라 문제를 여러 개 풀어보는 중인데 조금 생각이 필요한 문제라 괜찮은 것 같다. 경로는 인접리스트를 통해 입력해 주었고, Bus 클래스를 비용이 적은 순서대로 정렬한 뒤 우선순위큐를 사용해서 다익스트라를 구현하였다. 이 문제에서는 총 방문한 도시의 개수와 방문한 도시를 순서대로 출력을 해야하는 부분이 존재하는데, 그래서 그 전에 방문하였던 도시를 저장할 배열이 필요하다. 나..