[BOJ 3197] 백조의 호수

BOJ 3197

문제

풀이

R과 C 모두 1,500으로 총 칸은 최대 2,250,000개.
백조 두 마리가 존재하므로 최소의 물 영역은 2칸. 즉, 적어도 1,500일 안에는 모든 얼음이 녹고 백조가 만나게 된다.

그러나 매번 하루씩 bfs 또는 dfs를 통해 백조가 만나는지 확인한다면 매일 225만 번의 탐색을 하게 되므로 시간상 불가능. 따라서 Union find를 통해 두 백조가 있는 칸이 서로 이어져 있는지 확인하도록 한다.

또한 bfs를 사용하면 방문 처리를 위해 visited 배열을 생성해야 하는데, 원본의 크기가 워낙 커서 메모리 초과가 발생하므로 dfs를 사용하였다. 얼음의 경우에는 녹게 될 얼음과 대체될 인덱스를 기억하여 별다른 탐색 없이 union set의 인덱스로 처리가 가능하도록 하였다.

코드 (JavaScript)

const vectors = [
    [-1, 0],
    [1, 0],
    [0, 1],
    [0, -1]
]

function main() {
    const [rc, ...input] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n').map(el => el.trim());
    const [R, C] = rc.split(' ').map(Number);

    // init
    // field를 형성하고, 빈 칸이라면 dfs를 통해 인접한 물 공간에 동일한 인덱스를 부여한다.
    // 백조가 있다면 해당 공간에 부여된 인덱스를 따로 기억해둬 이후 Root 검색과 비교를 통해 서로 이어져있는지 확인하도록한다.
    const field = new Array(R);
    for (let i = 0; i < R; i++) {
        field[i] = [...input[i].split('')];
    }

    const isMelted = new Array(R).fill(0).map(() => new Array(C).fill(false)); // 얼음 방문처리용.
    const union = [];
    const swans = [];
    let melt = []; // 녹게 될 얼음.
    let idx = 0;
    for (let i = 0; i < R; i++) {
        for (let j = 0; j < C; j++) {
            if (field[i][j] === '.' || field[i][j] === 'L') {
                dfs(field, swans, idx, isMelted, melt, R, C, i, j);
                union.push(idx++);
            }
        }
    }

    let answer = 0;
    while(true) {
        if (findRoot(union, swans[0]) === findRoot(union, swans[1])) break;
        melt = melting(field, union, isMelted, melt, R, C);
        answer++;
    }

    console.log(answer);
}

function dfs(field, swans, idx, isMelted, melt, R, C, i, j) {
    if (field[i][j] !== '.' && field[i][j] !== 'L') return; // 얼음이라면 리턴.
    if (field[i][j] === 'L') swans.push(idx); // 백조라면 인덱스를 기억함.

    field[i][j] = idx;

    for (let [vy, vx] of vectors) {
        const ny = i + vy;
        const nx = j + vx;

        if (ny < 0 || ny >= R || nx < 0 || nx >= C) continue; // field 범위 확인
        if (field[ny][nx] === 'X') { // 바다에 인접한 얼음은 녹게 될 얼음.
            isMelted[ny][nx] = true;
            melt.push([ny, nx, idx]);
        }
  
        dfs(field, swans, idx, isMelted, melt, R, C, ny, nx);
    }
}

function melting(field, union, isMelted, melt, R, C) {
  	// 내일 녹게 될 얼음.
    const nmelt = [];

    // 얼음이 녹은 지점을 인덱스로 변경하고, 해당 지점 사방탐색하여 다음에 녹을 얼음의 위치를 저장함.
    melt.forEach(([i, j, idx]) => {
        field[i][j] = idx;

        for (let [vy, vx] of vectors) {
            const ny = i + vy;
            const nx = j + vx;
    
            if (ny < 0 || ny >= R || nx < 0 || nx >= C) continue;
            if (field[ny][nx] === 'X' && !isMelted[ny][nx]) {
                isMelted[ny][nx] = true;
                nmelt.push([ny, nx, idx]);
            }
        }
    })

  	// 녹은 얼음 주위의 인덱스를 구해 서로 union을 형성함.
    melt.forEach(([i, j, idx]) => {
        const adjSet = new Set();

        adjSet.add(idx);
        for (let [vy, vx] of vectors) {
            const ny = i + vy;
            const nx = j + vx;

            if (ny >= 0 && ny < R && nx >= 0 && nx < C && (field[ny][nx] !== 'X')) {
                adjSet.add(field[ny][nx]);
            }
        }

        const adjArray = Array.from(adjSet);
        for (let i = 1; i < adjArray.length; i++) {
            makeUnion(union, adjArray[i - 1], adjArray[i]);
        }
    })

    return nmelt;
}

function findRoot(union, a) {
    if (union[a] === a) return a;
    else return union[a] = findRoot(union, union[a]);
}

function makeUnion(union, a, b) {
    const aRoot = findRoot(union, a);
    const bRoot = findRoot(union, b);

    if (aRoot === bRoot) return false;
    else {
        union[bRoot] = aRoot;
        return true;
    }
}

main();