[백준] 14890번: 경사로 문제 풀이

시작 전 회고

처음에 문제에 접근할 땐 왼쪽 오른쪽 방향에서 각각 내리막길을 놓을 수 있는지 검사하고, 위쪽, 아래쪽에서 각각 검사하는 방식으로 진행했었다.

하지만 잘못된 접근이었고, 내리막길만 검사할게 아니라 오르막길의 가능 여부도 따져야했기 때문에, 양옆 방향에서 각각 검사할게 아닌 한쪽 방향에서 한쪽만 검사해도 충분한 문제였다.

접근 방법

배열을 한줄씩 검사하면서 경사로를 놓을 수 있는지 검사한다.
이 때, 사용할 변수로 현재 내리막길의 여부를 나타낼 down과
오르막길을 놓을 수 있는 거리 ableUp을 사용한다.
현재까지의 높이 curH를 저장하면서 한칸씩 검사한다.

• 이동할 칸의 높이가 현재 높이와 같고, 현재 내리막길을 내려가는 중이 아니라면 (down이 0이라면)
  -> 오르막길을 놓을 수 있는 거리를 1씩 증가시킨다.

if (curH == arr[idx][i] && down == 0)
	ableUp++;

• 이동할 칸의 높이가 현재 높이보다 낮고, 현재 내리막길을 내려가는 중이 아니라면
  -> 내리막길을 L만큼 놓고, 오르막길을 놓을 수 있는 거리를 0으로 바꾼다.

else if (down == 0 && curH - arr[idx][i] == 1) {
	down = L;
	ableUp = 0;
}

• 이동할 칸의 높이가 현재 높이보다 높고, 현재 내리막길을 내려가는 중이 아니라면
  -> 현재 오르막길을 놓을 수 있는 거리가 L 이상이면 오르막길을 놓았다고 치고 다시 ableUp을 1로 바꾼다.
  -> 만약 오르막길을 놓을 수 있는 거리가 L보다 작아 놓을 수 없으면 해당 길은 경사로를 만들 수 없으므로 return

else if (down == 0 && curH - arr[idx][i] == -1) {
	if (ableUp >= L) ableUp = 1;
	else return;
}

• 그 외에 (현재 내리막길을 내려가고 있는데 칸이 높아지거나 낮아지면, 혹은 높이 차이가 1보다 크면) return

• 현재 내리막길을 내려가고 있으면 (down이 0보다 크면) down 1씩 감소
  if (down > 0) down--;

• 현재 한 줄의 모든 칸 검사가 끝났는데 down이 0보다 크면
  -> 내리막길이 끝나지 않았는데 길이 끝났으므로 return

---

사실 행과 열을 각각 따로 검사하지 않고 동시에 진행할 수도 있었으나, 차피 시간도 넉넉하고, 코드의 가독성을 위해 checkRow와 checkCol로 각각 나누어 구현하였다.

전체 코드

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

public class Main {
	static int N, L, result;
	static int[][] arr;
	static void checkRow(int idx) {
		int down = 0;
		int ableUp = 1;
		int curH = arr[idx][0];
		for (int i = 1; i < N; i++) {
			if (curH == arr[idx][i] && down == 0)
				ableUp++;
			else if (down == 0 && curH - arr[idx][i] == 1) {
				down = L;
				ableUp = 0;
			}
			else if (down == 0 && curH - arr[idx][i] == -1) {
				if (ableUp >= L) ableUp = 1;
				else return;
			}
			else return;
			
			if (down > 0) down--; 
			curH = arr[idx][i];
		}
		if (down > 0) return;
		result++;
	}
	
	static void checkCol(int idx) {
		int down = 0;
		int ableUp = 1;
		int curH = arr[0][idx];
		for (int i = 1; i < N; i++) {
			if (curH == arr[i][idx] && down == 0)
					ableUp++;
			else if (down == 0 && curH - arr[i][idx] == 1) {
				down = L;
				ableUp = 0;
			}
			else if (down == 0 && curH - arr[i][idx] == -1) {
				if (ableUp >= L) ableUp = 1;
				else return;
			}
			else return;
			
			if (down > 0) down--;
			curH = arr[i][idx];
		}
		if (down > 0) return;
		result++;
	}
	
	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());
		arr = new int [N][N];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++)
				arr[i][j] = Integer.parseInt(st.nextToken());
		}
		for (int i = 0; i < N; i++) {
			checkRow(i);
			checkCol(i);
		}
		System.out.println(result);
		br.close();
	}
}