[알고리즘] 백준14890 경사로 - 자바

https://www.acmicpc.net/problem/14890

14890번: 경사로

 

[풀이 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_14890_경사로 {
	static int N, L, ans;
	static int[][] map;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = parse(st.nextToken());
		L = parse(st.nextToken());
		
		map = new int[N][N];
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				map[i][j] = parse(st.nextToken());
			}
		}
		
		for(int i=0; i<N; i++) {
			dfs(map[i], 0, 1); // 행 검사
			
			int[] arr = new int[N]; // 열 일차원 배열로 만들어주기
			for(int j=0; j<N; j++) {
				arr[j] = map[j][i];
			}
			dfs(arr, 0, 1); // 열 검사
			
		}
		System.out.println(ans);
	}
	
	private static void dfs(int[] arr, int idx, int cnt) {
		if(idx == N-1) {
			ans++;
			return;
		}
		
		if(idx >= N) {
			return;
		}
		
		if(arr[idx] == arr[idx+1]) { // 평지
			dfs(arr, idx+1, cnt+1);
		}
		if(arr[idx] - arr[idx+1] == -1 && cnt >= L) { // 오르막
			dfs(arr, idx+1, 1);
		}
		if(arr[idx] - arr[idx+1] == 1 ) { // 내리막
			if(idx+L < N && check(arr, idx)) { // 내리막 갈 수 있는지 여부 체크하는 함수
				dfs(arr, idx+L, 0);
			}
		}
		
	}

	private static boolean check(int[] arr, int idx) {
		int temp = arr[idx]-1; // 한칸 아래
		for(int l=1; l<=L; l++) {
			if(arr[idx+l] != temp) return false;
		}
		return true;
	}
	

	private static int parse(String str) {
		return Integer.parseInt(str);
	}

}

• 코드를 다 작성하고 나니까 dfs() 함수를 한 번만 쓰고 싶었는데 스터디원이 리팩터링을 해주신 걸 참조했다. 일차원 배열만 dfs에 넣어주면 되도록 작성했다.

 

[풀이 로직]

dfs함수에 들어가는 파라미터는 일차원 배열, idx, cnt이다. idx는 한칸한칸 앞으로 가기 위함이고 cnt변수는 오르막 길을 가기 위해 현재 위치한 곳에 도달하기까지를 몇 칸을 왔는지 넣어주었다.

dfs함수 내에서 세가지의 조건문으로 나눠 작성했다.

• 평지로 가는 경우
  
  
• 오르막길로 가는 경우
  cnt변수가 L보다 같거나 크면 갈 수 있으니 idx+1(한 칸 위로), cnt(변수를 1로 초기화해서 다시 dfs() 함수 수행
  
  
• 내리막길로 가능 경우
  cnt변수가 필요 없다. 내리막의 경우는 앞을 내다봐야 되기 때문에 따로 check() 함수를 만들어서 현재 위치한 곳부터 L까지의 거리를 탐색했다.