G14699. 관악산 등산

문제

제출 코드

• 사용 알고리즘 : 트리, BFS

가장 높은 쉼터에서부터 시작해서 더 낮은 쉼터로 내려가며 각 쉼터의 최대 방문횟수를 계산했다.

최대 방문횟수를 저장할 result 배열을 만들고, 가장 높은 쉼터부터 방문해서 해당 쉼터의 result값이 0이면 그 쉼터와 연결된 더 낮은 쉼터들을 bfs로 찾아 각 쉼터의 result값을 넣는다.

낮은 쉼터 중 이미 방문한 쉼터에 대하여, 이번 방문횟수가 더 큰 경우에는 그 하위의 쉼터들도 다시 값을 갱신해줘야 한다.

package gold;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class G14699_mountainClimbing {
	static int[] height, result;
	static List<Integer>[] edges;

	static class Node implements Comparable<Node>{
		int idx, height; // idx:쉼터번호, height:높이, shelter:오를 수 있는 최대 쉼터 수

		Node(int idx, int height){
			this.idx = idx;
			this.height = height;
		}
		@Override
		public int compareTo(Node o) { // 오름차순 정렬
			return o.height - this.height;
		}

	}

	static void bfs(int start) {
		result[start] = 1;
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(start);

		int cnt = 1;
		while(!queue.isEmpty()) {
			cnt++;
			int size = queue.size();

			for(int s=0; s<size; s++) {
				int now = queue.poll();

				for(int n : edges[now]) {
					if(height[n]<height[now] && result[n]<cnt) {
						result[n] = cnt;
						queue.add(n);
					}
				}

			}
		}
	}
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		Node[] nodes = new Node[N];
		height = new int[N+1];
		edges = new List[N+1];

		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			int h = Integer.parseInt(st.nextToken());
			nodes[i] = new Node(i+1, h);
			height[i+1] = h;
			edges[i+1] = new ArrayList<Integer>();
		}

		Arrays.sort(nodes);

		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			edges[a].add(b);
			edges[b].add(a);
		}

		result = new int[N+1];
		for(int i=0; i<N; i++) {
			if(result[nodes[i].idx]==0) bfs(nodes[i].idx);
		}

		StringBuilder sb = new StringBuilder();
		for(int i=1; i<=N; i++) sb.append(result[i]+"\n");
		System.out.println(sb);
	}

}