-
코딩테스트 연습 - 등산코스 정하기 (2022 KAKAO TECH, (DP, 그래프, BFS, 자료구조) 본문
# 주소
https://school.programmers.co.kr/learn/courses/30/lessons/118669#qna
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
# 문제
문제 설명
XX산은 n개의 지점으로 이루어져 있습니다. 각 지점은 1부터 n까지 번호가 붙어있으며, 출입구, 쉼터, 혹은 산봉우리입니다. 각 지점은 양방향 통행이 가능한 등산로로 연결되어 있으며, 서로 다른 지점을 이동할 때 이 등산로를 이용해야 합니다. 이때, 등산로별로 이동하는데 일정 시간이 소요됩니다.
등산코스는 방문할 지점 번호들을 순서대로 나열하여 표현할 수 있습니다.
예를 들어 1-2-3-2-1 으로 표현하는 등산코스는 1번지점에서 출발하여 2번, 3번, 2번, 1번 지점을 순서대로 방문한다는 뜻입니다.
등산코스를 따라 이동하는 중 쉼터 혹은 산봉우리를 방문할 때마다 휴식을 취할 수 있으며, 휴식 없이 이동해야 하는 시간 중 가장 긴 시간을 해당 등산코스의 intensity라고 부르기로 합니다.
당신은 XX산의 출입구 중 한 곳에서 출발하여 산봉우리 중 한 곳만 방문한 뒤 다시 원래의 출입구로 돌아오는 등산코스를 정하려고 합니다. 다시 말해, 등산코스에서 출입구는 처음과 끝에 한 번씩, 산봉우리는 한 번만 포함되어야 합니다.
당신은 이러한 규칙을 지키면서 intensity가 최소가 되도록 등산코스를 정하려고 합니다.
다음은 XX산의 지점과 등산로를 그림으로 표현한 예시입니다.
- 위 그림에서 원에 적힌 숫자는 지점의 번호를 나타내며, 1, 3번 지점에 출입구, 5번 지점에 산봉우리가 있습니다. 각 선분은 등산로를 나타내며, 각 선분에 적힌 수는 이동 시간을 나타냅니다. 예를 들어 1번 지점에서 2번 지점으로 이동할 때는 3시간이 소요됩니다.
위의 예시에서 1-2-5-4-3 과 같은 등산코스는 처음 출발한 원래의 출입구로 돌아오지 않기 때문에 잘못된 등산코스입니다. 또한 1-2-5-6-4-3-2-1 과 같은 등산코스는 코스의 처음과 끝 외에 3번 출입구를 방문하기 때문에 잘못된 등산코스입니다.
등산코스를 3-2-5-4-3 과 같이 정했을 때의 이동경로를 그림으로 나타내면 아래와 같습니다.
이때, 휴식 없이 이동해야 하는 시간 중 가장 긴 시간은 5시간입니다. 따라서 이 등산코스의 intensity는 5입니다.
등산코스를 1-2-4-5-6-4-2-1 과 같이 정했을 때의 이동경로를 그림으로 나타내면 아래와 같습니다.
이때, 휴식 없이 이동해야 하는 시간 중 가장 긴 시간은 3시간입니다. 따라서 이 등산코스의 intensity는 3이며, 이 보다 intensity가 낮은 등산코스는 없습니다.
XX산의 지점 수 n, 각 등산로의 정보를 담은 2차원 정수 배열 paths, 출입구들의 번호가 담긴 정수 배열 gates, 산봉우리들의 번호가 담긴 정수 배열 summits가 매개변수로 주어집니다. 이때, intensity가 최소가 되는 등산코스에 포함된 산봉우리 번호와 intensity의 최솟값을 차례대로 정수 배열에 담아 return 하도록 solution 함수를 완성해주세요. intensity가 최소가 되는 등산코스가 여러 개라면 그중 산봉우리의 번호가 가장 낮은 등산코스를 선택합니다.
제한사항
- 2 ≤ n ≤ 50,000
- n - 1 ≤ paths의 길이 ≤ 200,000
- paths의 원소는 [i, j, w] 형태입니다.
- i번 지점과 j번 지점을 연결하는 등산로가 있다는 뜻입니다.
- w는 두 지점 사이를 이동하는 데 걸리는 시간입니다.
- 1 ≤ i < j ≤ n
- 1 ≤ w ≤ 10,000,000
- 서로 다른 두 지점을 직접 연결하는 등산로는 최대 1개입니다.
- 1 ≤ gates의 길이 ≤ n
- 1 ≤ gates의 원소 ≤ n
- gates의 원소는 해당 지점이 출입구임을 나타냅니다.
- 1 ≤ summits의 길이 ≤ n
- 1 ≤ summits의 원소 ≤ n
- summits의 원소는 해당 지점이 산봉우리임을 나타냅니다.
- 출입구이면서 동시에 산봉우리인 지점은 없습니다.
- gates와 summits에 등장하지 않은 지점은 모두 쉼터입니다.
- 임의의 두 지점 사이에 이동 가능한 경로가 항상 존재합니다.
- return 하는 배열은 [산봉우리의 번호, intensity의 최솟값] 순서여야 합니다.
입출력 예npathsgatessummitsresult
| 6 | [[1, 2, 3], [2, 3, 5], [2, 4, 2], [2, 5, 4], [3, 4, 4], [4, 5, 3], [4, 6, 1], [5, 6, 1]] | [1, 3] | [5] | [5, 3] |
| 7 | [[1, 4, 4], [1, 6, 1], [1, 7, 3], [2, 5, 2], [3, 7, 4], [5, 6, 6]] | [1] | [2, 3, 4] | [3, 4] |
| 7 | [[1, 2, 5], [1, 4, 1], [2, 3, 1], [2, 6, 7], [4, 5, 1], [5, 6, 1], [6, 7, 1]] | [3, 7] | [1, 5] | [5, 1] |
| 5 | [[1, 3, 10], [1, 4, 20], [2, 3, 4], [2, 4, 6], [3, 5, 20], [4, 5, 6]] | [1, 2] | [5] | [5, 6] |
입출력 예 설명
입출력 예 #1
문제 예시와 같습니다. 등산코스의 intensity가 최소가 되는 산봉우리 번호는 5, intensity의 최솟값은 3이므로 [5, 3]을 return 해야 합니다.
입출력 예 #2
XX산의 지점과 등산로를 그림으로 표현하면 아래와 같습니다.
가능한 intensity의 최솟값은 4이며, intensity가 4가 되는 등산코스는 1-4-1 과 1-7-3-7-1 이 있습니다. intensity가 최소가 되는 등산코스가 여러 개이므로 둘 중 산봉우리의 번호가 낮은 1-7-3-7-1 을 선택합니다. 따라서 [3, 4]를 return 해야 합니다.
입출력 예 #3
XX산의 지점과 등산로를 그림으로 표현하면 아래와 같습니다.
가능한 intensity의 최솟값은 1이며, 그때의 등산코스는 7-6-5-6-7 입니다. 따라서 [5, 1]를 return 해야 합니다.
- 7-6-5-4-1-4-5-6-7 과 같은 등산코스는 산봉우리를 여러 번 방문하기 때문에 잘못된 등산코스입니다.
입출력 예 #4
XX산의 지점과 등산로를 그림으로 표현하면 아래와 같습니다.
가능한 intensity의 최솟값은 6, 그때의 등산코스는 2-4-5-4-2 입니다. 따라서 [5, 6]을 return 해야 합니다.
# 문제 해설 및 코드 리뷰
import java.util.*;
class Point {
int x;
int cost;
Point(int x, int cost){
this.x = x;
this.cost = cost;
}
}
class Solution {
static int[] dp;
static HashSet<Integer> hashSet;
static HashSet<Integer> hashSet2;
static ArrayList<ArrayList<Point>> list;
public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
dp = new int[n + 1];
int result = Integer.MAX_VALUE;
list = new ArrayList<>();
for(int i = 0; i <= n; i++){
list.add(new ArrayList<>());
dp[i] = Integer.MAX_VALUE;
}
hashSet = new HashSet<>();
hashSet2 = new HashSet<>();
for (int gate : gates) hashSet.add(gate);
for(int summit : summits) hashSet2.add(summit);
for(int[] path : paths){
list.get(path[0]).add(new Point(path[1], path[2]));
list.get(path[1]).add(new Point(path[0], path[2]));
}
int[] answer = new int[]{0, Integer.MAX_VALUE - 1};
for(Integer start : hashSet)
dfs(start);
for(Integer temp : hashSet2){
if(result == dp[temp] && answer[0] > temp)
answer[0] = temp;
if(result > dp[temp]){
result = dp[temp];
answer[0] = temp;
answer[1] = dp[temp];
}
}
return answer;
}
static void dfs(int start){
Queue<Point> queue = new LinkedList<>();
queue.offer(new Point(start, 0));
while (!queue.isEmpty()){
Point now = queue.poll();
if(hashSet2.contains(now.x))
continue;
for(Point power : list.get(now.x)){
if(!hashSet.contains(power.x)){
int next = Math.max(now.cost, power.cost);
if(next < dp[power.x]){
queue.offer(new Point(power.x, next));
dp[power.x] = next;
}
}
}
}
}
}문제 이해는 쉬웠으나 시간초과가 나기 쉬운 문제입니다.
저는 최초에 풀 때 DFS를 이용한 완전탐색으로 풀었습니다만 시간 초과가 나는 바람에 많이 헤맸습니다.
그래서 질문하기 코너에서 다른 분의 코드를 봤는데 맙소사.
DP를 이용해서 푸셨더군요.
그 분도 저랑 마찬가지로 양방향 간선연결 + HashSet 2개 사용까지 똑같더라구요.
여기서 저는 출발지점에서 끝지점까지의 탐색과 끝지점에서 출발지점까지 탐색을 따로 진행하여 최솟비용과 노드를 구했는데 테스트6번부터 시간초과가 나더라구요. ㅠㅠㅠ
그리고 또하나.
저는 Queue를 활용하지 않고 재귀를 이용하여 풀이하였는데 확실히 N값이 클 때는 앞으로 재귀를 쓰면 안될 것 같습니다.
Queue를 적극적으로 활용합시다.
어떤 분은 PriorityQueue를 쓰시던데 전 어짜피 HashSet을 쓴 입장이고 나중에 따로 처리할 수 있는 부분이여서 정렬하거나 Pq를 쓰진 않았습니다.
코드를 보기 전 문제를 요약해봅시다.
# 문제 요약
1. 출발지점에서 도착지점까지 갈 수 있는 노선 중 최대 비용을 Intensity라고 합니다.
2. 여러 경로들 중 이 Intensity가 최소가 되게 할 때, 산봉우리의 노드와 Intensity를 구해야 합니다.
3. 이를 위해 출발지점과 도착지점의 재방문을 따로 처리해주어야 합니다.
4. 양방향 간선에 주의해야 하고 끝지점에서 출발지점은 굳이 탐색할 필요 없습니다.
이건 제가 최초에 풀었던 코드입니다.
# DFS를 이용한 풀이 (시간 초과)
import java.util.*;
class Solution {
static HashSet<Integer> hashSet;
static HashSet<Integer> hashSet2;
static int result;
static int[] answer;
static int[][] arr;
static boolean[][] visit;
public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
result = Integer.MAX_VALUE;
answer = new int[2];
hashSet = new HashSet<>();
hashSet2 = new HashSet<>();
arr = new int[n + 1][n + 1];
visit = new boolean[n + 1][n + 1];
for(int gate : gates)
hashSet.add(gate);
for(int summit : summits)
hashSet2.add(summit);
for(int[] path : paths)
arr[path[0]][path[1]] = arr[path[1]][path[0]] = path[2];
visit = new boolean[n + 1][n + 1];
for(int gate : gates)
dfs(gate, 0, 0);
return answer;
}
static void dfs(int now, int max, int s){
if(hashSet2.contains(s)){
if(result == max && answer[0] > s)
answer[0] = s;
if(result > max){
result = max;
answer[0] = s;
answer[1] = max;
}
return;
}
for(int i = 1; i < arr.length; i++){
if(!visit[now][i] && arr[now][i] > 0 && !hashSet2.contains(i)){
visit[now][i] = true;
dfs(i, Math.max(max, arr[now][i]), s);
visit[now][i] = false;
}else if(!visit[now][i] && arr[now][i] > 0 && hashSet2.contains(i)){
visit[now][i] = true;
dfs(i, Math.max(max, arr[now][i]), i);
visit[now][i] = false;
}
}
}
}N값이 클 땐 재귀로 푸시면 큰일납니다!
Queue를 이용한 풀이가 더욱 좋겠습니다.
저도 앞으로 더욱 DFS를 이용한 재귀 + 완탐으로 부딪히지 않고 자료구조를 적극 활용해야겠습니다 ㅎ..
Queue를 활용하는데 파라미터를 2개를 담을 클래스를 활용해야합니다.
class Point {
int x;
int cost;
Point(int x, int cost){
this.x = x;
this.cost = cost;
}
}따라서 x는 노드의 번호, cost는 노드간의 비용이라고 하겠습니다.
static int[] dp;
static HashSet<Integer> hashSet;
static HashSet<Integer> hashSet2;
static ArrayList<ArrayList<Point>> list;hashset을 사용해서 푸는게 깔끔한데, 속도가 빠르고 자료구조 안의 값이 있는지없는지 유무만 체크하기 위해서 2개를 사용할 것입니다.
hashSet은 출발지점인 gates를, hashSet2는 도착지점인 summits를 저장합니다.
ArrayList를 Point타입의 ArrayList타입이라고 생성하는 것은 양방향 간선을 저장하기 위해서 그렇습니다.
예를들어 1번 노드에서의 간선과 비용을 모두 저장한다 했을 때, 예상되는 형태는
list.get(1)로 가져올 수 있을 것이고 이 내부에는 Point타입의 클래스들이 ArrayList형태로 저장되어 있게됩니다.
dp는 최솟값을 갱신하기 위해 선언합니다.
dp = new int[n + 1];
int result = Integer.MAX_VALUE;
list = new ArrayList<>();
for(int i = 0; i <= n; i++){
list.add(new ArrayList<>());
dp[i] = Integer.MAX_VALUE;
}
hashSet = new HashSet<>();
hashSet2 = new HashSet<>();
for (int gate : gates) hashSet.add(gate);
for(int summit : summits) hashSet2.add(summit);dp크기를 지정해주고 list도 크기를 지정해줍니다.
예전엔 전 list를 배열처럼 사용했었습니다. 근데 자바에서 권장하는 방법이 아니라고 들어서 최대한 사용을 줄이시는 것이 좋을 것 같네용.
list도 마찬가지로 n + 1개만큼 생성해주고 dp에는 최댓값을 넣습니다.
hashSet과 hashSet2에는 각각 gate와 summit을 삽입합니다.
for(int[] path : paths){
list.get(path[0]).add(new Point(path[1], path[2]));
list.get(path[1]).add(new Point(path[0], path[2]));
}양방향 간선의 값을 넣습니다.
int[] answer = new int[]{0, Integer.MAX_VALUE - 1};
for(Integer start : hashSet)
dfs(start);이후부터 정답이 될 answer를 생성하고 dfs문을 시작합니다.
hashSet의 start부터 시작하여 dfs를 실행합니다.
static void dfs(int start){
Queue<Point> queue = new LinkedList<>();
queue.offer(new Point(start, 0));
while (!queue.isEmpty()){
Point now = queue.poll();
if(hashSet2.contains(now.x))
continue;
for(Point power : list.get(now.x)){
if(!hashSet.contains(power.x)){
int next = Math.max(now.cost, power.cost);
if(next < dp[power.x]){
queue.offer(new Point(power.x, next));
dp[power.x] = next;
}
}
}
}
}dfs의 내부는 다음과 같습니다.
Queue를 생성하여 start지점부터 탐색하기 위해 start와 0을 넣습니다.
이후 여느 다른 bfs문제처럼 while문으로 queue에서 값을 빼내온 것으로 탐색을 진행합니다.
Point now = queue.poll();여기서 가져온 now점부터 시작해봅시다.
for(Point power : list.get(now.x)){
if(!hashSet.contains(power.x)){
int next = Math.max(now.cost, power.cost);
if(next < dp[power.x]){
queue.offer(new Point(power.x, next));
dp[power.x] = next;
}
}
}now점에서 가져온 now의 x값은 x노드와 연결된 모든 노드들을 확인할 수 있습니다.
이 노드들을 power로 가져와서 이 power의 x노드가 hashSet에 포함되어 있지 않아야 합니다.
그러니까 출발지점이 아닌 어떠한 새로운 노드여야 한다는 뜻입니다.
그리고 이 때의 비용과 현재 노드의 비용과 비교하여 next에 저장합니다.
최초의 탐색일 경우 dp의 값이 모두 최댓값이므로 next보다 크겠지만 이후의 탐색에서도 마찬가지로 dp값보다 next가 더 적다면 새로 탐색하기 위해 queue에 넣고 dp에도 값을 next로 넣습니다.
참으로 아이러니한 상황이 여기서 나온 겁니다.
간선간의 비용을 최댓값을 찾는데 그 최댓값이 다른 경로를 이용해서 도달한 것 보다 더 작아야 한다는 뜻입니다.
따라서 굳이 visit배열을 설정하지 않아도 dp의 값만 최솟값으로 갱신하면 되기 때문에 모두 걸러질 수 있게됩니다.
또한 hashSet2에 도착하게 되면 탐색하지 않아도 되므로 continue해주는 것이구요.
for(Integer temp : hashSet2){
if(result == dp[temp] && answer[0] > temp)
answer[0] = temp;
if(result > dp[temp]){
result = dp[temp];
answer[0] = temp;
answer[1] = dp[temp];
}
}그리고 answer배열에 값을 넣어주심 됩니다.
hashSet2의 값들만 dp에서 찾아 쓰면 되므로 result보다 적은 값들은 answer에 넣어주시고 만약 result가 서로 같으면 temp가 더 작은 것을 넣어주시면 됩니다.
이렇게 만들어도 최대 20만 정도의 N값이라서 정렬을 굳이 하지 않고 제어문을 통해 답을 도출해낼 수 있었습니다.
문제가 쉬울 줄 알고 가벼운 마음으로 풀었다가 시간초과를 제대로 해결하지 못해서 많이 아쉬웠습니다.
LEVEL3는 확실히 어려운게 체감이 되네요.
감사합니다.
'프로그래머스 문제 풀이' 카테고리의 다른 글
| 프로그래머스 코딩테스트 연습 - 외벽 점검 (2020 카카오, 구현, 완전 탐색, 순열) (1) | 2022.09.21 |
|---|---|
| 코딩테스트 연습 - 길 찾기 게임 (2019 KAKAO BLIND, 전위순회, 중위순회, 후외순회) (0) | 2022.09.15 |
| 코딩테스트 연습 - 기지국 설치 (그리디) (0) | 2022.09.14 |
| 프로그래머스 연습 - [1차] 셔틀버스 (2018 카카오 블라인드 채용), 자바, 우선순위 큐, 문자열) (0) | 2022.09.08 |
| 프로그래머스 코딩테스트 연습 - k진수에서 소수 개수 구하기(2022 카카오 블라인드 채용 5번 문제) (2) | 2022.09.05 |
