[SWEA] 1949. 등산로 조성
24431 단어 DFSBacktrackingSWEA알고리즘Backtracking
문제
1949. [모의 SW 역량테스트] 등산로 조성
제일 긴 등산로의 길이를 반환하라!
- 높이 : [1, 20]
- 가장 높은 곳들에서 시작
- 현재 높이보다 작은 높이로만 이동 가능
- 한 번 최대 K깊이만큼 산을 깎을 수 있음 (⭐️ 깎았을 때 높이가 0이 되는 것은 허용)
풀이
가장 높은 지형들에서 DFS()를 호출하여 가장 긴 등산로를 찾는다.
if (map[nx][ny] < start.h) { // 현재보다 낮은 곳
DFS(new Pair(nx, ny, map[nx][ny]), isCutted, length+1);
}
else { // 산을 깎을 수 있는가?
if (isCutted == false && (map[nx][ny]-start.h)<k)
DFS(new Pair(nx, ny, start.h-1), true, length+1);
}
- DFS로 구현했다.
- 좌표를 기록할 Pair 클래스를 구현했다.
- 산을 깎았을 때
map[][]
의 값을 바꾸지 않기 위해서 현재 높이를 기록한다.
- 산을 깎았을 때
- 재귀호출할 때 산을 깎았는지 여부(
isCutted
)를 넘겨주었다.- 다음 지형이 현재보다 지형이 높다면, 아직 깎지 않았고(
isCutted==false
) 깎을 높이가 k보다 작을 때 산을 깎고 이동할 수 있다. (->isCutted
를 true로 넘겨줌)
- 다음 지형이 현재보다 지형이 높다면, 아직 깎지 않았고(
- 재귀호출하면 다른 지형으로 이동한 것이므로 length값을 1 올려준다.
- 다음 지형이 현재보다 높고, 산도 깎을 수 없으면 되돌아가서 다음 곳을 찾으므로 백트래킹이다.
자바코드
import java.util.Scanner;
import java.io.FileInputStream;
class Solution
{
static class Pair {
int x;
int y;
int h; // height
Pair() {}
Pair(int x, int y, int h) {this.x=x; this.y=y; this.h=h;}
}
static int k=0;
static int n=0;
static int [][] map = new int[8][8];
static boolean [][] isVisited = new boolean [8][8];
static int maxLength = 0;
static int [] dx = {-1, 0, 1, 0};
static int [] dy = {0, -1, 0, 1};
public static void main(String args[]) throws Exception
{
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for(int test_case = 1; test_case <= T; test_case++)
{
n = sc.nextInt();
k = sc.nextInt();
int max=0;
map = new int[n][n];
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
// Load map
map[i][j] = sc.nextInt();
if (map[i][j] > max) max = map[i][j];
// init visited
isVisited[i][j] = false;
}
}
// 가장 높은곳에서부터 등산로 탐색
maxLength = 0;
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if (map[i][j] == max) {
DFS(new Pair(i, j, map[i][j]), false, 1);
}
}
}
System.out.printf("#%d %d\n", test_case, maxLength);
}
}
static void DFS(Pair start, boolean isCutted, int length) {
int nx, ny;
isVisited[start.x][start.y] = true;
if (length > maxLength) maxLength = length;
for (int d=0; d<4; d++) {
nx = start.x+dx[d];
ny = start.y+dy[d];
// 영역 밖 또는 이미방문
if(nx<0||nx>=n||ny<0||ny>=n||isVisited[nx][ny]) continue;
isVisited[nx][ny] = true;
if (map[nx][ny] < start.h) { // 현재보다 낮은 곳
DFS(new Pair(nx, ny, map[nx][ny]), isCutted, length+1);
}
else { // 산을 깎을 수 있는가?
if (isCutted == false && (map[nx][ny]-start.h)<k)
DFS(new Pair(nx, ny, start.h-1), true, length+1);
}
isVisited[nx][ny] = false;
}
isVisited[start.x][start.y] = false;
}
}
틀렸던 부분
- DFS에서 다음 지형이 영역 밖으로 나갔는 지 확인할 때,
nx<=0
으로 했었다..ㅎ ! ! - 깎았을 때도 높이가 1 이상이어야 되는 줄 알았다. (문제를 잘 읽자^^)
Author And Source
이 문제에 관하여([SWEA] 1949. 등산로 조성), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@euzl/SWEA-1949.-등산로-조성저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)