OJ

[SWEA] 1949 등산로 조성 (JAVA)

P3PP4 2022. 8. 27. 00:38

 

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

 

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

visited 배열을 사용하지 않고 제출하면 테케가 몇 개 틀리네요

이미 지나온 등산로는 공사하면 높이의 변화가 생기기 때문에 안되겠죠?

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

public class SWEA_1949 {
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	static int T, N, K, max, longest;
	static int[] dr = { -1,  0,  1,  0 };
	static int[] dc = {  0,  1,  0, -1 };
	static boolean[][] visited;
	
	public static void main(String[] args) throws IOException {
		
		T = Integer.parseInt(br.readLine());
		
		for (int tc = 1; tc <= T; tc++) {

			max = 0;		// 해당 부지에서 최대 높이가 몇인지 저장할 변수
			longest = 0;	// 등산로 최고 길이를 저장할 변수
			st = new StringTokenizer(br.readLine(), " ");
			N = Integer.parseInt(st.nextToken());	// 부지 크기
			K = Integer.parseInt(st.nextToken());	// 공사 가능한 최대 깊이
			int map[][] = new int[N][N];
			visited = new boolean[N][N];
			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(map[i][j] > max) {
						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;
						findPath(map, i, j, 1, true);
						visited[i][j] = false;
					}
				}
			}
			
			sb.append("#").append(tc).append(" ").append(longest).append("\n");
			
		}
		
		System.out.println(sb.toString());
		
	}
	
	// available은 공사가 가능한지 알려주는 매개변수
	static void findPath(int[][] map, int i, int j, int length, boolean available) {
		
		// 현재 최고 길이보다 지금 등산로 길이가 더 길면 갱신
		if(length > longest) longest = length;
		
		// 4방 탐색
		for (int dir = 0; dir < 4; dir++) {
			
			int nextR = i + dr[dir];
			int nextC = j + dc[dir];
			
			if(0 <= nextR && nextR < N && 0 <= nextC && nextC < N) {
				
				// 다음 위치의 높이가 현재 위치보다 낮으면 등산로로 추가 가능
				if(map[nextR][nextC] < map[i][j]) {
					
					visited[nextR][nextC] = true;
					findPath(map, nextR, nextC, length + 1, available);
					visited[nextR][nextC] = false;
					
				// 다음 위치의 높이가 현재 위치보다 낮지 않으면, 
				// 공사가 가능해야 하고 최대 깊이로 공사했을 때 지금 위치의 높이보다 낮아야 한다
				} else if(!visited[nextR][nextC] && available && map[nextR][nextC] - K < map[i][j]){
					
					int height = 1;		// 얼마나 땅을 파야 현재 위치보다 낮아질지 1부터 파봄
					int temp = map[nextR][nextC];	// 원래 다음 위치의 높이를 저장해둠
					
					// 최대 공사 가능 깊이까지 height를 늘려가며
					while(height <= K) {
						
						// 지금 height만큼 공사하면 다음 위치가 현재 위치보다 더 낮아지는가?
						if(map[nextR][nextC] - height < map[i][j]) {
														
							map[nextR][nextC] -= height;
							visited[nextR][nextC] = true;
							findPath(map, nextR, nextC, length + 1, false);
							map[nextR][nextC] = temp;
							visited[nextR][nextC] = false;
							break;
							
						} else height++;
						
					}
					
				}
				
			}
			
		}
		
	}

}