[백준 3085] 사탕 게임 with Node.js

문제 링크

www.acmicpc.net/problem/3085

3085번: 사탕 게임

풀이

const input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");
const n = +input[0];
const candy = input.slice(1).map(v => v.split(""));

function swap(i, j, k) {
    const coord = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    const here = candy[i][j];
    if (candy[i+coord[k][0]]
        && candy[i+coord[k][0]][j+coord[k][1]]
        && here !== candy[i+coord[k][0]][j+coord[k][1]]) {
        candy[i][j] = candy[i+coord[k][0]][j+coord[k][1]];
        candy[i+coord[k][0]][j+coord[k][1]] = here;
        return true;
    } else return false;
}

function search() {
    for (let l=0; l<2; l++) {
        for (let x=0; x<n; x++) {
            let count = 0;
            let color = curCandy(x, 0, l);
            for (let y=0; y<n; y++) {
                if (curCandy(x, y, l) === color) {
                    count++;
                    if (count > maxCount) {
                        maxCount = count;
                    }
                } else {
                    color = curCandy(x, y, l);
                    count = 1;
                }
            }
        }
    }
}

function curCandy(x, y, l) {
    if (l === 0) return candy[x][y];
    else return candy[y][x];
};

let maxCount = 0;
for (let i=0; i<n; i++) {
    for (let j=0; j<n; j++) {
        for (let k=0; k<4; k++) {
            if (swap(i, j, k)) {
                search()
                swap(i, j, k)
            }
        }
    }
}

console.log(maxCount);

브루트포스로 푸는 문제라지만, 솔직히 이 풀이는 조금 부끄럽다...

 

swap은 두 사탕의 위치를 바꾸는 함수이며, 선택한 사탕의 위치에서 상하좌우 중에 하나를 고르는데, 이 때 해당 방향에 사탕이 존재하지 않거나, 같은 색의 사탕일 경우에는 위치를 바꾸지 않는다.search는 사탕 전체에서 같은 색이 연속인 경우를 찾으며, 길이가 maxCount보다 길 경우 maxCount를 갱신하는 함수이다. curCandy는 가로줄/세로줄을 모두 탐색해야 하는데, 전체 반복문 코드를 중복하지 않게 하려고 작성하였다.

 

먼저 사탕을 2차원 배열에 담는다. 그리고 사탕을 하나씩 순회하면서 인접한 사탕과 위치를 바꾸고, 가장 긴 연속된 사탕의 길이를 구하고, 다시 위치를 원상복구한다.