3 분 소요

문제

코딩테스트 연습 - 등산코스 정하기

문제 요약

  • 등산코스를 따라 이동하는 중 쉼터 혹은 산봉우리를 방문할 때마다 휴식을 취할 수 있으며, 휴식 없이 이동해야 하는 시간 중 가장 긴 시간을 해당 등산코스의 intensity라고 부른다.
  • 등산 코스에서 출입구는 처음과 끝에 한 번씩, 산봉우리는 한 번만 포함되어야 한다.
  • intensity가 최소가 되도록 등산코스를 정하라.

내 풀이

import java.util.*;

public class Programmers_118669 {
	static List<Edge>[] graph;
	static int N;
	static boolean[] isGate;
	static boolean[] isSummit;
	static class Edge implements Comparable<Edge>{
		int to;
		int w;
		int maxIntensity;
		public Edge(int to, int w, int maxIntensity) {
			this.to = to;
			this.w = w;
			this.maxIntensity = maxIntensity; 
		}
		
		@Override
		public int compareTo(Edge o) {
			return this.w - o.w;
		}
	}
	
	// gate -> summit intensity
	static int getIntensity(int gate, int summit) {
		System.out.println("gate : "+gate+", summit : "+summit);
		boolean[] visited = new boolean[N+1];
		visited[gate] = true;
		
		
		PriorityQueue<Edge> pq = new PriorityQueue<>();
		for(Edge e : graph[gate]) {
			pq.add(e);
		}
		
		int intensityRst = Integer.MAX_VALUE;
		
		// visit 체크를 언제 해줘야하지?
		while(!pq.isEmpty()) {
			Edge now = pq.remove();
			visited[now.to] = true;
			
			if(now.to == summit) {
				intensityRst = Math.min(now.maxIntensity, intensityRst);
				System.out.println("arrive : "+now.to+", "+now.w+", "+intensityRst);
//				break;
			} else if(isSummit[now.to] || isGate[now.to]) {
				continue;
			}
			
			for(Edge next : graph[now.to]) {
				if(!visited[next.to]) {
					int biggerIntensity = Math.max(now.maxIntensity, next.w);
					pq.add(new Edge(next.to, next.w, biggerIntensity));
					
				}
			}
		}
		
		return intensityRst;
	} 
	
	public static int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
		N = n;
		isGate = new boolean[n+1];
		isSummit = new boolean[n+1];
		for(int i=0; i<gates.length; i++) {
			isGate[gates[i]] = true;
		}
		for(int i=0; i<summits.length; i++) {
			isSummit[summits[i]] = true;
		}
		
        int[] answer = {};
        // 그래프 만들기
        graph = new ArrayList[n+1];
        for(int i=1; i<=n; i++) {
        	graph[i] = new ArrayList<>();
        }
        
        for(int i=0; i<paths.length; i++) {
        	int u = paths[i][0];
        	int v = paths[i][1];
        	int w = paths[i][2];
        	
        	if(isGate[u] || isSummit[v]) {
        		graph[u].add(new Edge(v, w, w));
        	}else if(isGate[v] || isSummit[u]) {
        		graph[v].add(new Edge(u,w, w));
        	}else {
        		graph[u].add(new Edge(v, w, w));
        		graph[v].add(new Edge(u,w, w));
        	}
        }
        
        int minIntensity = Integer.MAX_VALUE;
        int minSummit = -1;
        
        // 출발지 선택
        // summit 선택
        for(int i=0; i<gates.length; i++) {
        	int gate = gates[i];
        	for(int j=0; j<summits.length; j++) {
        		int summit = summits[j];
        		// 출발지 -> summit -> 출발지에 대한 intensity 구하기 -> 최소인 경우 산봉우리 번호, intensity update
        		int intensity = getIntensity(gate, summit);
        		System.out.println("back : "+gate+", "+summit+", "+intensity);
        		
        		if(minIntensity > intensity) {
        			minIntensity = intensity;
        			minSummit = summit;
        		}
        	}
        }
        
        answer = new int[] {minSummit, minIntensity};
        return answer;
    }
}
  • 헷갈린 부분 : visit 체크
  • 정답은 맞는데 시간 초과 뜸 → 최적화 필요
  • 최적화 대상 → 이중 for 문 제거, 다익스트라 → 모든 gate에서 모든 정점 대상으로 최소값 갱신만 해주면 된다. (다익스트라라고 하는데 다익스트라는 아닌듯. 비슷한데 다름)

해설

public class Programmers_118669 {
	static List<Edge>[] graph;
	static class Edge {
		int to;
		int w;
		public Edge(int to, int w) {
			this.to = to;
			this.w = w;
		}
	}
	
	private static int[] dijkstra(int n, int[] gates, int[] summits) {
		Queue<Edge> q = new LinkedList<>();
		int[] intensity = new int[n+1];	// intensity[i] : i번 노드까지 모든 출발지 -> 모든 노드까지의 모든 경로 중에서 최소 intensity가 담긴다. 
		
		Arrays.fill(intensity, Integer.MAX_VALUE);
		
		// 출입구 전부를 큐에 넣음
		for(int gate : gates) {
			q.add(new Edge(gate, 0));		// 이때 가중치를 0으로 넣음. 의미적으로 가중치가 아니라 intensity
			intensity[gate] = 0; 
		}
		
		while(!q.isEmpty()) {
			Edge now = q.remove();
			
			if(now.w < intensity[now.to]) continue;	// pruning
			
			for(Edge next : graph[now.to]) {
				// next.to까지의 최소 intensity 갱신
				int dis = Math.max(intensity[now.to], next.w);
				if(intensity[next.to] > dis) {
					intensity[next.to] = dis;
					q.add(new Edge(next.to, dis));
				}
			}
		}
		
		int rstSummit = Integer.MAX_VALUE;
		int rstIntensity = Integer.MAX_VALUE;
		
		Arrays.sort(summits);
		
		for(int summit : summits) {
			if(intensity[summit] < rstIntensity) {
				rstSummit = summit;
				rstIntensity = intensity[summit];
			}
		}
		
		return new int[] {rstSummit, rstIntensity};
	}
	
	public static int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
		boolean[] isGate = new boolean[n+1];
		boolean[] isSummit = new boolean[n+1];
		for(int i=0; i<gates.length; i++) {
			isGate[gates[i]] = true;
		}
		for(int i=0; i<summits.length; i++) {
			isSummit[summits[i]] = true;
		}
		
        // 그래프 만들기
        graph = new ArrayList[n+1];
        for(int i=1; i<=n; i++) {
        	graph[i] = new ArrayList<>();
        }
        
        for(int i=0; i<paths.length; i++) {
        	int u = paths[i][0];
        	int v = paths[i][1];
        	int w = paths[i][2];
        	
        	if(isGate[u] || isSummit[v]) {
        		graph[u].add(new Edge(v, w));
        	}else if(isGate[v] || isSummit[u]) {
        		graph[v].add(new Edge(u,w));
        	}else {
        		graph[u].add(new Edge(v, w));
        		graph[v].add(new Edge(u,w));
        	}
        }
        
        return dijkstra(n, gates, summits);
    }
}
  • 애초에 visit 체크도 안 넣는다.
  • 모든 노드에 대한 intensity를 배열에 저장한다. (나는 Node 자체에 변수로 넣어두고, 최대값만 override했음) ⇒ 따라서 bfs 탐색을 한번만 하면 된다.

참고