[백준] 22860_폴더 정리 (small) (Javascript)

문제

BOJ22860_폴더 정리

코드 (런타임 에러)

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [N, M] = input[0].split(' ').map(Number);
const fileFolder = input.slice(1, N + M + 1).map((e) => e.split(' '));
const Q = +input[N + M + 1];
const query = input.slice(N + M + 2).map((e) => e.split('/'));
let answer = '';

const tree = { main: [] };
fileFolder.forEach(([p, f, c]) => {
    tree[p].push([f, c]);
    if (c === '1') tree[f] = [];
});

query.forEach((q) => {
    const folder = q.at(-1);
    bfs(folder);
});

function bfs(folder) {
    let files = [];
    let filesNoDup = new Set();
    const queue = [folder];
    let front = 0;
    while (queue.length > front) {
        const f = queue[front++];
        for (let next of tree[f]) {
            // 폴더일 경우
            if (next[1] === '1') {
                queue.push(next[0]);
            } else {
                files.push(next[0]);
                filesNoDup.add(next[0]);
            }
        }
    }
    answer += `${filesNoDup.size} ${files.length}\n`;
}

console.log(answer.trimEnd());

쿼리가 아래와 같이 주어졌을 때 에러 발생

main FolderA 1
FolderB File1 0 <- 에러 발생
main FolderB 1

tree 를 생성하는 부분에서 tree[p] 가 없을 경우 push() 함수를 사용하면 에러가 발생하기 때문에 아래와 같이 수정해주었다.

코드 (틀렸습니다)

. . .

    const tree = {};
    fileFolder.forEach(([p, f, c]) => {
        if (tree[p]) tree[p].push([f, c]);
        else {
          tree[p] = [];
          tree[p].push([f, c]);
        }
        if (c === '1') tree[f] = [];
    });

. . .

쿼리가 아래와 같이 주어졌을 때 잘못된 결과 출력

FolderA File1 0
main FolderA 1

첫 번째 쿼리로 FolderA와 File1을 연결시켰는데, 두 번째 쿼리에 의해서 FolderA 가 빈 배열로 초기화되어서 File1 과의 연결 정보가 사라진다.

코드 (맞았습니다)

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [N, M] = input[0].split(' ').map(Number);
const fileFolder = input.slice(1, N + M + 1).map((e) => e.split(' '));
const Q = +input[N + M + 1];
const query = input.slice(N + M + 2).map((e) => e.split('/'));
let answer = '';

const tree = {};
fileFolder.forEach(([p, f, c]) => {
    if (tree[p]) tree[p].push([f, c]);
    else {
        tree[p] = [];
        tree[p].push([f, c]);
    }
    if (c === '1' && !tree.hasOwnProperty(f)) tree[f] = [];
});

query.forEach((q) => {
    const folder = q.at(-1);
    bfs(folder);
});

function bfs(folder) {
    let files = [];
    let filesNoDup = new Set();
    const queue = [folder];
    let front = 0;
    while (queue.length > front) {
        const f = queue[front++];
        for (let next of tree[f]) {
            // 폴더일 경우
            if (next[1] === '1') {
                queue.push(next[0]);
            } else {
                files.push(next[0]);
                filesNoDup.add(next[0]);
            }
        }
    }
    answer += `${filesNoDup.size} ${files.length}\n`;
}

console.log(answer.trimEnd());

풀이

이 코드는 크게 두 부분으로 나뉜다.

1. 폴더 경로를 기반으로 트리 만들기
2. 하위 디렉토리를 탐색하며 파일 개수 찾기

우선 1번부터 살펴보자

const tree = {};
fileFolder.forEach(([p, f, c]) => {
    if (tree[p]) tree[p].push([f, c]);
    else {
        tree[p] = [];
        tree[p].push([f, c]);
    }
    if (c === '1' && !tree.hasOwnProperty(f)) tree[f] = [];
});

트리를 객체로 만들어서 key-value 형태로 만들어준다.
여기서 key는 상위 폴더 이름이 되고, value는 상위 폴더의 하위에 있는 폴더나 파일들의 이름이 배열형태로 저장된다.

예를 들어 아래와 같은 입력이 주어졌을 때,

main FolderA 1
main FolderB 1
FolderA File1 0
FolderA File2 0
FolderB FolderC 1
FolderB File1 0
FolderB File3 0

아래와 같은 형식으로 트리가 만들어진다.

그리고 쿼리를 '/'로 나눈 배열의 마지막 인덱스에 있는 폴더명을 기준으로 탐색을 시작한다.

query.forEach((q) => {
    const folder = q.at(-1);
    bfs(folder);
});

bfs 함수 안에서는 파일의 총 개수를 저장하기 위해 파일명을 저장할 배열(files)과, 파일 종류의 개수를 저장하기 위해 중복을 제거하는 Set 객체를 만들어준다.

function bfs(folder) {
    let files = [];
    let filesNoDup = new Set();
    const queue = [folder];
    let front = 0;
    while (queue.length > front) {
        const f = queue[front++];
        for (let next of tree[f]) {
            // 폴더일 경우
            if (next[1] === '1') {
                queue.push(next[0]);
            } else {
                files.push(next[0]);
                filesNoDup.add(next[0]);
            }
        }
    }
    answer += `${filesNoDup.size} ${files.length}\n`;
}

그리고 BFS를 반복하며 현재 폴더의 하위 목록들을 전부 탐색하며, 폴더의 경우 큐에 삽입하여 해당 폴더의 하위 목록들도 전부 탐색하도록 하고, 파일일 경우 files 변수와 filesNoDup 변수에 저장한다.

BFS탐색을 마쳤다다면, 정답을 저장할 answer 변수에 files 와 filesNoDup 의 길이를 전달하여 파일의 총 개수와, 파일의 종류의 개수를 저장할 수 있도록 한다.

그렇게 모든 쿼리를 마쳤다면 답을 출력해주면 된다.

console.log(answer.trimEnd());