SWEA [모의 SW 역량테스트] 등산로 조성

 

package swea;

import java.util.*;
import java.io.*;

public class 등산로조성 {
	public static class MyScanner {
		BufferedReader bf;
		StringTokenizer st;

		MyScanner() {
			bf = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(bf.readLine());
				} catch (Exception e) {
					e.printStackTrace();
				}

			}
			return st.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

		public char nextChar() {
			return next().charAt(0);
		}
	}

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("res/등산로.txt"));
		MyScanner sc = new MyScanner();

		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			int N = sc.nextInt();
			int K = sc.nextInt();
			int maxHeight = 0;
			ArrayList<int[]> heights = new ArrayList<int[]>();

			int map[][] = new int[N][N];
			int answer = 0;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					int h = sc.nextInt();
					map[i][j] = h;
					if (maxHeight == h)
						heights.add(new int[] { i, j });
					else if (maxHeight < h) {
						maxHeight = h;
						heights.clear();
						heights.add(new int[] { i, j });
					}
				}
			}
			Queue<int[]> q = new LinkedList<int[]>();
			for (int[] point : heights) {
				q.add(new int[] { point[0], point[1], map[point[0]][point[1]], 1, 0 });// x y 길이 여부
			}
			int dx[] = { -1, 1, 0, 0 };
			int dy[] = { 0, 0, -1, 1 };
			while (!q.isEmpty()) {

				int now[] = q.poll();
				answer = Math.max(answer, now[3]);
				for (int i = 0; i < 4; i++) {
					int nx = now[0] + dx[i];
					int ny = now[1] + dy[i];
					if (nx < 0 || nx >= N || ny < 0 || ny >= N)
						continue;
					int nh = map[nx][ny];
					int nt = now[3] + 1;
					int cut = now[4];
		

					if (nh >= now[2]) {
						if (cut >= 1)
							continue;
						else {
							cut++;
							for (int j = 1; j <= K && nh - j >= 0; j++) {
								if (nh - j >= now[2])
									continue;
								q.add(new int[] { nx, ny, nh - j, nt, cut});
							}
						}
					} else {
						q.add(new int[] { nx, ny, nh, nt, cut});
					}
				}

			}

			System.out.println("#" + tc + " " + answer);
		}
	}

}

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PoOKKAPIDFAUq&categoryId=AV5PoOKKAPIDFAUq&categoryType=CODE

SW Expert Academy

 

 

등산로를 조성하려고 한다.

등산로를 만들기 위한 부지는 N * N 크기를 가지고 있으며, 이곳에 최대한 긴 등산로를 만들 계획이다.

등산로 부지는 아래 [Fig. 1]과 같이 숫자가 표시된 지도로 주어지며, 각 숫자는 지형의 높이를 나타낸다.

 

등산로를 만드는 규칙은 다음과 같다.

   ① 등산로는 가장 높은 봉우리에서 시작해야 한다.

   ② 등산로는 산으로 올라갈 수 있도록 반드시 높은 지형에서 낮은 지형으로 가로 또는 세로 방향으로 연결이 되어야 한다.
       즉, 높이가 같은 곳 혹은 낮은 지형이나, 대각선 방향의 연결은 불가능하다.

   ③ 긴 등산로를 만들기 위해 딱 한 곳을 정해서 최대 K 깊이만큼 지형을 깎는 공사를 할 수 있다.

N * N 크기의 지도가 주어지고, 최대 공사 가능 깊이 K가 주어진다.

이때 만들 수 있는 가장 긴 등산로를 찾아 그 길이를 출력하는 프로그램을 작성하라.

 

 

 

 

 

 

N<=8이기 때문에 완전탐색으로 이용하여 문제를 풀수 있는 문제다.

반드시 상하좌우로만 이동할수 있고, 높은 지형에서 낮은 지형으로만 이동할 있고, 또 등산로조성을 위해 한번만 산을 깎을수 있다.

그러므로 BFS에서 사용될 큐에 x,y 좌표정보뿐만 아니라 현재 지점의 높이, 이 경로에서 등산로를 깎았는 지를 체크해야한다.

또 가장 높은 지점에서만 시작할수 있으므로 입력을 받을때 가장 높은 지점만 시작점으로 큐에 저장해줘야한다.