알고리즘매일매일

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

이 문제는 갈 수 있는 최대 길이를 구하는 문제이므로 dfs를 이용해서 풀 수 있다.

dfs의 depth가 문제의 최대 길이가 된다.

풀이

1. 입력받은 지형의 높이 중 가장 높은 높이를 저장해 놓는다.

2. 해당 높이를 가지고 있는 지형(가장 높은 봉우리)의 좌표를 벡터에 저장한다.

3. 가장 높은 봉우리로부터 출발할 수 있으므로 위에서 저장한 좌표에서 각각 출발해본다.

4. 출발할 때는, 모든 칸을 0번부터 k번까지 깎아보는 모든 경우에서 출발(dfs탐색)한다. 해당 칸을 깎은 경우에서 돌아온다면 깎은 만큼 다시 더해준다. (1칸만 깎을 수 있으므로)

5.dfs탐색을 할 때는 문제 조건에 따라 이동할 칸이 현재 지형보다 더 낮아야 이동할 수 있고, 다음 칸으로 이동할 때마다 길이를 하나씩 늘려준다.

문제

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

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

예전에 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;
	}

}