문제
접근법
막대 던지기
- N번 동안 막대를 왼쪽 오른쪽 번갈아가며 던져야 한다.
- 막대를 던지는 행위를 함수
throwStick()을 만들고 이를 N번 실행한다.- 막대를 던지는 방향에 따라 파괴되는 미네랄이 달라지므로 왼쪽에서 던지는지 오른쪽에서 던지는지 구별할 필요가 있다. 따라서
throwStick()함수는 "방향(왼쪽, 오른쪽)"을 매개변수로 받는다.- 그리고 막대를 던지는 높이에 있는 미네랄이 파괴되는 것이므로 해당 높이에 있는 미네랄 배열을 매개변수로 받는다.
클러스터가 분리되었는지 확인
- 막대를 한 번 던졌을 때 미네랄이 파괴되어 클러스터가 분리될 수도 있다. 따라서 클러스터가 분리되었는지 확인을 해야 한다.
- 2중 for문을 돌며 동굴의 모든 공간을 확인하면서 현재 공간이 미네랄('x') 이라면 그때의 위치(x, y)를 출발점으로 하여 bfs를 수행한다.
- bfs에서는 연결된 모든 미네랄에 방문하며 방문처리를 해준다. bfs를 마무리하면 queue에는 한 클러스터를 구성하는 미네랄들의 좌표가 담겨있다. 추후에 클러스터를 낙하시키기 위해 이 좌표값들이 사용될 수 있으므로 clusters 라는 배열에 좌표값들을 저장한다.
- 이로써 한 번의 bfs는 한 덩어리의 클러스터를 확인하는 것이 된다.
- bfs를 탈출하면 계속해서 2중 for문을 돌며 현재 공간을 확인한다. 만약 방문한 적 없는 미네랄('x') 을 만났다면 해당 미네랄은 아까 탐색했던 클러스터와 다른 클러스터에 속해있음을 의미한다. 즉 클러스터가 분리되었음을 의미한다.
- 이때도 마찬가지로 해당 좌표를 출발점으로 bfs를 수행해주고 clusters배열에 해당 클러스터를 구성하는 미네랄들의 좌표를 저장해주면 된다.
- 이로써 2중 for문이 종료되었을 때 clusters 배열의 길이가 2 이상이라면 클러스터가 분리되었음을 의미하므로 클러스터를 낙하시켜줘야 한다.
지금까지의 과정을 보자면 대략 아래 그림과 같다.
위와 같은 미네랄이 있고
막대를 던져서 미네랄이 파괴된다.
그리고 클러스터가 분리되었는지 확인하기 위에 bfs를 수행한다.
방문한 곳은 'T' 방문하지 않은 곳은 'F' 로 표시된다.
총 두개의 클러스터로 분리되었고, 이는 clusters 배열에 저장된다.
클러스터 낙하
- 만약 클러스터가 2개 이상이라면 땅이랑 이어져있지 않은 클러스터는 아래로 낙하를 수행해줘야 한다.
- 낙하란 미네랄이 y축으로 -1씩 이동하는 것을 의미한다.
- 낙하를 수행하는
fallDown()이라는 함수를 정의하고 클러스터의 좌표를 이동시키기 위해 하나의 클러스터(clusters[i])를 매개변수로 전달받도록 한다.- 만약 클러스터가 바닥이랑 이어져있을 경우에는 낙하하지 않기 때문에 해당 클러스터에서 y좌표가 가장 낮은 미네랄의 y값이 0이라면
fallDown()함수를 즉시 리턴하도록 한다.- 클러스터가 낙하할 때는 클러스터의 아래쪽 미네랄부터 낙하를 수행해줘야 한다. 만약 위에 있는 미네랄부터 낙하를 수행해줄 경우 아래에 있는 미네랄과 겹쳐질 수 있기 때문이다.
이를 위해 클러스터를 구성하는 미네랄들을 y좌표 기준으로 미리 오름차순 정렬을 수행해놓는다. 이렇게 하면 y값이 낮은 미네랄부터 낙하를 수행할 수 있다.
- 낙하시 클러스터의 모양은 변하지 않기 때문에 각각의 미네랄을 최대한 낙하시키는 것이 아니라 클러스터의 모든 미네랄들을 동시에 1칸씩 아래로 이동시켜야 한다. 그리고 그렇게 모든 미네랄을 이동시켰을 때 문제가 없는지 확인해야 한다.
- "문제가 없다"란 이동시켰을 때 모든 미네랄이 낙하가능한 지점에 있음을 의미하며, 낙하가 가능한 지점은 "빈 공간('.')" 을 말한다. 즉 낙하했을 때 미네랄과 겹치거나 땅 아래로 내려가면 안된다. 만약 클러스터중 한 미네랄이라도 낙하 불가능한 지점에 낙하할경우 낙하를 중단해야한다.
- 낙하를 중단했을 때 이미 낙하를 수행한 미네랄 들이 있을수도 있을 것이다. 이렇게 부분적으로 낙하했던 미네랄들은 바로 전 위치로 이동시켜야 한다. 따라서 낙하한 미네랄들의 좌표를 담기 위해
partOfCluster배열을 만들어서 미네랄이 낙하할 때마다 해당 배열에 삽입해준다.- 또한 부분적으로 낙하한 미네랄들을 원래 위치로 되돌릴 때는
partOfCluster에 들어온 "역순"으로 되돌려줘야 한다. 만약 정순으로 되돌려줄경우 미네랄이 겹쳐질 수 있기 때문이다.
사소한 포인트
입력값을 순서대로 배열에 저장할 경우 0번 인덱스가 바닥이 아니라 R-1번 인덱스가 바닥이 된다.
따라서 입력받은 배열을 거꾸로 뒤집어서 0번 인덱스가 바닥이 되도록 만들어주었고, 막대의 높이를 입력받을 때는 각각의 높이에 -1씩 해주어서 높이와 인덱스를 맞춰주었다.
코드
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
let R, C;
let cave = [];
let N; // 막대 던진 횟수
let height; // 던진 높이
rl.on('line', (line) => {
if (!R && !C) [R, C] = line.split(' ').map(Number);
else if (cave.length < R) cave.push(line.split(''));
else if (!N) N = +line;
else if (!height) height = line.split(' ').map((e) => +e - 1); //높이 1 감소
if (height) rl.close();
}).on('close', () => {
solution();
});
function solution() {
let L = false;
cave = cave.reverse();
const clusters = [];
const visited = Array.from(Array(R), () => Array(C).fill(false));
const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];
let answer = '';
for (let i = 0; i < N; i++) {
L = !L;
// 왼쪽 오른쪽 번갈아가며 막대기 던지기
// 콘솔창에 출력했을 때 R-1이 가장 바닥면임
throwStick(L, cave[height[i]]);
visited.forEach((e) => e.fill(false));
// 클러스터가 분리됐는지 확인
for (let i = 0; i < R; i++) {
for (let j = 0; j < C; j++) {
if (!visited[i][j] && cave[i][j] === 'x') {
visited[i][j] = true;
clusters.push(bfs(i, j));
}
}
}
// 클러스터가 두 개 이상이라면 땅과 이어져있지 않은 클러스터는 아래로 떨어져야 한다.
if (clusters.length > 1) {
// 각각의 클러스터의 미네랄을 y축 기준으로 오름차순 정렬
// 그러면 클러스터를 순회할 때 y축이 낮은 미네랄부터 접근할 수 있음
clusters.forEach((e) => {
e.sort((a, b) => a[0] - b[0]);
});
for (const cluster of clusters) {
fallDown(cluster);
}
}
// 클러스터 배열 초기화
clusters.length = 0;
}
for (let i = cave.length - 1; i >= 0; i--) {
answer += cave[i].join('') + '\n';
}
console.log(answer.trimEnd());
function throwStick(L, arr) {
// 막대기에 맞은 미네랄은 '.'으로 바뀜
if (L) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === 'x') {
arr[i] = '.';
return;
}
}
} else {
for (let i = arr.length - 1; i >= 0; i--) {
if (arr[i] === 'x') {
arr[i] = '.';
return;
}
}
}
}
function bfs(y, x) {
const queue = [[y, x]];
let front = 0;
while (queue.length > front) {
const [y, x] = queue[front++];
for (let i = 0; i < 4; i++) {
const nx = x + dx[i];
const ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < C && ny < R && !visited[ny][nx] && cave[ny][nx] === 'x') {
visited[ny][nx] = true;
queue.push([ny, nx]);
}
}
}
return queue;
}
function fallDown(cluster) {
while (true) {
let cantFalldown = false;
const partOfCluster = [];
for (const [y, x] of cluster) {
// 땅과 이어져있다면 해당 클러스터는 바닥으로 안떨어짐
if (y === 0) return;
// 다음 칸이 미네랄이거나, 바닥보다 아래라면 다음 차례에서 아래로 내려가지 못함
if (cave[y - 1][x] === 'x' || y - 1 === -1) {
cantFalldown = true;
break;
}
// 한 칸은 무조건 떨어짐
cave[y][x] = '.';
cave[y - 1][x] = 'x';
partOfCluster.push([y, x]);
}
// 다음 차례에 낙하가 불가능한 경우
if (cantFalldown) {
// 부분적으로 떨어졌던 미네랄들 다시 되돌리기
while (partOfCluster.length) {
const [y, x] = partOfCluster.pop();
cave[y - 1][x] = '.';
cave[y][x] = 'x';
}
break;
} else {
// 낙하한 지점 클러스터에 반영
cluster.forEach(([y, x], i) => (cluster[i] = [y - 1, x]));
}
}
}
}
유용했던 반례
input
7 5
.....
.xxx.
.x...
xx.xx
x...x
x...x
x...x
1
4
answer
.....
.....
.xxx.
.x.xx
xx..x
x...x
x...x
지속적인 성장