[Softeer] 동계 테스트 시점 예측 JS

https://softeer.ai/practice/6281

북위 65도. 스웨덴의 소도시 아르예플로그(Arjeplog)에 자리한 동계 테스트 센터. 겨울 내내 얼음 두께가 1M 내외로 유지되는 광할한 얼음 호수와 그냥 걷기조차 힘든 눈길을 무대로 현대자동차그룹 연구원들은 극한 환경 속에서 더 나은 차량 성능을 확보하기 위해 제동안정성, 주행안정성, ADAS 기능 등에 대한 다양한 평가를 숨가쁘게 이어가고 있다.

이 곳은 기온이 너무 추워서 아침에 출근해보면 테스트 차량들 위에 큰 눈얼음이 생겨 있다. 정상적인 테스트를 위해서는 커다란 얼음이 어느정도 녹고 난 뒤에 가능한데, 차량 마다 당일의 테스트 가능 시점을 알기 위한 예측 프로그램을 제작 중에 있다.

예측 프로그램은 N×M (5 ≤ N, M ≤ 100)의 격자 화면 위에 눈 얼음의 모양을 작은 정사각형들이 집합되어 있는 모양으로 변환하여 위 그림과 같이 표시해 준다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 얼음은 아침이 되면 기온이 상승하여 천천히 녹는다.

그런데 화면에서 나타난 얼음의 모양은 작은 정사각형 모양의 4변 중에서 적어도 2변 이상이 외부의 공기와 접촉했을 때 정확히 한 시간 만에 녹아 없어져 버린다. 따라서 위 그림의 모양과 같은 얼음(파란으로 표시된 부분)라면 C로 표시된 모든 얼음 격자는 한 시간 후에 사라진다.

위와 같이 얼음 내부에 있는 공간은 얼음 외부 공기와 접촉하지 않는 것으로 가정한다. 그러므로 이 공간에 접촉한 얼음 격자는 녹지 않고 C로 표시된 얼음 격자만 사라진다. 그러나 한 시간 후, 이 공간으로 외부공기가 유입되면, 아래 그림에서와 같이 C로 표시된 얼음 격자들이 사라지게 된다.

격자 화면의 맨 가장자리에는 얼음이 놓이지 않는 것으로 가정한다. 입력으로 주어진 얼음이 모두 녹아 없어지는데 걸리는 정확한 시간을 구하는 프로그램을 작성해보자.

제약조건

5 ≤ N, M ≤ 100

입력형식

첫째 줄에는 격자 화면의 크기를 나타내는 두 개의 정수 N, M이 주어진다. 그 다음 N개의 줄에는 격자 화면 위에 얼음이 있는 부분은 1로 표시되고, 얼음이 없는 부분은 0으로 표시된다. 또한, 각 0과 1은 하나의 공백으로 분리되어 있다.

출력형식

출력으로는 주어진 얼음이 모두 녹아 없어지는데 걸리는 정확한 시간을 정수로 첫 줄에 출력한다.

입력예제1

8 9 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

출력예제1

4

---

문제요점

N세로, M가로, 2변이상 접촉시 1시간 후 없어짐
얼음내부공간은 접촉하지 않는것으로 판단
모두 녹는데 필요한 시간 출력

 

풀이

• bfs로 외부, 내부공기 구분 (외부 . / 얼음 1 / 내부 0  )
• 외부공기와 2면이상 맞닿아 녹을 얼음 기록하기
• 녹을 얼음들 모두 외부공기로 바꿔주기
• 남은 얼음이 있는지 확인하기
• 위의 과정을 남은 얼음이 없을 때까지 진행하기

 

코드

const readline = require('readline');
const rl = readline.createInterface({
    input : process.stdin,
    output : process.stdout
});

const lines = [];

// input
rl.on('line', input => {
    lines.push(input.split(' ').map(e => parseInt(e)))
})

// output
let size = {}
let map;
rl.on('close', () => {
    const [height, width] = lines.shift();
    size.h = height;
    size.w = width;
    map = lines;
    let time = 0;

    while(1) {
        updateOutsideAir(); // 외부, 내부 공기 구분
        meltIce(); // 얼음 녹이기
        time++;
        if (isAllMelted()) break; // 얼음 남아있는지 검사
    }
    console.log(time);
    process.exit();
})

const dr = [-1, 0, 1, 0];
const dc = [0, 1, 0, -1];
    
// 외부공기를 찾아서 . 로 표시
function updateOutsideAir() {
    const queue = [{r: 0, c: 0}];
    const isVisited = Array.from({ length: size.h }, () => Array.from({ length: size.w }, () => false));
    map[0][0] = '.'; 
    isVisited[0][0] = true;
    
    while(queue.length) {
        const {r, c} = queue.shift();
        for (let i = 0; i < 4; i++) {
            const nextR = r + dr[i];
            const nextC = c + dc[i];

            // 아직 방문하지 않고 얼음이 아닌 곳을 만난다면
            if (isInsideArr(nextR, nextC) &&
                !isVisited[nextR][nextC] &&
                map[nextR][nextC] !== 1
            ) {
                map[nextR][nextC] = '.'; // 외부공기
                isVisited[nextR][nextC] = true;
                queue.push({ r: nextR, c: nextC });
            }
        }
    }
}

function meltIce() {
    const gonnaMelt = [];
    for (let r = 0; r < size.h; r++) {
        for (let c = 0; c < size.w; c++) {
            // 얼음을 찾음
            if (map[r][c] === 1) {
                let edge = 0; // 외부와 맞닿은 면 갯수
                // 상하좌우를 탐색하며 녹을 얼음인지 확인
                for (let i = 0; i < 4; i++) {
                    const nextR = r + dr[i];
                    const nextC = c + dc[i];

                    if (isInsideArr(nextR, nextC) && map[nextR][nextC] === '.') {
                        edge++;
                    }
                }
                // 외부와 맞닿은 갯수가 2개이상이면 녹을거임
                if (edge >= 2) {
                    gonnaMelt.push([r, c]);
                }
            }
           
        }
    }
    // 녹을 얼음들 표시하기
    for (const [r, c] of gonnaMelt) {
        map[r][c] = '.';
    }
}

function isInsideArr(r, c) {
  return r >= 0 && r < size.h && c >= 0 && c < size.w;
}


function isAllMelted() {
    for (let r = 0; r < size.h; r++) {
        for (let c = 0; c < size.w; c++) {
            if (map[r][c] === 1) return false;
        }
    }
    return true;
}

 

 

 

3번 케이스가 어떤 경우인지 아직 모르겠다..

혹시 아시는 분 있으시면 댓글 달아주세요 감사합니다!

 

 

참고

https://chanhuiseok.github.io/posts/baek-33/