[삼성 SW Expert Academy] 등산로 1949[JAVA]

Problem

※ SW Expert Academy는 문제의 무단 복제를 금지하고 있기 때문에, 기재하지 못한 점 양해 부탁드립니다.

Link

※ 하단의 Link를 클릭해도, 로그인 후 열람이 가능합니다.

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PoOKKAPIDFAUq

SW Expert Academy

풀이

1.  DFS

2. 

 

코드

import java.util.Arrays;
import java.util.Scanner;

public class 등산로조정_SW1949 {

	static int N; //맵의 크기
	static int K; // 최대 깔 수 있는 땅 깊이
	static int[][] map;
	static boolean[][] visited;
	static int[] dr = {-1, 1, 0, 0};
	static int[] dc = {0, 0, -1, 1};
	static int answer;
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int Tc = sc.nextInt();
		
		for( int tc =1; tc<=Tc ; tc++) {
			
			N = sc.nextInt();
			K = sc.nextInt();
			
			map = new int[N][N];
			visited = new boolean[N][N];
			
			answer = Integer.MIN_VALUE;
			int max = Integer.MIN_VALUE; 
			for( int i=0; i<N; i++) {
				for( int j=0; j<N; j++) {
					map[i][j] = sc.nextInt();
					max = Math.max(map[i][j], max);
				}
			}
			
			for( int i=0; i<N; i++) {
				for( int j=0; j<N; j++) {
					
					if( map[i][j] == max ) {
						//visited[i][j]= true;
						dfs( i, j, false, 1, map[i][j]);
						
					}
				}
			}
			
			
			
			System.out.println("#"+tc+" "+answer);
		}
		
	}
	
	private static void dfs(int r, int c, boolean drill, int count, int Cur_height) {
		// 방문처리하고
		visited[r][c] = true;
		// 현재 몇번왔는지 최대값 기억
		if( count > answer ) answer = count;

		// 4방향에 대해서 
		 
		for( int d=0; d<4; d++) {
			
			int nr = r+dr[d];
			int nc = c+dc[d];
			
			if( !IsIn(nr,nc) || visited[nr][nc] ) continue;
			
			// 현재위치보다 다음 위치가 더 낮으면 그냥 ㄱㄱ
			if( Cur_height > map[nr][nc] ) {
				dfs( nr, nc, drill, count+1, map[nr][nc]);
			}
			
			// 높이가 작지 않지만, K만큼 깎을수 있으면 , 이미 drill 사용하지 않았다면
			if ( Cur_height <= map[nr][nc] && map[nr][nc]-K < Cur_height && !drill) {
				dfs( nr, nc, true, count+1, Cur_height-1);
			}			
//			else if ( map[nr][nc]-K < Cur_height && !drill) {
//				dfs( nr, nc, true, count+1, Cur_height-1);
//			}			
		}
		// 현재위치 안온것으로
		visited[r][c] = false;
	}
	
	private static boolean IsIn(int r, int c) {
		if( r>=0 && r<N && c>=0 && c<N) return true;
		
		return false;
	}
	
	
}