[백준] 14890번 경사로

- 문제 : https://www.acmicpc.net/problem/14890

 지도(2차원 행렬)에 지형의 높이가 나와있고 높이가 다른 지형을 경사로를 설치해서 연결하는 문제입니다. 경사로의 높이는 1이고 높이 차이가 1이 나는 지형에만 경사로를 설치할 수 있습니다. 경사로의 길이는 매번 다르며 경사로 설치를 위해 따라야하는 몇 가지 제약 조건이 있습니다.

- 풀이

 

 문제의 제약 사항을 분기하고 프로그램을 구현할 수 있는지 확인하는 문제입니다. 문제의 출처에 가보면 4가지 제약 사항이 나오는데, 그 중에서 경사로를 설치한 위치에 다시 경사로를 설치할 수 없다는 제약을 만족 시키기 위해서 boolean 타입의 isSlope[][]을 선언해서 해당 위치에 이미 경사로가 설치된 상태인지 확인했습니다. 그리고 높이 차이가 2 이상나는 위치는 경사로를 설치할 수 없다는 제약을 걸어줬습니다.

 만약 높이 차이가 절대값 1인 경우에 경사로 설치를 위한 while문을 실행 했습니다. 이전 값과 같은 값이 경사로의 길이만큼 이어져 있다면 경사로 설치를 할 수 있도록 했습니다. 만약 길이가 2인 경사로를 설치할 때 지형이 3 2 1 인 경우에 2 다음 위치의 높이가 1이므로 2와 1의 차이가 1이 납니다. 그렇기 때문에 이 경우에는 경사로 설치를 할 수 없습니다. 3 2 2 인 경우에는 3 다음에 길이가 2인 경사로를 설치할 수 있습니다. isOkay변수를 이용해서 해당 위치에 경사로를 설치해서 길이 연결될 수 있는지 확인했습니다.

 위에서 아래로 가는 경우(TopDown)와 왼쪽에서 오른쪽으로 가는 경우(LeftRight)를 나눠서 작성하면 소스 코드의 길이가 너무 길어집니다. 그래서 일관성을 주기 위해서 mapTopDown과 mapLeftRight를 선언해서 수직 방향과 수평 방향을 분할하고 수평 방향의 인자들을 수직 방향으로 변경해서 계산했습니다.

- 코드

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

public class Slope {
	BufferedReader br;
	int[][] mapTopDown, mapLeftRight;
	int[] slope;
	int n, sLength, result;
	int slopeIndex;
	boolean[][] isSlope;

	public int checkMap(int[][] map) {
		int tempLength = 0;
		int before = 0;
		int tempCol = 0;
		int ans = 0;
		boolean isOkay = false;
		
		for (int row = 0; row < n; row++) {
			for (int col = 0; col < n; col++) {
				if (col + 1 >= n) {
					break;
				}
				
				tempLength = 0;
				if (map[row][col] - map[row][col + 1] > 1 || map[row][col] - map[row][col + 1] < -1) {
					isOkay = false;
					break;
				} else if (map[row][col] - map[row][col + 1] == 1) {
					before = map[row][col + 1];
					tempCol = col + 1;
					while (tempLength < sLength) {
						try {
							if (before == map[row][tempCol]) {
								isOkay = true;
								isSlope[row][tempCol] = true;
							} else {
								isOkay = false;
							}
							before = map[row][tempCol];
							tempCol++;
							tempLength++;
						} catch (ArrayIndexOutOfBoundsException e) {
							isOkay = false;
							break;
						}
					}
				} else if (map[row][col] - map[row][col + 1] == -1) {
					before = map[row][col];
					tempCol = col;
					while (tempLength < sLength) {
						try {
							if (before == map[row][tempCol]) {
								if (isSlope[row][tempCol] == false) {
									isOkay = true;
									isSlope[row][tempCol] = true;
								} else {
									isOkay = false;
									break;
								}
							} else {
								isOkay = false;
								break;
							}
							before = map[row][tempCol];
							tempCol--;
							tempLength++;
						} catch (ArrayIndexOutOfBoundsException e) {
							isOkay = false;
							break;
						}
					}
				} else if (map[row][col] - map[row][col + 1] == 0) {
					isOkay = true;
				}
				if (isOkay == false) {
					break;
				}
			}
			if (isOkay) {
				ans++;
			}
		}
		return ans;
	}
	
	public void resetIsSlope(){
		for (int i = 0; i < n; i++) {
			Arrays.fill(isSlope[i], false);
		}
	}

	public void solve() throws IOException {
		String temp[];
		br = new BufferedReader(new InputStreamReader(System.in));
		temp = br.readLine().split(" ");
		n = Integer.parseInt(temp[0]);
		sLength = Integer.parseInt(temp[1]);
		mapTopDown = new int[n][n];
		mapLeftRight = new int[n][n];
		isSlope = new boolean[n][n];
		slope = new int[sLength];
		slopeIndex = 0;
		
		for (int i = 0; i < n; i++) {
			temp = br.readLine().split(" ");
			for (int j = 0; j < n; j++) {
				mapLeftRight[i][j] = Integer.parseInt(temp[j]);
				mapTopDown[j][i] = mapLeftRight[i][j];
			}
		}
		
		result += checkMap(mapTopDown);
		resetIsSlope();
		result += checkMap(mapLeftRight);
		System.out.println(result);
	}

	public static void main(String[] args) throws IOException {
		Slope m = new Slope();
		m.solve();
	}

}