[백준] 0921 오늘의 문제 풀이📚

항상 문제를 다 풀고, 자바스크립트30도 공부하고

엄청 질질 끌다가 새벽에 포스팅을 하게 되는 것 같다.

어차피 질질 끌 거, 그냥 일찍 포스팅하고 자는 게 나은가?

 

1. 불!

문제 링크

var input = [];
const readline = require('readline');
const fs = require('fs');

const r = readline.createInterface({
    input: process.stdin
});

r.on('line', function(line) {
    input.push(line.trim());
});

r.on('close', function() {
    const firstLine = input.shift().split(' ');
    const r = Number(firstLine[0]);
    const c = Number(firstLine[1]);

    let J = [];
    let F = [];

    const maze = new Array(r);
    const fire = new Array(r);
    const jihoon = new Array(r);

    for(let i = 0; i < r; i++) {
        maze[i] = new Array(c);
        jihoon[i] = new Array(c).fill(0);
        fire[i] = new Array(c).fill(0);
        for(let j = 0; j < c; j++) {
            maze[i][j] = input[i][j];

            if(maze[i][j] === 'F') {
                F.push([i, j]);
            } else if(maze[i][j] === 'J') {
                J = [i, j];
            }
        }
    }

    const queue = [];
    const dirX = [1, -1, 0, 0];
    const dirY = [0, 0, -1, 1];

    function bfsForJ() {
        const Jstart = J;
        jihoon[Jstart[0]][Jstart[1]] = 1;
        queue.push([Jstart[0], Jstart[1]]);

        while(queue.length > 0) {
            const cur = queue.shift();

            for(let i = 0; i < 4; i++) {
                const nextX = cur[0] + dirX[i];
                const nextY = cur[1] + dirY[i];

                if(nextX < 0 || nextY < 0 || nextX >= r || nextY >= c) {
                    console.log(jihoon[cur[0]][cur[1]]);
                    return;
                }

                if(nextX >= 0 && nextY >= 0 && nextX < r && nextY < c) {
                    if(jihoon[nextX][nextY] === 0 && maze[nextX][nextY] !== '#') {
                        if(!fire[nextX][nextY] || fire[nextX][nextY] > jihoon[cur[0]][cur[1]] + 1) {
                            jihoon[nextX][nextY] = jihoon[cur[0]][cur[1]] + 1;
                            queue.push([nextX, nextY]);
                        }
                    }
                }
            }
        }
        console.log("IMPOSSIBLE");
    }

    const queue_2 = [];

    function bfsForFire() {
        while(F.length > 0) {
            const Fstart = F.pop();
            fire[Fstart[0]][Fstart[1]] = 1;
            queue_2.push(Fstart);
        }

        while(queue_2.length > 0) {
            const cur = queue_2.shift();

            for(let i = 0; i < 4; i++) {
                const nextX = cur[0] + dirX[i];
                const nextY = cur[1] + dirY[i];

                if(nextX >= 0 && nextY >= 0 && nextX < r && nextY < c) {
                    if(fire[nextX][nextY] === 0 && maze[nextX][nextY] !== '#') {
                        fire[nextX][nextY] = fire[cur[0]][cur[1]] + 1;
                        queue_2.push([nextX, nextY]);
                    }
                }
            }
        }
    }

    if(F) {
        bfsForFire(F[0], F[1]);
    }
    bfsForJ(J[0], J[1]);
});

이 문제도 좀 기초적인 응용이라는 얘기가 있던데, 적어도 나한테만큼은 너무나 어려웠다..

일단 지훈이와 불을 각각 BFS를 돌려야 했으며, 여러 가지 테스트 케이스도 직접 생각해내야 했다.

반례(테스트 케이스) 찾는게 알고리즘 코드 짜는 것보다 더 힘든 것 같다.

이 문제에서는 일단

 

1. 테스트 케이스가 1X1일 때도 고려해야 하고(최소 케이스)

2. 문제에서 불이 1개인 테스트 케이스가 주어졌다고 해서, 불이 무조건 하나밖에 없을 거란 생각을 했으면 안됐다.

문제에 '불은 반드시 한 곳에서 발생한다'라는 조건이 없었기 때문에, 불이 여러 곳에서 발생하는 경우를 고려해야 한다.

3. 또, 지훈이가 벽에 다닥다닥 붙어있는 경우도 고려해야 한다.

 

솔직히 약간 집중을 못해서 그런지, 2번은 생각지도 못했다.

지훈이는 사람이니까 당연히 하나이지만, 불은 한 곳에서만 발생하는 게 아니라는 생각을 전혀 못했다.

이제 알았으니까, 앞으로는 반례 생각할 때 이런 것들을 다 고민해봐야겠다.

 

2. 숨바꼭질

문제 링크

 

a. 혼자서 풀기

var input = [];
const readline = require('readline');
const fs = require('fs');
const { count } = require('console');

const r = readline.createInterface({
    input: process.stdin
});

r.on('line', function(line) {
    input.push(line.trim());
});

r.on('close', function() {
    const line = input[0].split(' ');
    const N = Number(line[0]);
    const K = Number(line[1]);
    const len = 100001;

    const location = new Array(len).fill(0);
    location[K] = 1;
    const visit = new Array(len).fill(0);

    const queue = [];

    function seek(x) {
        queue.push(x);
        visit[x] = 1;

        while(queue.length > 0) {
            const cur = queue.shift();

            if(location[cur] === 1) {
                return visit[cur] - 1;
            }

            if(cur + 1 < len && visit[cur + 1] === 0) {
                queue.push(cur + 1);
                visit[cur + 1] = visit[cur] + 1;
            }

            if(cur - 1 >= 0 && visit[cur - 1] === 0) {
                queue.push(cur - 1);
                visit[cur - 1] = visit[cur] + 1;
            }

            if(2 * cur < len && visit[2 * cur] === 0) {
                queue.push(2 * cur);
                visit[2 * cur] = visit[cur] + 1;
            }
        }
    }

    console.log(seek(N));
});

b. 참고해서 다시 풀기

var input = [];
const readline = require('readline');
const fs = require('fs');
const { count } = require('console');

const r = readline.createInterface({
    input: process.stdin
});

r.on('line', function(line) {
    input.push(line.trim());
});

r.on('close', function() {
    const line = input[0].split(' ');
    const N = Number(line[0]);
    const K = Number(line[1]);
    const len = 100001;

    const visit = new Array(len).fill(0);

    const queue = [];

    function seek(x) {
        queue.push(x);
        visit[x] = 1;

        while(queue.length > 0) {
            const cur = queue.shift();

            if(visit[K] !== 0) {
                return visit[K] - 1;
            }

            if(cur + 1 < len && visit[cur + 1] === 0) {
                queue.push(cur + 1);
                visit[cur + 1] = visit[cur] + 1;
            }

            if(cur - 1 >= 0 && visit[cur - 1] === 0) {
                queue.push(cur - 1);
                visit[cur - 1] = visit[cur] + 1;
            }

            if(2 * cur < len && visit[2 * cur] === 0) {
                queue.push(2 * cur);
                visit[2 * cur] = visit[cur] + 1;
            }
        }
    }

    console.log(seek(N));
});

굳이 배열을 두 개 쓰지 않고, 동생이 있는 자리에 숫자가 0에서 달라진다면

그 숫자를 바로 return하면 된다는 것을 알았다(물론 다른사람 풀이를 보고..).

 

사실 이 문제는 예전에 한 번 풀어봤는데, 그 때 되게 신선하다고 느꼈던 기억이 있다.

물론, BFS 문제를 많이 접해보지 못해서 그렇게 느낀거겠지만..

항상 상, 하, 좌, 우로 움직이는 BFS에만 익숙해져있다가

이렇게 경우를 직접 나눠서 푸는 것이 되게 낯설었다.

BFS의 틀을 깨준 문제랄까.

 

아, 그리고 이 문제에서도 함부로 단정짓고 넘어가면 안 되는 것이 있다.

문제에서 수빈이와 동생이 0 ~ 100,000 사이에 위치해야 한다고 조건이 나와있는데

이것이, 수빈이가 이동할 때 0 ~ 100,000을 벗어나선 안된다는 말은 아니다.

수빈이가 저 범위를 벗어났다가, 다시 범위 내로 들어와서 동생을 찾을 수도 있는 거니까.

 

물론 이 문제에서는 범위 밖으로 벗어나는 경우가 매우 비효율적이기 때문에

0 ~ 100,000 까지의 범위만 고려해주면 되긴 하지만

사실은 문제의 조건에 따라 0 ~ 200,000(두 배 순간이동 할 수 있으니)까지 고려해야 할 수도 있었다는 점.

문제의 조건을 함부로 제한하지 않도록 주의하자.