[JS]백준 14890 : 경사로

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

14890번: 경사로

 

📋풀이방법

1. 주어진 N배열을 시계방향으로 90도 돌린 복사배열 하나를 생성한다.

2. 두 배열의 행을 기준으로 하나의 행씩 검사한다. (행별로 나눔)

3. 행을 검사할 때 아래와 같이 검사한다. arr[ j - 1 ] == arr[ j ]

4. possible라는 변수로 경사로가 설치가능한 거리를 저장한다.

5. 검사하면서 아래의 조건을 따진다

 -1. 만약 j 와 j-1이 같을 때

  -> 이는 둘이 같은 높이이므로 경사로를 설치가능한 거리가 증가한다.

  -> possible을 1 증가시킨다.

 -2. 만약 j 와 j-1이의 차이가 1일 때

  ->1. 만약 j가 큰 경우(오르막길 상황)

   -> 경사로 설치가능한 거리가 L 보다 크거나 같다면 경사로를 설치가능하다는 의미로 해당 길은 갈 수 있게된다.

   -> 갈 수 있다면 possible을 1로 만들어서 경사로 설치 가능한 거리를 다시 초기화한다.

  ->2. 만약 j가 작은 경우(내리막 상황)

   -> 경사로 설치가능한 거리가 0보다 크다면 일단 현재 정상적으로 길을 가고 있었다는 것을 의미한다.(이전에 내리막 상황에서 만약  충분하지 않은 경사설치 가능거리가(possible) 형성되었을 때를 대비함)

   -> 그렇다면 경사로 설치가능한거리를 1 에서 L을 빼줌으로써 다음 반복에서 경사로 설치가능한 거리를 파악한다.

 -3. 만약 possible이 위 조건 모두에 부합하지 않은 상황일 때 ( 이때는 j와 j-1의 높이차이가 2이상이므로 불가능한 상황이다)

  ->possible을 음수로 만들어서 추후 가능한 길을 체크할 때 넘어가게 한다.

6. possible이 0보다 크다면 해당 길은 갈 수 있는 길이 된다.

7. 갈 수 있는 길을 누적하여 출력한다.

 

 

🤟내 제출

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim();
input=input.replace(/\r/g,"").split("\n");

let [N,L]=input.shift().split(" ").map(Number);
let arr=[]
for(var i=0;i<N;i++){
    arr.push(input.shift().split(" ").map(Number));
}

function check(arr, N, L) {
    let answer = 0;
    for (let i = 0; i < N; i++) {
        //검사할 열또는 행을 하나 꺼냄
        const now = arr[i];
        let possible = 1; // 두번째 칸부터 시작하므로 처음엔 1로 초기화(경사로를 설치할 수 있는 거리를 뜻함)
        for (let j = 1; j < N; j++) {
            if (now[j - 1] == now[j]) possible++; // 2번째 칸과 1번째 칸이 같으면 가능한 길이므로 possible++
            else if (now[j - 1] + 1 == now[j] && possible >= L) possible = 1; //만약 2번째칸과 1번째 칸의 높이 차이가 1이고(now[1]>now[0]), possible이 L보다 크거나 같으면
            //possible을 1로 만드는 이유는 해당 길에 경사로를 설치했으므로 경사로를 설치할수 있는 거리는 다시 1이 된다.
            else if (now[j - 1] == now[j] + 1 && possible >= 0) possible = 1 - L; //만약 2번째 칸과 1번째 칸의 높이 차이가 1이고(now[1]<now[0]), possible이 0보다 크면 
            //possible = 1 - L로 만드는 이유는 아래로 내려가는 상황이므로 앞으로 경사로 설치 가능한 길이 L만큼이 있어야한다. 그것을 미리 1에서 빼고, 다음 반복 때 가능한 길을 체크한다  
            //이때 possible이 음수로 반복문이 끝난다면 더이상 경사로를 설치가능한 거리가 되지않는 것이므로 아래 if (possible >= 0)에서 걸러진다.
            else { possible = -1; break }; //만약 possible이 위 if문에서 걸러지지 않는다면 가능한 상황이 아니므로 possible을 음수로 만들어준다.
        }
        if (possible >= 0) {
            answer++;
        }
    
    }
    return answer;
}

let newBoard = Array.from(Array(N), () => Array(N));
//행부분과 열부분 한번에 검사하기위해
for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
    newBoard[j][i] = arr[i][j]
    }
}
const res = check(arr, N, L) + check(newBoard, N, L);
console.log(res);

 

 

💢어려웠던 점

1. 경사로를 설치했다면 그 자리에는 또다시 경사로가 겹치거나 설치될 수 없음을 어떻게 구현해야할지 생각하지 못했다.

 -possible이라는 변수를 통해서 경사로를 설치가능한 거리를 저장하고 행을 순회하면서 그 거리를 활용하는 방법을 알아내지못했다.

2. 오르막 상황과 내리막 상황에서 어떻게 경사로를 설치하게 해야하는지 생각해내지 못했다.

-오르막상황일 때와 내리막 상황일 때 파악해야하는 경사로 설치가능구역이 달랐다.

-possible을 통해서 누적했던 거리를 이용하거나

 미리 L을 빼줘서 다음 순회에서 걸러주는 방법을 생각해내지 못했다.