[swexpert] 1949. 등산로 조성 (java, dfs)

높이를 깎아서 다른 높이를 전달할 수 있다

=> 같은 위치더라도 다른 높이로 들어온다. 방문정보를 어떻게 전달할 지 몰라서 방문 처리가 어려워 dfs로 했다

 

package algo0424;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Pos{
	int y,x;
	int cut;
	int	num;
	int len;

	public Pos(int y, int x,int cut,int num,int len) {
		super();
		this.y = y;
		this.x = x;
		this.cut=cut;
		this.num=num;
		this.len=len;
	}
	
}

public class S_1949_등산로조성_Solution {
	static int t,n,k;//최대 공사 가능한 깊이
	static int[][] map;
	static boolean[][]vis;
	static int high;
	static int[] xpos= {0,0,1,-1};
	static int[] ypos= {1,-1,0,0};
	static int answer;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		t=sc.nextInt();
		for (int tc = 1; tc <=t; tc++) {
			n=sc.nextInt();
			k=sc.nextInt();
			map=new int[n][n];
			high=0;
			answer=Integer.MIN_VALUE;
			vis=new boolean[n][n];
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					map[i][j]=sc.nextInt();
					if(map[i][j]>high)high=map[i][j];
				}
			}

			bfs();
			System.out.printf("#%d %d\n",tc,answer);
		}
	}
	private static void bfs() {
		
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if(map[i][j]==high) {
					dfs(i,j,false,1,map[i][j]);
				}
			}

		}
	}
	private static void dfs(int y, int x, boolean isCut, int len,int height) {
		vis[y][x]=true;
		answer=Math.max(answer, len);
		
		for (int p = 0; p <4; p++) {
			int yy=y+ypos[p];
			int xx=x+xpos[p];
			if(yy<0 || xx<0|| yy>=n || xx>=n)continue;
			if(vis[yy][xx])continue;
			
			if(map[yy][xx]<height) {
				dfs(yy,xx,isCut,len+1,map[yy][xx]);
			}else if(isCut==false) {
				for (int i = 1; i <=Math.min(k, map[yy][xx]); i++) {
					if(map[yy][xx]-i<height) {
						dfs(yy,xx,true,len+1,map[yy][xx]-i);
					}
				}
			}
		}
		vis[y][x]=false;
	}
		
		
}