[JavaScript/구현] 백준 골드 3 : 14890 - 경사로

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

14890번: 경사로

---

📌 작성한 코드 

// 14890
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Gold/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const [N, L] = input.shift().split(" ").map(Number);
const board = input.map((str) => str.split(" ").map(Number));

let answer = 0;

let prev = 0;
for (let i = 0; i < N; i++) {
    const visited = new Array(N).fill(false);
    let flag = true;
    prev = board[i][0];

    for (let j = 1; j < N; j++) {
        if (board[i][j] === prev) continue;
        else if (board[i][j] === prev - 1) {
            let isOk = true;

            if (j + L - 1 > N) {
                flag = false;
                break;
            }

            for (let k = j; k < j + L; k++) {
                if (board[i][k] !== prev - 1 || visited[k]) isOk = false;
            }

            if (isOk) {
                for (let k = j; k < j + L; k++) {
                    visited[k] = true;
                }
            } else {
                flag = false;
            }

            prev = board[i][j];
            j += L - 1;
        } else if (board[i][j] === prev + 1) {
            let isOk = true;

            if (j - L < 0) {
                flag = false;
                break;
            }

            for (let k = j - 1; k >= j - L; k--) {
                if (board[i][k] !== prev || visited[k]) {
                    isOk = false;
                }
            }

            if (isOk) {
                for (let k = j - 1; k >= j - L; k--) {
                    visited[k] = true;
                }
            } else {
                flag = false;
            }

            prev = board[i][j];
        } else {
            flag = false;
            break;
        }
    }

    if (flag) {
        answer++;
    }
}

for (let j = 0; j < N; j++) {
    const visited = new Array(N).fill(false);
    let flag = true;
    prev = board[0][j];

    for (let i = 1; i < N; i++) {
        if (board[i][j] === prev) continue;
        else if (board[i][j] === prev - 1) {
            let isOk = true;

            if (i + L - 1 >= N) {
                flag = false;
                break;
            }

            for (let k = i; k < i + L; k++) {
                if (board[k][j] !== prev - 1 || visited[k]) isOk = false;
            }

            if (isOk) {
                for (let k = i; k < i + L; k++) {
                    visited[k] = true;
                }
            } else {
                flag = false;
            }

            prev = board[i][j];
            i += L - 1;
        } else if (board[i][j] === prev + 1) {
            let isOk = true;

            if (i - L < 0) {
                flag = false;
                break;
            }

            for (let k = i - 1; k >= i - L; k--) {
                if (board[k][j] !== prev || visited[k]) {
                    isOk = false;
                }
            }

            if (isOk) {
                for (let k = i - 1; k >= i - L; k--) {
                    visited[k] = true;
                }
            } else {
                flag = false;
            }

            prev = board[i][j];
        } else {
            flag = false;
            break;
        }
    }

    if (flag) {
        answer++;
    }
}

console.log(answer);

 

📌 설명 

지도에 경사로를 놓아서 갈 수 있는 길이 몇 개인지 구하는 구현 문제이다. 

 

💡 갈 수 있는 길의 조건

(1) 갈 수 있는 길은 한 행이나 한 열 전부를 나타낸다. 따라서 가로로 이동하다가 세로로 이동하는 것은 불가능하다.

(2) 모든 칸의 높이가 같으면 이동할 수 있고, 경사로를 두어서 이동할 수 있는 길을 만드는 것도 이동할 수 있는 것으로 생각한다.

(3) 경사로를 놓으려면 경사로를 놓는 칸은 모두 높이가 같아야 하고, 길의 범위를 벗어나지 않아야 하며, 더 낮은 칸에 경사로를 두어야 한다. 

 

💡 구현 시 고려 사항

(1) 모든 행, 열을 확인하기 위해서 가로와 세로를 확인하는 코드를 각각 작성 해야한다.

(2) 경사로는 낮은 칸에 두어야 하기 때문에, 이동할 길이 높은 칸인지 낮은 칸인지에 따라서 경사로를 두는 로직을 다르게 작성해야 한다.

(3) 이전에 경사로를 놓은 곳에 또 놓을 수 없으므로, 경사로가 놓여있는지 확인하는 방문 배열을 사용해야 한다.

 

💡 구현 방식 

(1) 이전에 방문한 길의 높이를 저장하고, 해당 높이와 비교해서 현재 높이가 같으면 다음 위치로 넘어간다.

if (board[i][j] === prev) continue;

(2)이전에 방문한 길보다 1칸 낮으면, 현재 위치부터 경사로의 길이 L동안 모두 같은 높이(1칸 낮은 높이)를 가지고 있는지 확인한다.

- 경사로를 놓아야 할 자리가 길의 범위를 넘어가면 이동이 불가능하므로 확인을 그만둔다

 

- 확인 후 모두 같은 높이이고 경사로를 두지 않았으면, 다시 반복을 돌며 각 위치에 경사로를 놓아준다.(방문 배열을 true로 변경한다.)

- 모두 같은 높이가 아니면 해당 길은 이동이 불가능하므로 확인을 그만둔다.

- 경사로를 놓은 길은 확인할 필요가 없으므로, 경사로 놓은 이후로 이동하기 위해 인덱스를 (경사로 길이 - 1)만큼 증가시킨다.

(경사로 -1인 이유는 현재 내가 위치한 곳부터 경사로를 놓기 때문이다.)

 

- 이전 방문 위치를 현재 위치로 업데이트 한다. 

else if (board[i][j] === prev - 1) { // 한칸 낮으면
    let isOk = true;

    if (j + L - 1 > N) { // 경사로를 놓을 자리가 있는지 확인하기
        flag = false;
        break;
    }

    for (let k = j; k < j + L; k++) {
        if (board[i][k] !== prev - 1 || visited[k]) isOk = false; // 같은 높이이고, 경사로 없는지 확인
    }

    if (isOk) {
        for (let k = j; k < j + L; k++) { // 경사로 둘 수 있으면 경사로 놓기
            visited[k] = true;
        }
    } else {
        flag = false; // 경사로 놓을 수 없으면 확인 그만하기
    }
 
    prev = board[i][j]; // 이전 위치 업데이트하기
    j += L - 1; // 경사로 놓은 만큼 인덱스 증가시키기 
}

(3) 이전에 방문한 길보다 1칸 높으면, 현재의 직전 위치부터 (위치를 감소시키며) 경사로의 길이 L동안 모두 같은 높이를 가지고 있는지 확인한다.

- 경사로는 낮은 칸에 두어야 하기 때문에, 현재 위치한 곳이 높으면 더 낮은 곳에 두기 위해서 낮은 곳의 인덱스를 확인한다.

- (2)번과 마찬가지로 확인해준다.

- 현재 위치보다 이전의 위치를 확인하고 있기 때문에 인덱스를 증가시킬 필요가 없다. 

else if (board[i][j] === prev + 1) {
            let isOk = true;

            if (j - L < 0) {
                flag = false;
                break;
            }

            for (let k = j - 1; k >= j - L; k--) {
                if (board[i][k] !== prev || visited[k]) {
                    isOk = false;
                }
            }

            if (isOk) {
                for (let k = j - 1; k >= j - L; k--) {
                    visited[k] = true;
                }
            } else {
                flag = false;
            }

            prev = board[i][j];
        }

(4) 다음 위치가 높이 1 초과로 차이난다면 이동이 불가능하므로 확인을 그만둔다. 

else {
    flag = false;
    break;
}

주의 

인덱스의 범위를 설정할 때 매우 매우 헷갈리는 문제이다. 풀기 전에 설계할 때 그림 그려보면서 인덱스에 대한 감을 잡고 구현하는 것을 추천한다. 

 

✅ 성공