[BJ]G3 14890 경사로

백준 G3 14890 경사로

이 문제는 SW Expert Academy의 모의 4014 활주로 건설과 같은 문제입니다.~

 

문제링크

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

14890번: 경사로

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeW7FakkUDFAVH

SW Expert Academy

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

 

https://www.youtube.com/watch?v=jnnvZInpTTQ 

 

 

소스보기

동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package bj.gold.l3;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.StringTokenizer;

/**
 * @author 은서파
 * @since 2020. 03. 15.
 * @see https://www.acmicpc.net/problem/14890
 * @performance 12792 116
 * @category #시뮬레이션
 * @memo
 * SWEA_모의_4014_활주로건설와 같은 문제
 */

public class BJ_G3_14890_경사로 {

	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder output = new StringBuilder();
	static StringTokenizer tokens;

	static int N, L;
	static int[][] map;

	public static void main(String[] args) throws IOException {
		input = new BufferedReader(new StringReader(src));
		tokens = new StringTokenizer(input.readLine());
		N = Integer.parseInt(tokens.nextToken());
		L = Integer.parseInt(tokens.nextToken());

		map = new int[N][N];

		for (int r = 0; r < N; r++) {
			tokens = new StringTokenizer(input.readLine());
			for (int c = 0; c < N; c++) {
				map[r][c] = Integer.parseInt(tokens.nextToken());
			}
		}// 입력 완료

		int answer = 0;
		// 현재 상태에서 가로로 (즉 row 기준) 도로를 건설해보자.
		for (int r = 0; r < N; r++) {
			boolean result = check(map[r]);
			if (result) {
				answer++;
			}
		}

		// 배열 회전 처리 - 전치 배열 만들기
		for (int r = 0; r < N; r++) {
			for (int c = r + 1; c < N; c++) {
				int temp = map[r][c];
				map[r][c] = map[c][r];
				map[c][r] = temp;
			}
		}

		// 회전된 상태에서 가로로 (즉 row 기준) 도로를 건설해보자.
		for (int r = 0; r < N; r++) {
			boolean result = check(map[r]);
			if (result) {
				answer++;
			}
		}

		System.out.println(answer);
	}

	/**
	 * 주어진 일차원 배열에 도로를 놓을 수 있는가?
	 * 
	 * @param line
	 * @return
	 */
	private static boolean check(int[] line) {
		int slopeEnd = -1; // 기존 내리막 경사로의 끝 지점
		int base = line[0];// 첫 발은 당연히 내딜 수 있겠다.

		for (int n = 1; n < N; n++) {
			// 높이 차 계산
			int gap = base - line[n];

			// 계속해서 평지
			if (gap == 0) {
				continue;
			}
			// 내리막 경사로 필요
			else if (gap == 1) {
				// 경사로를 설치할 만한 충분한 공간이 나오나?
				if (n + L <= N) {
					// L 동안은 높이가 같아야 한다.
					for (int l = 1; l < L; l++) {
						if (line[n] != line[n + l]) {
							return false;
						}
					}

					// 경사로 설치 가능
					base--;// 현재 높이는 -1
					n += L - 1; // 경사로 설치 길이 만큼 증가
					slopeEnd = n; // 내리막 경사로의 끝 지점 갱신
				} else {
					return false;
				}
			}
			// 오르막 경사로 필요
			else if (gap == -1) {
				// 오르막 경사로가 기존에 있던 내리막 경사로를 침범하지는 않는가?
				if (n - 1 - L >= slopeEnd) {
					//L 동안은 높이가 같아야 한다.
					for (int l = 1; l <= L; l++) {
						if (base != line[n - l]) {
							return false;
						}
					}
					// 경사로 설치 가능
					base++;
				} else {
					return false;
				}
			}
			// 실패
			else {
				return false;
			}
		}
		// 여기까지 왔다면 성공!!
		return true;
	}

	// REMOVE_START
	private static String src = "6 2\n"
								+ "3 3 3 3 3 3\n"
								+ "2 3 3 3 3 3\n"
								+ "2 2 2 3 2 3\n"
								+ "1 1 1 2 2 2\n"
								+ "1 1 1 3 3 1\n"
								+ "1 1 2 3 3 2";
	// REMOVE_END

}