2023.08.03[Softeer 장애물 인식 프로그램/백준 2667번 단지 번호 붙이기]

Softeer라는 사이트에서 코테준비를 하다가 거의 하루종일 삽질을 했다!

https://softeer.ai/practice/info.do?idx=1&eid=409 

Softeer

BFS/DFS를 이용해서 풀 수 있는 기본 문제였다. 개념만 알고 문제를 혼자서 제대로 풀어본 적이 없어서 공부하기 적절한 문제라고 생각했다.

이전에 공부한 문제랑 풀이 방법이 비슷할 것 같아서 예제를 해결하고 된건가 하고 있었는데 웬걸 제출해보니 테스트 케이스가 3개 빼고 다 오답이었다...

 

const fs = require('fs');

const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n").map(e => e.split("").map(Number));
const N = +input.shift();
const dx = [1, -1, 0, 0];
const dy = [0, 0, 1, -1];
const result = [];

const bfs = (y, x) => {
    let count = 0;

    const queue = [];
    queue.push([y, x]);
    input[y][x] = 0;

    while(queue.length > 0) {
        const [y, x] = queue.shift();
        count += 1;

        for(let i = 0; i<4; i++) {
            const moveX = x + dx[i];
            const moveY = y + dy[i];
        
            if(moveX >= 0 && moveX < N && moveY >= 0 && moveY < N && input[moveY][moveX]) {
                queue.push([moveY, moveX]);
                input[moveY][moveX] = 0;
            }
        }
    }

    result.push(count);
}

for(let y = 0; y<N; y++) {
    for(let x = 0; x<N; x++){
        if(!input[y][x]) continue;  
        bfs(y, x);
    }
}

console.log(`${result.length}
${result.join('\n')}`)

 

정말 한~~~참을 풀이를 보고 다른 사람 풀이랑 비교해도 도저히 틀리는 이유를 찾을 수 없었다. 블로그 글이 많은 문제가 아니라서 반례를 찾기가 더 힘들었다 ㅠㅠ 그러다가 똑같은 문제를 백준에서 발견했다.

 

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

2667번: 단지번호붙이기

 

이 문제에서도 어김없이 오답이 떠서 게시판에 올라온 반례들을 하나씩 테스트해봤다.

그런데 웬만한 반례는 다 통과해서 더 답답했다... 반례를 찾아야 어디서 잘못됐는지 찾기 쉬울텐데..!! 하고 계속 반례를 찾다가

12 000000000000 000000000001 000000000001 000000000001 000000000001 000000000001 000000000001 000000000001 000000000001 000000000001 000000000001 011111111111

이 반례로 테스트해보니 출력값이 잘못된 것을 발견했다!!

 

그래서 어디서 잘못된건지 하나하나 찾아보니.. input을 정제하는 과정에서 첫번째 줄은 N 값인데 같이 이중배열로 만들어버려서 N이 두자리수가 되면 의도와 다르게 작동하고 있던 것이다..!! 다른 반례들이 오류가 없었던 게 신기하다...

 

정말 허무한 실수를하고 있었지만덕분에 드디어 하루종일 속썩였던 문제를 해결할 수 있었다 ㅠㅠㅠ 해결되서 정말 다행이야...

const fs = require('fs');

const input = fs.readFileSync('/dev/stdin').toString().split("\n");
const N = input.shift();
const splitInput = input.map(e => e.trim().split("").map(Number));
const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];
const result = [];

const bfs = (x, y) => {
    let count = 0;

    const queue = [];
    queue.push([x, y]);
    splitInput[x][y] = 0;

    while(queue.length) {
        const [x, y] = queue.shift();
        count += 1;

        for(let i = 0; i<4; i++) {
            const moveX = x + dx[i];
            const moveY = y + dy[i];
        
            if(moveX >= 0 && moveX < N && moveY >= 0 && moveY < N && splitInput[moveX][moveY] === 1) {
                queue.push([moveX, moveY]);
                splitInput[moveX][moveY] = 0;
                
            }
        }
    }

    return count;
}

for(let x = 0; x<N; x++) {
    for(let y = 0; y<N; y++){
        if(splitInput[x][y] === 1) {
            result.push(bfs(x, y))};
    }
}

console.log(result.length)
console.log(result.sort((a, b) => a - b).join('\n'))

 

문제 해결!!