[SWEA] 1949. [모의 SW 역량테스트] 등산로 조성 - Java

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

SW Expert Academy

---

1. 문제 요약

NxN크기 map이 주어진다.

등산로는 가장 높은 봉우리에서 시작되며, 사방탐색으로 높이가 작은 좌표로만 이동할 수 있다.

딱 한 곳은 K높이 이하 만큼 깎는 공사를 할 수 있다.

이 때 만들 수 있는 가장 긴 등산로를 출력한다.

 

2. 풀이

dfs로 풀었다. 

1. 최대 높이는 입력받을 때 갱신해주었다.

2. 가장 높은 위치는 큐에 좌표 저장한다.

3. 해당 좌표로 갈 수 있는 모든 길을 탐색한다. => dfs

   - 범위 안에 들 경우,

        - 다음 위치의 높이가 현재 높이보다 작으면 dfs 돌러 간다

        - 다음 위치의 높이가 현재 높이보다 크거나 같으면,

            공사를 하지 않았고, 두 높이의 차가 K보다 작다면 높이를 깎아 현재높이-1 로 만들고 dfs를 돈다.

* 방문한 지점은 visited를 true로해주고, dfs가 끝나면 다른 경로로도 가봐야하므로 visited를 false로 원복시킨다.

 

내가 놓친 부분은, 시작점을 visited해주지 않았다.

경로를 쭉 탐색하다가 시작점을 만났을 때, K만큼 깎아보고 깎이면 dfs를 도는 경우가 발생해서 문제가 되었다.

시작지점도 앞 뒤로 visited 체크를 해주니 통과하였다.

 

3. 코드

package a22_11_08;

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

public class SW_1949_등산로조성 {

	static int N, K, ans, max;
	static int[][] map;
	static boolean[][] visited;
	static Queue<Pos> starts;
	
	static int[] dy= {-1,1,0,0};
	static int[] dx= {0,0,-1,1};
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		int T = Integer.parseInt(br.readLine());
		
		for (int tc=1; tc<=T; tc++) {
			
			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];
			starts = new ArrayDeque<> ();
			
			max = 0;
			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());
					max = Math.max(max, map[i][j]);
				}
			} //입력 끝
			
			for (int i=0; i<N; i++) {
				for (int j=0; j<N; j++) {
					if (map[i][j] == max) {
						starts.offer(new Pos(i, j));
					}
				}
			} //시작점 셋팅
			
			ans = 0;
			solution();
			System.out.println("#"+tc+" "+ans);
		}
	}
	
	static void solution() {
		while (!starts.isEmpty()) {
			Pos start = starts.poll();
			visited[start.y][start.x] = true;
			dfs(start.y, start.x, 1, false, max);
			visited[start.y][start.x] = false;
			
		}
	}
	
	static void dfs(int y, int x, int dep, boolean used, int now) {
		ans = Math.max(ans, dep);
		for (int d=0; d<4; d++) {
			int ny = y+dy[d];
			int nx = x+dx[d];
			if (ny<0||ny>=N||nx<0||nx>=N||visited[ny][nx]) continue;
			
			if (map[ny][nx] < now) {
				visited[ny][nx] = true;
				dfs(ny, nx, dep+1, used, map[ny][nx]);
				visited[ny][nx] = false;
			} else {
				if (used == false) {
					if (map[ny][nx] - now < K) {
						visited[ny][nx] = true;
						dfs(ny, nx, dep+1, true, now-1);
						visited[ny][nx] = false;
					}
				}
			}
			
		}
		
	}
	
	static class Pos {
		int y, x;
		Pos(int y, int x) {
			this.y = y;
			this.x = x;
		}
	}
}