[BOJ] 14890 경사로 Java 풀이

 

 

문제 접근 방식은 아래와 같다.

 

• int[][] board : 각 위치의 높이를 저장할 2차원 배열
• boolean[][] isPlaced : 각 위치에 경사로 배치 여부를 저장할 2차원 배열

 

문제에서 길은 행 단위로 N개, 열 단위로 N개 존재해 총 2N개의 길을 검사해야 한다. 따라서 행 단위로 먼저 0행부터 N-1행까지 각 길이 지나갈 수 있는지를 확인하고, 이후 열 단위로 0열부터 N-1열까지 각 길이 지나갈 수 있는지 검사하도록 코드를 작성했다.

 

여기서 유의할 점은 행 단위로 검사하면서 한 위치에 경사로를 넣었더라도, 열 단위로 검사할 때 이전에 행 단위 검사에서 넣은 경사로는 고려하지 않아야 한다. (각 길이 지나갈 수 있는지 여부를 체크하는 것이기 때문) 그래서 행 단위 검사가 끝나고 열 단위 검사를 시작하기 전에, isPlaced 배열은 새로 초기화해준다.

 

먼저, 행 단위 검사 코드는 아래와 같다.

// 행 기준 검사
for(int i = 0; i < N; i++) {
	boolean isPossible = true;
	for(int j = 0; j < N - 1; j++) {
		// 경사가 1 차이나는 지점을 만나면 
		if(Math.abs(board[i][j] - board[i][j + 1]) == 1) {
			// 좌상향 경사로인 경우
			// 경사로를 놓을 수 있는 길이가 부족하거나, 
			if(board[i][j] > board[i][j + 1]) {
				if(j + L > N - 1) {
					isPossible = false;
					continue;
				}
				// 그 길이의 블록에 이미 놓아진 경사로가 이미 있거나, 높이가 1 낮은 블록들이 아니라면 불가
				for(int k = 1; k <= L; k++) {
					if(isPlaced[i][j + k] || board[i][j + k] + 1 != board[i][j]) {
						isPossible = false;
						break;
					}
				}
				if(isPossible) {
					for(int k = 1; k <= L; k++) {
						isPlaced[i][j + k] = true;
					}
				}
			}else {	// 우상향 경사로인 경우
				if(j - L + 1 < 0) {
					isPossible = false;
					continue;
				}
				for(int k = 0; k < L; k++) {
					if(isPlaced[i][j - k] || board[i][j - k] + 1 != board[i][j + 1]) {
						isPossible = false;
						break;
					}
				}
				if(isPossible) {
					for(int k = 0; k < L; k++) {
						isPlaced[i][j - k] = true;
					}
				}
			}
		}else if(Math.abs(board[i][j] - board[i][j + 1]) > 1) {
			isPossible = false;
		}
	}
	// 경사로를 놓을 수 있거나, 모두 높이가 같다면 answer 증가
	if(isPossible) {
		answer++;
	}
}

 

 

• 행, 열 순으로 이중 반복문을 배치해서 높이의 차가 1 차이나면, 경사로를 배치할지 여부를 검사한다. 경사로 배치를 고려할 때는, 오른쪽의 높이가 높은지, 왼쪽의 높이가 높은지를 구분해야 한다. 경사로 배치 방향이 달라지기 때문이다.

 

• 만약 오른쪽의 높이가 높다면, 왼쪽에 경사로를 배치한다. 따라서 경사로의 길이 L만큼 놓을 여유가 있는지를 먼저 검사해보고, 여유가 있다면 경사로를 놓는 그 위치들에 이미 놓은 경사로는 없는지, 또 높이가 일정한지를 확인해야 한다.

 

• 만약 위 모든 조건들을 통과해서 경사로를 놓을 수 있다면, isPlaced 배열에 true 값을 넣어주며 경사로를 놓는다. 

 

위 단계들은 다시 열 단위 검사할 때도 유사하게 적용되므로 약간의 수정만 거쳐서 코드를 추가적으로 작성해주면 된다.

전체 풀이 코드는 아래와 같다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	static int N, L, answer;
	static int[][] board;
	static boolean[][] isPlaced;
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		L = Integer.parseInt(st.nextToken());
		
		board = new int[N][N];
		isPlaced = new boolean[N][N];
		
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < N; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		// 행 기준 검사
		for(int i = 0; i < N; i++) {
			boolean isPossible = true;
			for(int j = 0; j < N - 1; j++) {
				// 경사가 1 차이나는 지점을 만나면 
				if(Math.abs(board[i][j] - board[i][j + 1]) == 1) {
					// 좌상향 경사로인 경우
					// 경사로를 놓을 수 있는 길이가 부족하거나, 
					if(board[i][j] > board[i][j + 1]) {
						if(j + L > N - 1) {
							isPossible = false;
							continue;
						}
						// 그 길이의 블록에 이미 놓아진 경사로가 이미 있거나, 높이가 1 낮은 블록들이 아니라면 불가
						for(int k = 1; k <= L; k++) {
							if(isPlaced[i][j + k] || board[i][j + k] + 1 != board[i][j]) {
								isPossible = false;
								break;
							}
						}
						if(isPossible) {
							for(int k = 1; k <= L; k++) {
								isPlaced[i][j + k] = true;
							}
						}
					}else {	// 우상향 경사로인 경우
						if(j - L + 1 < 0) {
							isPossible = false;
							continue;
						}
						for(int k = 0; k < L; k++) {
							if(isPlaced[i][j - k] || board[i][j - k] + 1 != board[i][j + 1]) {
								isPossible = false;
								break;
							}
						}
						if(isPossible) {
							for(int k = 0; k < L; k++) {
								isPlaced[i][j - k] = true;
							}
						}
					}
				}else if(Math.abs(board[i][j] - board[i][j + 1]) > 1) {
					isPossible = false;
				}
			}
			// 경사로를 놓을 수 있거나, 모두 높이가 같다면 answer 증가
			if(isPossible) {
				answer++;
			}
		}
		
		// 경사로 초기화
		isPlaced = new boolean[N][N];
		
		
		// 열 기준 검사
		for(int j = 0; j < N; j++) {
			boolean isPossible = true;
			for(int i = 0; i < N - 1; i++) {
				// 경사가 1 차이나는 지점을 만나면 
				if(Math.abs(board[i][j] - board[i + 1][j]) == 1) {
					// 경사로를 놓을 수 있는 길이가 부족하거나, 
					if(board[i][j] > board[i + 1][j]) {
						if(i + L > N - 1) {
							isPossible = false;
							continue;
						}
						// 그 길이의 블록에 이미 놓아진 경사로가 이미 있거나, 높이가 1 낮은 블록들이 아니라면 불가
						for(int k = 1; k <= L; k++) {
							if(isPlaced[i + k][j] || board[i + k][j] + 1 != board[i][j]) {
								isPossible = false;
								break;
							}
						}
						if(isPossible) {
							for(int k = 1; k <= L; k++) {
								isPlaced[i + k][j] = true;
							}
						}
					}else {	
						if(i - L + 1 < 0) {
							isPossible = false;
							continue;
						}
						for(int k = 0; k < L; k++) {
							if(isPlaced[i - k][j] || board[i - k][j] + 1 != board[i + 1][j]) {
								isPossible = false;
								break;
							}
						}
						if(isPossible) {
							for(int k = 0; k < L; k++) {
								isPlaced[i - k][j] = true;
							}
						}
					}
				}else if(Math.abs(board[i][j] - board[i + 1][j]) > 1) {
					isPossible = false;
				}
			}
			// 경사로를 놓을 수 있거나, 모두 높이가 같다면 answer 증가
			if(isPossible) {
				answer++;
			}
		}
		System.out.println(answer);
	} // end of main
}