[Java] swea 1949 등산로조성

[Java] swea 1949 등산로조성

 

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PoOKKAPIDFAUq&categoryId=AV5PoOKKAPIDFAUq&categoryType=CODE&problemTitle=sw&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=2

SW Expert Academy

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {
	static int N, K, MAX;
	static int[][] map;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine());
		for (int testcase = 1; testcase <= T; testcase++) {
			MAX = 0;
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());

			map = new int[N][N];
			visited = new boolean[N][N];
			int max = 0;
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < N; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
					if (max < map[i][j])
						max = map[i][j];
				}
			}

			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (map[i][j] == max) {
						visited[i][j] = true;
						solve(false, i, j, 1);
						visited[i][j] = false;
					}
				}
			}

			System.out.println("#" + testcase + " " + MAX);
		} // tc

	} // main

	static int[][] dir = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
	static boolean[][] visited;

	private static void solve(boolean isUse, int x, int y, int cnt) {
		if (MAX < cnt)
			MAX = cnt;

		for (int d = 0; d < 4; d++) {
			int nx = x + dir[d][0];
			int ny = y + dir[d][1];

			if (isInBound(nx, ny) && !visited[nx][ny]) {
				int val = map[nx][ny];
				if (map[x][y] > val) {
					visited[nx][ny] = true;
					solve(isUse, nx, ny, cnt + 1);
					visited[nx][ny] = false;
				} else {
					if (!isUse) {
						int i = 0;
						while (i < K) {
							i++;
							map[nx][ny]--;
							if (map[nx][ny] < 0)
								break;
							if (map[x][y] > map[nx][ny]) {
								visited[nx][ny] = true;
								solve(true, nx, ny, cnt + 1);
								visited[nx][ny] = false;
							}
						} // while
						map[nx][ny] += i;
					}
				}
			}
		} // d

	} // solve

	static boolean isInBound(int x, int y) {
		if (x < 0 || x >= N || y < 0 || y >= N)
			return false;
		return true;
	}
}

 

제일 높은 곳에서 등산로를 시작할 수 있으므로 input 받을 때 max 를 찾아서 배열 순회하면서 max 값인 경우에만 함수 호출한다.

 

solve 는 한 번 깎을 수 있는 기회를 썼는 지 안 썼는 지 저장하는 isUse, 현재까지 등산로 길이 cnt, 그리고 현재 땅 x, y 를 매개변수로 들고다닌다.

 

solve를 처음 들어오면 현재까지 지나온 길 cnt 와 MAX 와 비교하여 MAX 를 갱신한다.

 

현재 위치 (x, y)에서 상하좌우 4방향으로 다 가보는데, 

이미 방문했거나 내가 있는 땅보다 낮은 지형은 visited = true로 표시해주고 solve()를 들어간다.

solve 나와서는 visited=  false 로 바꿔서 다른 재귀에서 영향 받지 않도록!!!!! 하는 게 중요하다.

 

만약 이동하려고 하는 땅이 내가 있는 땅보다 높거나 같아서 못가는데 아직 깎은 적 없으면(즉 isUse가 false이면) 1부터 K만큼 한 번씩 다 깎아서 solve에 들어가본다.

map[nx][ny]를 깎아서 solve 다 들어가보고

while 이 끝나면 깎은 만큼 +i해서 돌려놓는다!!!!

while 들어가자마자 i를 +1하고 그 밑에 if 문으로 0보다 작을 경우 break 하므로

무조건 깎은 만큼 다시 되돌려진다.