[백준] 14890 경사로 (Java)

[14890 경사로]

난이도: 골드3

14890번: 경사로

문제

입력

출력

---

[아이디어]

단순한 구현 문제이다.

문제 설명대로 코드를 짜주면 되는데 경사로가 겹치게 놓이면 안된다는 것이 가장 까다롭다. 따라서 나는 경사로가 이미 놔져있는가를 체크하는 배열을 따로 써줬다.

그리고 열방향 탐색의 함수를 따로 만들지 않고, 열을 행으로 변환하여 하나의 함수를 재활용 하였다.

---

[JAVA 코드]

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

public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	
	static int N, L, cnt;
	static int [][] map;

	public static void main(String[] args) throws IOException {
		tokens = new StringTokenizer(br.readLine());
		N = Integer.parseInt(tokens.nextToken());
		L = Integer.parseInt(tokens.nextToken());
		
		map = new int [N][N];
		for(int r = 0; r < N; r++) {
			tokens = new StringTokenizer(br.readLine());
			for(int c = 0; c < N; c++) {
				map[r][c] = Integer.parseInt(tokens.nextToken());
			}
		}
		
		for(int r = 0; r < N; r++) {
			// 행 방향 탐색			
			if(isPossible(map[r])) cnt++;
			
			// r번째 열을 행으로 변환
			int [] temp = new int [N];
			for(int i = 0; i < N; i++) {
				temp[i] = map[i][r];
			}
			// 열 방향 탐색
			if(isPossible(temp)) cnt++;
		}
		System.out.println(cnt);
	}
	
	// 현재 행을 지나갈 수 있는가?
	private static boolean isPossible(int[] row) {
		// 경사로 놨는지 체크
		boolean [] checked = new boolean [N];
		
		for(int idx = 1; idx < N; idx++) {
			if(checked[idx] || row[idx] == row[idx - 1]) continue; // 이미 경사로를 놨거나 높이가 같으면 통과
			if(Math.abs(row[idx] - row[idx - 1]) > 1) return false; // 높이의 차가 1보다 크면 실패

			if(row[idx] + 1 == row[idx - 1]) { // 오른쪽으로 경사로 놓기
				if(idx + L - 1 >= N || checked[idx + L - 1]) return false; // 인덱스 벗어나거나 이미 경사로가 놔져있다면 실패
				for(int i = idx; i < idx + L; i++) {
					if(checked[i] || row[idx] != row[i]) return false;
					
					checked[i] = true;
				}
			} else if(row[idx] == row[idx - 1] + 1) { // 왼쪽으로 경사로 놓기
				if(idx - L < 0 || checked[idx - L]) return false; // 인덱스 벗어나거나 이미 경사로가 놔져있다면 실패
				for(int i = idx - 1; i >= idx - L; i--) {
					if(checked[i] || row[idx - 1] != row[i]) return false;
					
					checked[i] = true;
				}
			}
		}
		
		return true;
	}

}