[ 알고리즘 ] 코딩 - 백준 14890 - 경사로.java

---

문제 링크

www.acmicpc.net/problem/14890

14890번: 경사로

---

문제 개요

BOJ 14890 - (자바) 경사로 - 구현

크기가 N×N인 지도가 있다. 지도의 각 칸에는 그곳의 높이가 적혀 있다.

오늘은 이 지도에서 지나갈 수 있는 길이 몇 개 있는지 알아보려고 한다. 길이란 한 행 또는 한 열 전부를 나타내며, 한쪽 끝에서 다른 쪽 끝까지 지나가는 것이다. 

다음과 같은 N=6인 경우 지도를 살펴보자.

지도 예시

길을 지나갈 수 있으려면 길에 속한 모든 칸의 높이가 모두 같아야 한다. 또는, 경사로를 놓아서 지나갈 수 있는 길을 만들 수 있다. 경사로는 높이가 항상 1이며, 길이는 L이다. 또, 개수는 매우 많아 부족할 일이 없다. 경사로는 낮은 칸과 높은 칸을 연결하며, 아래와 같은 조건을 만족해야 한다.

• 경사로는 낮은 칸에 놓으며, L개의 연속된 칸에 경사로의 바닥이 모두 접해야 한다.
• 낮은 칸과 높은 칸의 높이 차이는 1이어야 한다.
• 경사로를 놓을 낮은 칸의 높이는 모두 같아야 하고, L개의 칸이 연속되어 있어야 한다.

아래와 같은 경우에는 경사로를 놓을 수 없다.

• 경사로를 놓은 곳에 또 경사로를 놓는 경우
• 낮은 칸과 높은 칸의 높이 차이가 1이 아닌 경우
• 낮은 지점의 칸의 높이가 모두 같지 않거나, L개가 연속되지 않은 경우
• 경사로를 놓다가 범위를 벗어나는 경우

L = 2인 경우에 경사로를 놓을 수 있는 경우를 그림으로 나타내면 아래와 같다.

설치 예시

설치 불가 예시

 

---

로직

Step 00. 입력을 받을 때, 열과 행을 관리할 수 있는 2차원 배열을 2개 입력받는다.

Step 01. 경사로를 설치할 위치를 행과 열로 끊어서 확인한다. 시작 위치를 이전 높이로 저장하고 난 후 4개지의 경우를 판단한다.

1. 현재 위치가 이전과 같은 높이라면 count+1.
2. 이전 칸이 현재 칸보다 한 칸 낮은 경우 count가 L보다 작다면 설치 불가. false 리턴. 아니라면 설치하고 count를 1로 초기화한 후 이전 높이를 현재 높이로 저장한다.
3. 이전 칸이 현재 칸보다 한 칸 높은 경우 현재 위치에서 남은 위치를 살펴본다. 남은 위치에서 평 탄로가 아닌 위치가 나타난다면 반복을 멈추고 몇 칸이 나왔는지 확인한다. 만약 개수가 L보다 작다면 설치 불가. 아니라면 이전 위치에 해당 높이를 설정하고 다음 위치를 현재 위치 + L - 1로 바꿔준다.
4. 1, 2, 3번에 해당하지 않는다면 높이차이가 2 이상이므로 설치 불가능

Step 02. Step01의 과정을 모든 행과 열에 대해 반복한다.

Step 03. Step 02의 결과로 나온 합이 정답!

---

코드

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stt = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(stt.nextToken());
		int L = Integer.parseInt(stt.nextToken());

		int[][] map = new int[N][N];
		int[][] rmap = new int[N][N];

		for (int i = 0; i < N; i++) {
			stt = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				rmap[j][i] = map[i][j] = Integer.parseInt(stt.nextToken());
			}
		} // input end

		int res = process(N, L, map, rmap);
		System.out.println(res);
	}

	private static int process(int n, int l, int[][] map, int[][] rmap) {
		int max_cnt = 0;
		for (int i = 0; i < n; i++) {
			if (makeRoad(map[i], n, l))
				max_cnt++;
			if (makeRoad(rmap[i], n, l))
				max_cnt++;
		}
		return max_cnt;
	}

	private static boolean makeRoad(int[] map, int n, int l) {
		int beforeHeight = map[0];
		int count = 1;
		for (int j = 1; j < n; j++) {
			// 같은 높이
			if (beforeHeight == map[j]) {
				count++;
			}
			
			// 이전 칸이 한 칸 낮음
			else if (beforeHeight + 1 == map[j]) {
				if(count < l) return false;
				beforeHeight++;
				count = 1;
			}

			// 이전 칸이 한 칸 높음
			else if (beforeHeight - 1 == map[j]) {
				// 앞으로 평지의 수를 세어야 한다.
				int remain = 0;
				for(int k = j; k < n; k++) {
					if(beforeHeight-1 != map[k]) break;
					remain++;
				}
				if(remain < l) return false;
				
				// 설치 가능
				j += l-1;
				count = 0;
				beforeHeight--;
			}

			// 높이 차이 2이상
			else {
				return false;
			}
		}
		return true;
	}
}