[BaekJoon] 14890 경사로 (Java)

1.  문제 링크

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

2.  문제

요약

• 크기가 NxN인 지도가 있고 각 칸에는 그 곳의 높이가 적혀져 있습니다.
• 길이란 한 행 또는 한 열 전부를 나타내며, 한쪽 끝에서 다른쪽 끝까지 지나가는 것인데, 이 지도에서 지나갈 수 있는 길이 몇 개인지 알아보려고 합니다.
• 길을 지나갈 수 있으려면 길에 속한 모든 칸의 높이가 모두 같거나 경사로를 놓아서 지나갈 수 있는 길을 만들 수 있습니다.
• 경사로는 높이가 항상 1이며, 길이는 L이고 개수는 매우 많아 부족할 일이 없습니다.
• 경사로는 낮은 칸과 높은 칸을 연결하며, 아래와 같은 조건을 만족해야합니다.
  • 경사로는 낮은 칸에 놓으며, L개의 연속된 칸에 경사로의 바닥이 모두 접해야 합니다.
  • 낮은 칸과 높은 칸의 높이 차이는 1이어야 합니다.
  • 경사로를 놓을 낮은 칸의 높이는 모두 같아야 하고, L개의 칸이 연속되어 있어야 합니다.
• 아래와 같은 경우에는 경사로를 놓을 수 없습니다.
  • 경사로를 놓은 곳에 또 경사로를 놓는 경우
  • 낮은 칸과 높은 칸의 높이 차이가 1이 아닌 경우
  • 낮은 지점의 칸의 높이가 모두 같지 않거나, L개가 연속되지 않은 경우
  • 경사로를 놓다가 범위를 벗어나는 경우
• 지도가 주어졌을 때, 지나갈 수 있는 길의 개수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 2보다 크거나 같고 100보다 작거나 같은 N과 1보다 크거나 같고 N보다 작거나 같은 L이 주어지고 두 번째 줄부터 N개의 줄에는 10보다 작거나 같은 자연수인 각 칸의 높이가 주어집니다.
• 출력: 첫째 줄에 지나갈 수 있는 길의 개수를 출력합니다.

3.  소스코드

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

public class Main {
	static int N, L;
	static int[][] map;
	static boolean[][] slopeWay;
	static void input() {
		Reader scanner = new Reader();
		N = scanner.nextInt();
		L = scanner.nextInt();
		map = new int[N][N];
		slopeWay = new boolean[N][N];
		for(int row = 0; row < N; row++) {
			for(int col = 0; col < N; col++) map[row][col] = scanner.nextInt();
		}
	}
	
	static void solution() {
		int answer = 0;
		for(int row = 0; row < N; row++) {
			if(isRowRoad(row)) {
				answer++;
			} else {
				if(checkRows(row)) answer++;
			}
		}
		slopeWay = new boolean[N][N];
		for(int col = 0; col < N; col++) {
			if(isColRoad(col)) {
				answer++;
			} else {
				if(checkColumns(col)) answer++;
			}
		}
		System.out.println(answer);
	}
	
	static boolean isRowRoad(int row) {
		int num = map[row][0];
		for(int col = 1; col < N; col++) {
			if(map[row][col] != num) return false;
		}
		return true;
	}
	
	static boolean isColRoad(int col) {
		int num = map[0][col];
		for(int row = 1; row < N; row++) {
			if(map[row][col] != num) return false;
		}
		return true;
	}
	
	static boolean checkRows(int row) {
		int num = map[row][0];
		for(int col = 1; col < N; col++) {
			if(num == map[row][col]) continue;
			if(num > map[row][col]) { // 높이가 낮아졌을 때
				if(map[row][col] < num - 1) return false;
				if(col + L - 1 >= N) return false;
				num = map[row][col];
				for(int col2 = col; col2 <= col + L - 1; col2++) {
					if(slopeWay[row][col2]) return false;
					slopeWay[row][col2] = true;
					if(num != map[row][col2]) {
						return false;
					}
				}
			} else if(num < map[row][col]) { // 높이가 높아졌을 때
				if(map[row][col] > num + 1) return false;
				if(col - L < 0) return false;
				num = map[row][col - 1];
				for(int col2 = col - L; col2 < col; col2++) {
					if(slopeWay[row][col2]) return false;
					slopeWay[row][col2] = true;
					if(num != map[row][col2]) {
						return false;
					}
				}
				num = map[row][col];
			}
		}
		return true;
	}
	
	static boolean checkColumns(int col) {
		int num = map[0][col];
		for(int row = 1; row < N; row++) {
			if(num == map[row][col]) continue;
			if(num > map[row][col]) { // 높이가 낮아졌을 때
				if(map[row][col] < num - 1) return false;
				if(row + L - 1 >= N) return false;
				num = map[row][col];
				for(int row2 = row; row2 <= row + L - 1; row2++) {
					if(slopeWay[row2][col]) return false;
					slopeWay[row2][col] = true;
					if(num != map[row2][col]) {
						return false;
					}
				}
			} else if(num < map[row][col]) { // 높이가 높아졌을 때
				if(map[row][col] > num + 1) return false;
				if(row - L < 0) return false;
				num = map[row - 1][col];
				for(int row2 = row - L; row2 < row; row2++) {
					if(slopeWay[row2][col]) return false;
					slopeWay[row2][col] = true;
					if(num != map[row2][col]) {
						return false;
					}
				}
				num = map[row][col];
			}
		}
		return true;
	}
	
	public static void main(String[] args) {
		input();
		solution();
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
}

4.  접근

• 각 길에 대해서 문제에서 주어진 조건들을 하나씩 확인해보고 모든 조건을 만족하는 길의 개수를 구하는 문제입니다.
• 각 길에서 경사로를 겹쳐서 놓을 수 없기 때문에 경사로를 놓았는지를 나타내는 slopeWay라는 boolean 타입의 2차원 배열을 만들고 경사로가 필요할 때 이 배열에 경사로를 표시하고 경사로가 겹치는지를 확인합니다.
• 조건 확인은 행에서의 길과 열에서의 길이 같은 방식이기 때문에 행에서의 길에 대해서만 확인해보겠습니다.

checkRows 함수

static boolean checkRows(int row) {
	int num = map[row][0];
	for(int col = 1; col < N; col++) {
		if(num == map[row][col]) continue;
		if(num > map[row][col]) { // 높이가 낮아졌을 때
			if(map[row][col] < num - 1) return false;
			if(col + L - 1 >= N) return false;
			num = map[row][col];
			for(int col2 = col; col2 <= col + L - 1; col2++) {
				if(slopeWay[row][col2]) return false;
				slopeWay[row][col2] = true;
				if(num != map[row][col2]) {
					return false;
				}
			}
		} else if(num < map[row][col]) { // 높이가 높아졌을 때
			if(map[row][col] > num + 1) return false;
			if(col - L < 0) return false;
			num = map[row][col - 1];
			for(int col2 = col - L; col2 < col; col2++) {
				if(slopeWay[row][col2]) return false;
				slopeWay[row][col2] = true;
				if(num != map[row][col2]) {
					return false;
				}
			}
			num = map[row][col];
		}
	}
	return true;
}

• 이 함수는 행에서의 길에서 지나갈 수 있는 길인지 확인하는 함수입니다.
• 이 함수를 실행시키기 이전에 모든 칸이 같은 높이인지 먼저 확인하고 그렇다면 이미 지나갈 수 있는 길임을 확인했기 때문에 지나갈 수 있는 길의 개수를 하나 증가시켜주고 다음 길을 확인하고 그렇지 않을 때에 이 함수를 호출해 지나갈 수 있는 길인지 확인합니다.
• 왼쪽부터 오른쪽으로, 즉 열의 index가 0일 때부터 N - 1일 때까지 확인하는데, 이 때 높이가 높아지는 경우와 낮아지는 경우, 높이가 같은 경우가 있습니다.
• 높이가 같은 경우는 지나갈 수 있기 때문에 다음 열을 확인합니다.
• 높아지는 경우와 낮아지는 경우는 같은 방식이기 때문에 낮아지는 경우에 대해서만 살펴보겠습니다.
• 만약 높이가 낮아졌다면 높이가 1보다 더 낮아졌는지 확인하고 그렇다면 경사로를 통해서도 이동을 할 수 없기 때문에 지나갈 수 없는 길임을 반환합니다.
• 또한, 높이가 낮아진 곳부터 L만큼 이동한 곳이 길을 벗어난다면 경사로를 놓을 수 없기 때문에 이 또한 지나갈 수 없는 길임을 반환합니다.
• 위 두 경우를 만족했다면 높이가 낮아진 곳부터 L만큼 이동한 곳까지 각 위치를 살펴보면서 경사로를 놓을 수 있는지 확인합니다.
  • 만약 이미 경사로가 놓여진 위치가 있다면 해당 위치에는 경사로를 설치할 수 없기 때문에 지나갈 수 없는 길임을 반환합니다.
  • 만약 그렇지 않다면 그 위치에는 경사로를 세워놓기 위해 해당 위치의 slopeWay 값을 true로 변경합니다.
  • 만약 낮아진 높이와 높이가 다른 칸이 존재한다면 경사로는 낮은 지점의 높이가 같은 곳에만 놓을 수 있다는 조건에 위배되므로 지나갈 수 없는 길임을 반환합니다.
• 위 조건들을 모두 만족했다면 해당 길은 지나갈 수 있는 길이기 때문에 지나갈 수 있는 길임을 반환합니다.