[SWEA] 1949. 등산로 조성

문제

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

SW Expert Academy

지도의 한 변의 길이 N은 3 이상 8 이하의 정수이다. (3 ≤ N ≤ 8)
최대 공사 가능 깊이 K는 1 이상 5 이하의 정수이다. (1 ≤ K ≤ 5)
지도에서 가장 높은 봉우리는 최대 5개이다.
-> 이 조건들을 통해 완전 탐색을 해도 되겠다고 생각했다.

 

 

 

위가 DFS, 아래가 DFS

예전에 BFS로 길이를 배열에 저장해가며 풀었다가 메모리를 너무 많이 사용해서 DFS로 다시 풀었다.

DFS로 푸는 게 최대 depth를 저장하면 되므로 BFS보다 더 효율적인 듯하다.

BFS로도 잘 처리해주면 될 것 같지만 문제 맥락상(?) DFS가 더 맞는 것 같다.

문제를 잘 생각하고 알고리즘 사용하자!!

 

풀이

1. 값을 처음에 입력받으면서 가장 큰 값을 top 변수에 저장한다.
2. 배열을 탐색하며 top값과 같은 곳의 좌표를 ArrayList에 저장한다.
3. 모든 위치에 대해서 0번에서 K번 깎는 경우까지 모든 길이를 구해서 최댓값을 max에 저장한다.
4. max 출력.

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

public class Solution {
	static class Pair {
		int x;
		int y;
		Pair(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
    
	static int[] dx = {0,0,1,-1};
	static int[] dy = {1,-1,0,0};
	static int N, K, max;
	static int[][] map;
	static boolean[][] check;
	static ArrayList<Pair> topList;
    
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for(int tc=1; tc<=T; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());
			map = new int[N][N];
			topList = new ArrayList();
			
			int top = 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());
					if(top < map[i][j]) top = map[i][j];
				}
			}
			
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					if(map[i][j] == top) topList.add(new Pair(i,j));
				}
			}
            
			max = 0;
			construct();
			System.out.println("#"+tc+" "+max);
		}
	}
	
	static void construct() {
		for(int k=0; k<=K; k++) {
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					map[i][j] -= k;
					for(int l=0; l<topList.size(); l++) { //가장 높은 봉우리들에서부터 경로 탐색
						int x = topList.get(l).x;
						int y = topList.get(l).y;
						if(x == i && y == j) continue; //현재 탐색할 가장 높은 봉우리를 공사한 경우
						check = new boolean[N][N];
						check[x][y] = true;
						int tmp = dfs(x,y,1);
						if(tmp > max) max = tmp;
						
					}
					map[i][j] += k;
				}
			}
		}
	}
	
	static int dfs(int x, int y, int depth) {
		int d = depth;
        
		for(int i=0; i<4; i++) {
			int nx = x+dx[i];
			int ny = y+dy[i];
			if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
			if(check[nx][ny]) continue;
			if(map[nx][ny] >= map[x][y]) continue;
            
			check[nx][ny] = true;
			d = Math.max(d,dfs(nx,ny,depth+1));
			check[nx][ny] = false;
			
		}

		return d;
	}

}