SWEA_1949_[모의 SW 역량 테스]등산로 조성

1

구분: DFS

언어: Java

전략

• 경로를 탐색하는 것이기 때문에 DFS를 이용한다.
• 한번 부술 수 있기 때문에 부순 여부를 늘 확인한다.
• 방문 처리와 해제를 꼭 한다. 
• 등산로는 자를 때 가장 조금만 자른다.

---

2. 코드 

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

public class Solution {
	
	static int n, k, max;
	static int[][] map;
	static boolean[][] visit;


	
	static int[] dx = {0,0,-1,1};
	static int[] dy = {-1,1,0,0};
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		int T = scanner.nextInt();
		
		for(int tc = 1; tc<=T; tc++) {
			n = scanner.nextInt();
			k = scanner.nextInt();
			
			map = new int[n][n];
			visit = new boolean[n][n];
			int high = 0;
			max = Integer.MIN_VALUE;
			
			//가장 높은 지점을 찾는다
			for(int i = 0; i<n; i++) {
				for(int j = 0; j<n; j++) {
					map[i][j] = scanner.nextInt();
					if(map[i][j]>high)
						high = map[i][j];
				}
			}

			//가장 높은 지점이라면 등산로를 조성
			for(int i = 0; i<n; i++) {
				for(int j = 0; j<n; j++) {
					if(map[i][j] == high) {
						dfs(i,j,1,false);
					}
				}
			}
			
			System.out.println("#"+tc+" "+max);
			
			
		}//test
	}//main
	
	//좌표, 길이, 부순 상태
	private static void dfs(int y, int x, int len, boolean state) {
		
		//방문처리
		visit[y][x] = true;
		//긴 등산로 갱신
		max = Math.max(max, len);
		
		//4방 탐색
		for(int d = 0; d<4; d++) {
			int ny = y + dy[d];
			int nx = x + dx[d];
			
			//범위를 벗어나거나 방문되어있으면 그만
			if(!boundCheck(ny, nx)||visit[ny][nx])
				continue;
			
			//나보다 높이가 낮은 경우 - 등산로 조성
			if(map[y][x]>map[ny][nx]) {
				dfs(ny, nx, len+1, state);
			}
			//높이가 같거나 높은 경우 
			else {
				//아직 부순 적이 없고, k만큼 자르면 등산로 조성 가능
				if(!state && map[y][x]>map[ny][nx]-k) {
					
					int temp = map[ny][nx];//복구를 위한 저장
					map[ny][nx] = map[y][x] - 1; //딱 1 만큼만 자른다 - 그래야 최대 길이 등산로 구할 수 있음
					dfs(ny, nx, len+1, true);
					map[ny][nx] = temp;//복구
				}
			}
		}
		//방문처리 해제 
		visit[y][x] = false;
		
	}//dfs
	
	private static boolean boundCheck(int y, int x) {
		if(x<0 || y<0|| x>=n || y>=n)
			return false;
		else
			return true;
	}
}

---

3

경로이기 때문에 DFS를 이용해야 한다는 생각이 어려웠다. 

방문 여부를 재귀함수 시작과 끝에 하다가 오류가 나서 처음과 마지막에만 했다.