프로그래머스 - 등산 코스 정하기

문제 설명

n개의 등산지점이 있다.

출발지점으로 부터 목적지 지점까지 , 목적지점으로부터 출발지점까지 최소 인텐시티를 등상코스를 정하라

인텐시티란 거쳐가는 최대 간선 비용이다.

생각한 아이디어

인텐시티를 짧게 하려면 짧은 코스트를 가진 방향 리스트로 부터 구할 수 있다고 생각했다.

하지만 일반적인 다익스트라는 한 지점으로부터 다른지점의 최소 거리를 구하는 것이다.

조금 변형하여 최소거리가 아닌 최소 인텐시티 테이블을 두고 구하면 어떨까라는 아이디어는 해설을 참조하여 발견했다.

주의사항

• 간선의 정보를 저장하는 구조를 잘만들어야 한다.
  • 봉우리는 단 한번만 지나야 하는 규칙이 존재한다.
  • 다른 출입구는 거칠 수 없어야 한다.
  • 이런 경우가 있을 수 있다
    • 봉우리가 가장 작은 간선비용을 가져서 한번더 지날 수 있기 때문이다.
    • 출입구쪽으로 들어가고 다른곳으로 나가는 인텐시티가 최소일 수 있다.

2022 테크 여름인턴십 코딩테스트 해설

다른 분은 신기한 아이디어로 접근했다.

MST(최소 비용 건설)를 형성하고 그래프 탐색을 시도하였다.

풀이

static final int INF=Integer.MAX_VALUE;

	class Node implements Comparable<Node>{
		int v,w;

		public Node(int v,int w){
			this.v=v;
			this.w=w;
		}

		@Override
		public int compareTo(Node o){
			return this.w - o.w;
		}
	}
	List<Node> adj[];
	public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
		adj=new List[n+1];
		for(int i=0; i<=n; i++){
			adj[i]=new ArrayList<>();
		}

		Set<Integer> starts=Arrays.stream(gates).boxed().collect(Collectors.toSet());
		Set<Integer> targets=Arrays.stream(summits).boxed().collect(Collectors.toSet());

		// 출입구 또는 봉우리는 반드시 한번 지나야한다! 그렇기에 출입구는 나가는 간선만, 봉우리는 들어가는 간선만
		for(int[] path: paths){
			int from=path[0];
			int to=path[1];
			int weight=path[2];
			if(starts.contains(from) || targets.contains(to)){
				adj[from].add(new Node(to,weight));
			}else if(starts.contains(to) || targets.contains(from)){
				adj[to].add(new Node(from,weight));
			}else{
				adj[from].add(new Node(to,weight));
				adj[to].add(new Node(from,weight));
			}
		}

		return dijkstra(n,gates,summits);
	}

	int[] dijkstra(int n,int[] gates, int[] summits){
		int intensities[]=new int[n+1]; // 현재까지 경로를 따라서 온 인텐시티의 최댓값
		Arrays.fill(intensities,INF);
		PriorityQueue<Node> pq=new PriorityQueue<>();

		for(int start:gates){
			intensities[start]=0;
			pq.offer(new Node(start,0));
		}

		while(!pq.isEmpty()){
			Node cur=pq.poll();

			if(intensities[cur.v] < cur.w) continue;

			for(Node next: adj[cur.v]){
				// 현재까지 온 인텐시티 최소값 과 현재 경로의 코스트 값 중 누가 큰가
				int intensity=Math.max(intensities[cur.v],next.w);
				if(intensities[next.v] > intensity){ // 현재까지 온 인텐시티 보다 큰게 있다면 교체
					intensities[next.v]=intensity;
					pq.offer(new Node(next.v, intensity));
				}

			}
		}
		int minIntensity=INF;
		int minSummit=0;

		Arrays.sort(summits); // 인텐시티가 같다면 가장 작은 봉우리를 가진 것이 우선
		for(int summit: summits){
			if(intensities[summit] <minIntensity){
				minIntensity=intensities[summit];
				minSummit=summit;
			}
		}

		return new int[]{minSummit,minIntensity};
	}