경사로

문제

• 백준 14890번 - 경사로

언어

• JavaScript

순서도

1. 각각의 행마다 검사, 행의 개수는 총 N * N 번
2. 행에서 하나의 칸씩 앞으로 가면서 검사
3. 이전 칸과 현재 칸의 높이가 동일하다면 다음 칸으로 이동
4. 이전 칸과 현재 칸의 높이 차이가 2 이상 난다면 갈 수 없는 길로 판별
5. 이전 칸이 현재 칸의 높이보다 1 만큼 작다면
   1. 이전에 경사로를 놓아야 하는 경우로
   2. 이전 칸의 총 개수가 경사로의 길이보다 작다면 갈 수 없는 길로 판별
   3. 이전 칸을 시작으로 한 칸씩 이전으로 가면서 높이가 같은지 그리고 경사로를 놓은 길이 아닌지 판별
   4. 5.3번의 조건을 만족한다면 경사로를 놓음
   5. 5.1 ~ 5.4 의 과정을 수행하며 현재 행의 마지막 칸에 도달한다면 갈 수 있는 길로 판별
6. 반대로 이전 칸이 현재 칸의 높이보다 1 만큼 크다면
   1. 다음에 경사로를 놓아야 하는 경우로
   2. 다음 칸의 총 개수가 경사로의 길이보다 작다면 갈 수 없는 길로 판별
   3. 현재 칸을 시작으로 한 칸씩 다음으로 가면서 높이가 같은지 그리고 경사로를 놓은 길이 아닌지 판별
   4. 6.3 번의 조건을 만족한다면 경사로를 놓음
   5. 6.1 ~ 6.4 의 과정을 수행하며 현재 행의 마지막 칸에 도달한다면 갈 수 있는 길로 판별
7. 위의 과정 모두 수행하면서 갈 수 있는 길의 개수를 모두 세서 출력

문제 풀이 step 1

• 구현 문제로서, 문제에서 주어진 설명대로 구현하는 문제입니다.
• 시행착오를 많이 했지만, 결국 주어진 예제를 손으로 써가면서 풀어보니 해결책을 찾을 수 있었습니다.
• 결론은 각 행을 한 칸씩 지나가면서 이 길이 그냥 지나갈 수 있는 길인지 아니면 경사로가 필요한 길인지 판별하는 것이 해결 방법이었습니다.

문제 풀이 step 2

• 각 행을 한 칸씩 지나가면서 검사하는 과정을 자세히 설명해보겠습니다.
• 각 칸의 높이가 모두 같은 경우와 다른 경우로 나뉩니다.
  • 각 칸의 높이가 모두 같다면 그 길은 지나갈 수 있는 길로 판별됩니다.
  • 각 칸의 높이가 다른 경우는 두 개의 경우로 또 나뉩니다.
• 각 칸의 높이가 다르다면, 경사로를 놓을 수 있는 경우와 놓을 수 없는 경우로 나뉩니다.
  • 경사로를 놓을 수 있는 경우는 또 두 개의 경우로 나뉩니다.
    • 증가하는 모양의 경사로를 놓는 경우
    • 감소하는 모양의 경사로를 놓는 경우
  • 경사로를 놓을 수 없는 경우는 놓을 수 있는 경우에서 제외되는 경우입니다.

문제 풀이 step 3

• 각 경우를 자세히 설명해보겠습니다.
• 각 칸의 높이가 모두 같은 경우는 별다른 처리를 할 필요가 없습니다.
• 각 칸의 높이가 다른데 증가하는 모양의 경사로를 놓는 경우는
  • 이전 칸의 높이보다 다음 칸의 높이가 1 만큼 커야 합니다.
  • 이 때, 다음 칸을 기준으로 이전 칸들의 개수가 L 개 (경사로의 길이) 여야 하며,
  • L 개의 이전 칸이 모두 높이가 같아야 하며, 경사로를 놓지 않은 칸이여야 합니다.
  • 이 경우가 아니라면 경사로를 못 놓게 되고, 지나갈 수 없는 길로 판별됩니다.
• 각 칸의 높이가 다른데 감소하는 모양의 경사로를 놓는 경우는
  • 이전 칸의 높이보다 다음 칸의 높이가 1 만큼 작아야 합니다.
  • 이 때, 이전 칸을 기준으로 다음 칸들의 개수가 L 개 (경사로의 길이) 여야 하며,
  • L 개의 다음 칸이 모두 높이가 같아야 하며, 경사로를 놓지 않은 칸이여야 합니다.
  • 이 경우가 아니라면 경사로를 못 놓게 되고, 지나갈 수 없는 길로 판별됩니다.
• 경사로를 놓을 수 없는 경우는
  • 위에서 경사로를 못 놓는 경우
  • 이전 칸의 높이와 다음 칸의 높이 차이가 2 이상인 경우
  • 이미 경사로를 놓은 경우입니다.
• 각 경우에 맞게 로직을 구현하고, 지나갈 수 있는 길의 개수를 모두 세서 출력하면 정답이 됩니다.
• 추가적인 설명은 주석에 작성하겠습니다.

후기

• 가로 방향 검사와 세로 방향 검사가 필요한데, 각 행마다 새로운 배열에 복사하는 방식이 낭비가 될 것이라고 생각했습니다.
• 그래서 가로 방향 검사와 세로 방향 검사가 소스 코드가 똑같음에도 불구하고 중복된 코드를 사용했습니다.
• 물론 이 방식의 풀이는 소요 시간은 적게 걸렸지만, 중복된 코드로 인해서 코드량이 너무 많았습니다.
• 그래서 각 행마다 새로운 배열에 복사하고, 검사하는 로직을 별도의 함수로 분리하니 중복을 없앨 수 있었고, 코드량을 줄일 수 있었습니다. 물론 시간은 더 걸렸지만, 후자의 방법이 더 나은 것 같습니다.
• 이번 문제도 어떻게 구현해야 할 지 막막했지만, 손으로 작성하면서 풀어보면서 문제의 감을 찾는 것이 가장 중요한 것 같습니다.

소스 코드

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

// 주어진 행이 갈 수 있는 길인지 판별하는 함수
const checkPossibleRoute = (n, l, arr) => {
	// 각 칸에 경사로를 놓았는지 안놓았는지 판별하기 위한 배열
	const isRunway = Array(n).fill(false);

	// 이전 칸 기록
	let before = arr[0];

	// 다음 칸 부터 한 칸씩 진행
	for (let j = 1; j < n; j++) {
		const now = arr[j];

		// 이전 칸과 다음 칸의 높이 차이가 2 이상인 경우 : 못 지나가는 길
		if (Math.abs(before - now) > 1) return false;

		if (before === now) continue;

		if (now - before === 1) {
			// 1.1. 이전에 경사로를 놓는 경우 (증가하는 경사로를 놓는 경우)
			let cnt = 0;

			// 이전 칸들의 개수가 L 개보다 작은 경우 : 못 지나가는 길
			if (j - l < 0) return false;

			// 이전 칸들의 높이가 같은지 그리고 경사로를 놓지 않은 길인지 판별
			for (let k = j - 1; k >= j - l; k--) {
				if (arr[k] === before && isRunway[k] === false) cnt += 1;
			}

			if (cnt === l) {
				for (let k = j - 1; k >= j - l; k--) {
					// 경사로를 놓음
					isRunway[k] = true;
				}
			} else {
				// 이전 칸들의 높이가 같지 않거나 경사로를 이미 놓은 칸이 존재하는 경우 : 못 지나가는 길
				return false;
			}
		} else if (before - now === 1) {
			// 1.2. 이후에 경사로를 놓는 경우 (감소하는 경사로를 놓는 경우)
			let cnt = 0;

			// 다음 칸들의 개수가 L 개보다 작은 경우 : 못 지나가는 길
			if (j + l > n) return false;

			// 다음 칸들의 높이가 같은지 그리고 경사로를 놓지 않은 길인지 판별
			for (let k = j; k < j + l; k++) {
				if (arr[k] === now && isRunway[k] === false) cnt += 1;
			}

			if (cnt === l) {
				for (let k = j; k < j + l; k++) {
					// 경사로를 놓음
					isRunway[k] = true;
				}
			} else {
				// 다음 칸들의 높이가 같지 않거나 경사로를 이미 놓은 칸이 존재하는 경우 : 못 지나가는 길
				return false;
			}
		}

		before = now;
	}

	// 지나갈 수 있는 길
	return true;
};

const solution = (input) => {
	const [n, l] = input[0].split(" ").map(Number);
	const arr = input.slice(1).map((v) => v.split(" ").map(Number));

	let cnt = 0;
	// 1. 행 검사
	for (let i = 0; i < n; i++) {
		const oneArr = [];
		for (let j = 0; j < n; j++) {
			// 새로운 배열에 한 줄 복사
			oneArr[j] = arr[i][j];
		}
		if (checkPossibleRoute(n, l, oneArr) === true) cnt += 1;
	}

	// 2. 열 검사
	for (let i = 0; i < n; i++) {
		const oneArr = [];
		for (let j = 0; j < n; j++) {
			// 새로운 배열에 한 줄 복사
			oneArr[j] = arr[j][i];
		}
		if (checkPossibleRoute(n, l, oneArr) === true) cnt += 1;
	}

	return cnt;
};

console.log(solution(input));