[백준] 0920 어제의 문제 풀이📚

BFS 문제 위주로 풀어봤다.

일단은 여러 유형들을 위주로 쉬운 문제부터 풀어봤는데 생각보다는 괜찮았던 듯.

예전에 풀었던 BFS 문제도 한 번 풀어봤는데 한 번에 풀려서 다행.

 

일단 BFS의 기본 틀은 거의 여기서 변하지 않는다.

const whole = new Array(n);
const visit = new Array(n);
for(let i = 0; i < n; i++) {
    whole[i] = new Array(m);
    for(let j = 0; j < m; j++) {
        whole[i][j] = Number(input[i].split(' ')[j]);
    }
    visit[i] = new Array(m).fill(0);
}

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

function bfs(x, y) {
    visit[x][y] = 1;
    queue.push([x, y]);

    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 < n && nextY < m) {
                if(visit[nextX][nextY] === 0 && whole[nextX][nextY] === 1) {
                    visit[nextX][nextY] = 1;
                    queue.push([nextX, nextY]);
                }
            }
        }
    }
}

 

1. 그림

문제 링크

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

const file = 'input.txt';
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 n = Number(firstLine[0]);
    const m = Number(firstLine[1]);

    const whole = new Array(n);
    const visit = new Array(n);
    for(let i = 0; i < n; i++) {
        whole[i] = new Array(m);
        for(let j = 0; j < m; j++) {
            whole[i][j] = Number(input[i].split(' ')[j]);
        }
        visit[i] = new Array(m).fill(0);
    }

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

    let max = 0;
    let count = 0;

    function bfs(x, y) {
        let size = 1;
        visit[x][y] = 1;
        queue.push([x, y]);

        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 < n && nextY < m) {
                    if(visit[nextX][nextY] === 0 && whole[nextX][nextY] === 1) {
                        visit[nextX][nextY] = 1;
                        queue.push([nextX, nextY]);
                        size++;
                    }
                }
            }
        }

        if(max < size) max = size;
    }

    for(let i = 0; i < n; i++) {
        for(let j = 0; j < m; j++) {
            if(whole[i][j] === 1 && visit[i][j] === 0) {
                bfs(i, j);
                count++;
            }
        }
    }
    console.log(count);
    console.log(max);
});

매우 기초적인 BFS 문제였다.

딱히 함정도 없고 응용도 없는.

 

2. 미로 탐색

문제 링크

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

const file = 'input.txt';
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 n = Number(firstLine[0]);
    const m = Number(firstLine[1]);

    const maze = new Array(n);
    const visit = new Array(n);

    for(let i = 0; i < n; i++) {
        maze[i] = new Array(m);
        visit[i] = new Array(m).fill(0);
        for(let j = 0; j < m; j++) {
            maze[i][j] = Number(input[i][j]);
        }
    }

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

    function bfs(x, y) {
        visit[x][y] = 1;
        queue.push([x, y]);

        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 < n && nextY < m) {
                    if(visit[nextX][nextY] === 0 && maze[nextX][nextY] === 1) {
                        visit[nextX][nextY] = visit[cur[0]][cur[1]] + 1;
                        queue.push([nextX, nextY]);
                    }
                }
            }
        }
    }

    bfs(0, 0);
    console.log(visit[n-1][m-1]);
});

그림 문제보다는 한 단계 더 응용되긴 했지만

(지나간 루트에다가 거리를 표시해야 한다는)

그럼에도 불구하고 아주 기초적인 문제.