백준 14890 - 경사로

Java

14890 번 - 경사로

문제

접근 방법

가로 n줄, 세로 n줄을 확인하여 끝까지 갈 수있는지 확인하는 문제이다.

따라서 가로, 세로 한줄 씩 뽑아내고 끝까지 갈 수있는지 확인하는 메서드를 만들어 한줄 씩 확인한다.

각 줄의 인덱스 1부터 n-1까지 바로 이전 높이와 확인하여

1. 높이가 2 이상 차이나는지
2. 현재 높이가 이전 높이보다 작은지
3. 현재 높이가 이전 높이보다 높은지
   를 확인한다.

1번의 경우 경사로를 놓을 수 없으므로 메서드를 리턴한다.
2번의 경우 현재 위치에서 앞으로 m - 1개 크기까지 경사로를 놓을 수 있는지 확인하고 가능하면 boolean 배열에 놓았다고 표시한다. 3번의 경우 현재 위치에서 뒤로 m개 크기까지 경사로를 놓을 수 있는지 확인한다. 2번에서 놓은 경사로가 있는지 확인하는 조건이 추가된다.

코드

import java.util.*;
import java.io.*;

public class Main {
	static int n, m, result;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	n = stoi(stk.nextToken());
    	m = stoi(stk.nextToken());
    	
    	int[][] map = new int[n][n];
    	
    	for(int i = 0; i < n; i++) {
    		stk = new StringTokenizer(br.readLine());
    		for(int j = 0; j < n; j++) {
    			map[i][j] = stoi(stk.nextToken());
    		}
    	}
    	
    	int[] curR = new int[n];;
    	// 가로 탐색
    	for(int line = 0; line < n; line++) {
    		curR = map[line].clone();
    		
    		if(isPass(curR))
    			result++;
    	}
    	
    	// 세로 탐색
    	for(int i = 0; i < n; i++) {
			// 세로 줄 하나를 뽑아낸다.
    		for(int j = 0; j < n; j++)
    			curR[j] = map[j][i];
    		
    		if(isPass(curR))
    			result++;
    	}
    	
    	System.out.println(result);
    	br.close();
	}
	
	// 한 줄이 지나갈 수 있는지 확ㅇ니
	static boolean isPass(int[] curR) {
		boolean[] vis = new boolean[n];
		int h;
		// 1번째 위치부터 n - 1까지 이동한다.
		for(int i = 1; i < n; i++) {	
			if(Math.abs(curR[i] - curR[i - 1]) >= 2) {
				return false;
			}
			// 내리막길이면
			else if(curR[i - 1] > curR[i]) {
				h = curR[i];
				vis[i] = true;
				// 현재 위치에서 내리막길을 만들 수 있는지 확인
				for(int j = 1; j < m; j++) {
					// 범위를 벗어났거나, 같은 높이가 아닐 때
					if(!isIn(i + j) || h != curR[i + j])
						return false;
					vis[i + j] = true;
				}
			}
			else if(curR[i - 1] < curR[i]) {
				h = curR[i - 1];
				if(vis[i - 1])
					return false;
				
				for(int j = 1; j < m; j++) {
					// 범위를 벗어났거나, 경사로를 놓을 자리에 이미 놓았거나, 같은 높이가 아닐 때
					if(!isIn(i - 1 - j) || vis[i - 1 - j] || h != curR[i - 1 - j])
						return false;
				}
			}
		}
		
		return true;
	}
	
	static boolean isIn(int idx) {
		if(0 <= idx && idx < n)
			return true;
		return false;
	}
	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

개선할 점