[Java] 백준14890 - 경사로

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

14890번: 경사로

 

생각보다 너무 어려웠던..문제.. 생각해야하는 경우가 너무 많다.

 

일단 행과 열 각각 따로따로 탐색해야 하는데, 좌→우 / 우→좌든 상→하/하→상이든 상관없다. 

(어차피 오르막이랑 내리막 조건이 같기 때문)

 

문제에 나와있는 조건에 맞게 길 탐색만 하면 나머지는 상관없다.

1. 다음칸이 같은 높이면 그냥 전진

2. 다음칸이 1칸 낮은 경우,  다다음칸이 똑같이 1칸 낮은지 확인 후 전진 (내리막 사용가능)

- 이 때, slope를 이미 놨다는 의미로 boolean[][] 2차원 배열의 값을 true로 설정

- 다다음칸이 없거나 다른 값이면 전진 불가 -> false 리턴

3. 다음칸이 1칸 높은 경우, 이전 칸이 현재 칸과 같은 높이인지 확인 후 전진 (오르막 사용 가능)

- 이 때, slope가 이미 놓여있으면(boolean[][] 2차원 배열이 true일 경우) 못 올라감 ! -> false 리턴

 

대충 이런 식으로 구현해줬다.

오르막이랑 내리막만 잘 신경써주면 될듯!

package BOJ_SS;

import java.util.*;

public class boj14890 {
	static int n, l, cnt=0;
	static int[][] map;
	static boolean[][] hasSlope;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
	    n = sc.nextInt();
	    l = sc.nextInt();
	    map = new int[n][n];
	    
	    
	    for(int i=0; i<n; i++)
	    	for(int j=0; j<n; j++)
	    		map[i][j] = sc.nextInt();
	    
	    for(int i=0; i<n; i++) {
	    	hasSlope = new boolean[n][n];
	    	if(checkPath(0,i)) 
	    		cnt++;
	    
	    	hasSlope = new boolean[n][n];
	    	if(checkPath(1,i)) 
	    		cnt++;
	    }
	    
	    System.out.println(cnt);
	}
	
	
	public static boolean checkPath(int dir, int i) {
		switch(dir) {
		//좌->우
		case 0:{
			int num = map[i][0];
			for(int j=1; j<n; j++) {
	    		if(map[i][j]==num)
	    			continue;
	    		//오르막
	    		if(map[i][j]==num+1 && j>=l) {
	    			num = map[i][j];
	    			if(checkUpSlope(dir, num-1, i, j-1))
	    				continue;
	    			return false;
	    		}
	    		//내리막
	    		if(map[i][j]==num-1 && j+l<=n) {
	    			num = map[i][j];
	    			if(checkDownSlope(dir, num, i, j))
	    				continue;
	    			return false;
	    		}
	    		return false;
	    	}
			return true;
		}
		//상->하
		case 1:{
			int num = map[0][i];
			for(int j=1; j<n; j++) {
				if(map[j][i]==num)
	    			continue;
	    		//오르막
	    		if(map[j][i]==num+1 && j>=l) {
	    			num = map[j][i];
	    			if(checkUpSlope(dir, num-1, i, j-1))
	    				continue;
	    			return false;
	    		}
	    		//내리막
	    		if(map[j][i]==num-1 && j+l<=n) {
	    			num = map[j][i];
	    			if(checkDownSlope(dir, num, i, j))
	    				continue;
	    			return false;
	    		}
	    		return false;
			}
			return true;
		}
		}
		return false;
	}
	
	public static boolean checkUpSlope(int dir, int num, int i, int idx) {
		switch(dir) {
		case 0:{
			for(int j=idx; j>idx-l; j--) {
				if(hasSlope[i][j])
					return false;
				if(map[i][j]!=num)
					return false;
			}
			
			for(int j=idx; j>idx-l; j--) {
				hasSlope[i][j]=true;
			}
			
			return true;
		}
		case 1:{
			for(int j=idx; j>idx-l; j--) {
				if(hasSlope[j][i])
					return false;
				if(map[j][i]!=num)
					return false;
			}
			
			for(int j=idx; j>idx-l; j--) {
				hasSlope[j][i]=true;
			}
			
			return true;
		}
		}
		
		return false;
	}
	
	public static boolean checkDownSlope(int dir, int num, int i, int idx) {
		switch(dir) {
		case 0:{
			for(int j=idx; j<idx+l; j++) {
				if(hasSlope[i][j])
					return false;
				if(map[i][j]!=num)
					return false;
			}
			for(int j=idx; j<idx+l; j++) {
				hasSlope[i][j]=true;
			}
			return true;
		}
		case 1:{
			for(int j=idx; j<idx+l; j++) {
				if(hasSlope[j][i])
					return false;
				if(map[j][i]!=num)
					return false;
			}
			for(int j=idx; j<idx+l; j++) {
				hasSlope[j][i]=true;
			}
			return true;
		}
		}
		
		return false;
	}
}