SWEA 1949 등산로 조성(JAVA) ⛰

구조화

가장 높은 수부터 시작해서 작을 때만 이동 가능

특이케이스) 딱 한번 최대 -K를 해서 이동 가능 -> 1~K까지 빼서 모든 케이스 돌리기

0까지만 가능하고 음수는 안됨

소스 코드

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

public class Solution {

	static class Node{
		/*
		 * x, y 좌표
		 * num 해당 값
		 * flag 깎음 유무
		 */
		int x, y, num;
		boolean flag;
		
		public Node(int x, int y, int num, boolean flag) {
			super();
			this.x = x;
			this.y = y;
			this.num = num;
			this.flag = flag;
		}
		
	}

	static int T, N, K, top, result;
	static int[][] map;
	static boolean[][] visited;
	
	// 상 하 좌 우
	static int[][] way = {{-1,0},{1,0},{0,-1},{0,1}};
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		T = Integer.parseInt(br.readLine());
		
		for (int t = 1; t <= T; t++) 
		{
			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];
			result = Integer.MIN_VALUE;
			top = Integer.MIN_VALUE;
			List<Node> tops = new ArrayList<>();
			
			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());
					// 정상 찾기
					top = Math.max(top, map[i][j]);
				}
			}
			
			for (int i = 0; i < N; i++) 
			{
				for (int j = 0; j < N; j++) 
				{
					if(map[i][j] == top)
					{
						tops.add(new Node(i,j,map[i][j],false));
					}
				}
			}
			
			for (int i = 0; i < tops.size(); i++) 
			{
				visited = new boolean[N][N];
				visited[tops.get(i).x][tops.get(i).y] = true;
				dfs(tops.get(i), 1);
			}
			System.out.printf("#%d %d%n", t, result);
		}

	}
	private static void dfs(Node node, int distance) {
		
		visited[node.x][node.y] = true;
		result = Math.max(result, distance);
		
		for (int i = 0; i < 4; i++) 
		{
			int nx = node.x + way[i][0];
			int ny = node.y + way[i][1];
			
			if(node.flag)
			{
				if(isRight(nx, ny) && !visited[nx][ny])
				{
					// 클 경우만 가능
					if(map[nx][ny]<node.num)
					{
						visited[nx][ny] = true;
						dfs(new Node(nx,ny,map[nx][ny],true), distance+1);
						visited[nx][ny] = false;
					}
				}
			}
			
			else
			{
				if(isRight(nx, ny) && !visited[nx][ny])
				{
					// 클 경우만 가능
					if(map[nx][ny]<node.num)
					{
						visited[nx][ny] = true;
						dfs(new Node(nx, ny, map[nx][ny], false), distance+1);
						visited[nx][ny] = false;
					}
					// 차이값이 
					else 
					{
						for (int j = 1; j <= K; j++) 
						{
							if(!(map[nx][ny]-j<0) && map[nx][ny]-j<node.num)
							{
								visited[nx][ny] = true;
								dfs(new Node(nx, ny, map[nx][ny]-j, true), distance+1);
								visited[nx][ny] = false;
							}
						}
					}
				}
			}
		}
		
	}
	
	private static boolean isRight(int nx, int ny) {
		return (nx>=0 && nx<N && ny>=0 && ny<N);
	}

}