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++;
}
}
}
}
}
}