백준 16918번

QEUSTION LINK

1. 첫 풀이 방식 : 규칙 사용하기 (실패)

문제에서 일종의 규칙을 찾은 뒤, 이후 문제가 되는 부분에 대해서만 처리를 해주고자 했습니다. 가장 처음에 한 것은 상황을 구분 짓는 것이었는데, 해당 문제의 경우 총 세 가지 경우의 수가 반복되고 있었습니다.

1. 처음에 주어진 폭탄의 상황
2. 모든 위치에 폭탄이 들어간 상황
3. 처음 위치와 반대로 폭탄이 설치된 상황

이 상황들 중 3번에 대한 처리만 하면 될 것이라는 생각으로, 처음에 주어진 폭탄의 상황을 먼저 만드는 것으로 시작했습니다. 이를 위해 주어진 값들에 대해서 그래프 형식으로 바꾸는 작업부터 해주었습니다.

const [R, C, time] = input[0].split(" ");
// R x C 의 그래프에서 time을 가져옴
const graph = input.splice(1).map((line) => line.split(""));
// 그래프 각각의 값을 나누어줌
const visited = {};
// 방문한 곳을 처리하기 위한 객체

위 코드를 통해 아래와 같은 형식의 그래프를 가져올 수 있었습니다.

const graph = [
  [".", ".", ".", ".", ".", ".", "."],
  [".", ".", ".", "O", ".", ".", "."],
  [".", ".", ".", ".", "O", ".", "."],
  [".", ".", ".", ".", ".", ".", "."],
  ["O", "O", ".", ".", ".", ".", "."],
  ["O", "O", ".", ".", ".", ".", "."],
];

그 후, 각 초마다의 상황을 처리해야했는데, 이는 아래와 같은 규칙성을 가지고 있었습니다.

0초 : 처음 주어진 상황
1초 : 처음 주어진 상황
2초 : 모든 위치에 폭탄
3초 : 처음과 뒤바뀐 상황
4초 : 모든 위치에 폭탄
5초 : 처음 주어진 상황
6초 : 모든 위치에 폭탄
...

즉, 시간이 주어진 상황에서, 4로 나눌 때, 아래와 같은 결과가 됩니다.

나머지 1 = 첫 상황
나머지 2, 나머지 4 = 모든 위치에 폭탄
나머지 3 = 첫 상황과 반대

이렇게 상황을 설정한 뒤에는 ‘첫 상황과 반대’인 경우에 대해 처리를 해주어야 했습니다. 이 부분에 대한 처리는 그래프를 순회하며 폭탄(”0”)을 만날 때마다 그 주위의 값들을 터짐(”.”)으로 바꿔주도록 설정했습니다. 그리고 만약, 그 주위에 다른 폭탄이 있는 경우에는 이후에 그 폭탄이 터지는 것으로 처리했습니다.

const getResult = () => {
  const remain = time % 4;
  if (remain === 1) {
    // 처음과 같은 상태 유지
    return graph.map((line) => line.join("")).join("\n");
  }
  if (remain === 0 || remain === 2) {
    // 모두 폭탄이 위치한 것으로 설정
    return graph.map(() => "O".repeat(C)).join("\n");
  }
  if (remain === 3) {
    // 처음 폭탄과 반대 상황 설정
    graph.forEach((line, lineIndex) => {
      line.forEach((box, boxIndex) => {
        if (box === "O") {
          checkMark(lineIndex, boxIndex, true);
          // 처음 위치에 폭탄이 터지고, 이후 주변 폭탄도 터지도록 설정
          if (lineIndex - 1 >= 0) checkMark(lineIndex - 1, boxIndex);
          if (boxIndex - 1 >= 0) checkMark(lineIndex, boxIndex - 1);
          if (boxIndex + 1 <= C - 1) checkMark(lineIndex, boxIndex + 1);
          if (lineIndex + 1 <= R - 1) checkMark(lineIndex + 1, boxIndex);
        }
        if (box === ".") {
          // 폭탄이 아닌 곳을 지날 시, 폭탄으로 바뀌도록 설정
          const mark = `${lineIndex},${boxIndex}`;
          if (!visited[mark]) {
            visited[mark] = true;
            graph[lineIndex][boxIndex] = "O";
          }
        }
      });
    });

    return graph.map((line) => line.join("")).join("\n");
  }
};

그리고, 폭탄에 도착할 시, 폭탄이 터지는 상황에 대한 함수는 따로 구분해서 생성해주었습니다. 이 때, 폭탄이 터지는 상황은 현재 위치가 폭탄일 때, 주변 위치가 폭탄이 아닐 때로 설정했습니다.

const checkMark = (lineIndex, boxIndex, isSelf = false) => {
  const mark = `${lineIndex},${boxIndex}`;
  // 폭탄이 터질 위치
  if (graph[lineIndex][boxIndex] === "O" && !visited[mark] && !isSelf) return;
  // 폭탄 자체의 위치가 아닌 상황에서 방문한 적 없는 주변 폭탄인 경우에는 넘어감
  visited[mark] = true;
  graph[lineIndex][boxIndex] = ".";
};

이를 통해 예제의 상황에 대해서는 제대로 결과가 호출되는 것을 볼 수 있었습니다. 하지만, 백준을 통해 채점을 했을 때 틀렸다는 결과가 나와서 문제점을 파악하는 데에 시간을 꽤 소요됐습니다.

2. 두 번째 방식 : 직접 반복하기 (성공)

이전에 규칙을 찾아 적용하는 방식을 할 경우, 규칙이 무조건 반복되지 않을 수도 있다는 문제가 있다는 것을 발견했습니다. 그래서, 이를 해결하기 위해서는 직접 폭탄이 터지는 상황을 반복하는 것이 안전하다고 판단해, 직접 진행하는 것으로 방법을 변경했습니다.

문제를 풀기 위해 진행한 순서는 아래와 같습니다.

1. 1초만 진행된 상황에 대해 처리하기
2. 짝수초 만큼 진행된 상황에 대해 처리하기
3. 1,2번 이외의 상황 처리하기

가장 먼저 진행한 것은 첫 번째 방식과 동일하게 그래프를 만들어주는 것이었습니다.

const [R, C, N] = input[0].split(" ");
const time = Number(N);
const graph = input.slice(1).map((line) => line.split(""));

[
  [".", ".", ".", ".", ".", ".", "."],
  [".", ".", ".", "O", ".", ".", "."],
  [".", ".", ".", ".", "O", ".", "."],
  [".", ".", ".", ".", ".", ".", "."],
  ["O", "O", ".", ".", ".", ".", "."],
  ["O", "O", ".", ".", ".", ".", "."],
];
// 생성된 그래프 배열

그리고 폭탄이 터지는 상황에서 사용하기 위한 폭탄으로만 가득찬 배열을 만드는 함수를 생성했습니다. 이 함수의 경우, 앞서 말한 바와 같이 짝수초 만큼 지나간 상황에서는 폭탄으로만 가득한 배열이 나오기 때문에 그 상황에서도 활용이 가능합니다.

const getNewGraph = () =>
  [...Array(Number(R))].map(() => [...Array(Number(C))].map(() => "O"));

그리고 1, 2번의 상황을 처리하기 위한 함수를 먼저 생성했습니다.

const getResult = () => {
  // 1초만 지나간 경우 원래의 그래프를 보여줌
  if (time === 1) {
    return input.slice(1).join("\n");
  }
  // 짝수초만큼 지나간 경우 폭탄으로 가득한 그래프를 보여줌
  if (!(time % 2)) {
    return getNewGraph()
      .map((line) => line.join(""))
      .join("\n");
  }

  ...
};

이후 폭탄이 터진 뒤의 상황을 보여주는 그래프를 생성해야 했습니다. 이를 해결하기 위해 생각한 것은 우선 폭탄으로 가득찬 그래프를 먼저 만든 뒤, 이전 그래프에서 폭탄이 위치한 곳과 상하좌우를 폭탄이 터지도록 하여 다음에 터져야할 폭탄들이 보이는 그래프가 나오도록 설정을 해주었습니다.

그리고 2초가 더 지나간 상황에서는 새롭게 만들어진 그래프에서 폭탄이 터지는 상황을 만들도록 하여 앞서 진행한 것과 같은 방식으로 진행하도록 했습니다.

const getResult = () => {
  ...

  let curTime = Number(time) - 2;
  // 시간이 이미 2초 지나간 뒤의 상황부터 시작하기 때문에 2를 뺌
  let curGraph = graph;
  // 폭탄의 위치를 나타내는 그래프
  while (curTime > 0) {
  // 2초씩 지나간 뒤, 0초 이하일 경우 멈춤
    curTime -= 2;
    // 2초가 지나간 뒤의 상황을 보여줄 것이므로 뺌
    const newGraph = getNewGraph();
    // 새롭게 만들어질 폭탄으로 가득찬 그래프
    curGraph.forEach((line, lineIndex) => {
      line.forEach((box, boxIndex) => {
      // 폭탄 위치를 나타내는 그래프에서 좌표를 빼내어 폭탄과 그 상하좌우가 터지도록 설정
        if (box !== "O") return;
        newGraph[lineIndex][boxIndex] = ".";
        if (lineIndex - 1 >= 0) newGraph[lineIndex - 1][boxIndex] = ".";
        if (boxIndex - 1 >= 0) newGraph[lineIndex][boxIndex - 1] = ".";
        if (boxIndex + 1 <= C - 1) newGraph[lineIndex][boxIndex + 1] = ".";
        if (lineIndex + 1 <= R - 1) newGraph[lineIndex + 1][boxIndex] = ".";
      });
    });
    curGraph = newGraph;
    // 새롭게 만들어진 폭탄 위치 그래프로 설정
  }
  return curGraph.map((line) => line.join("")).join("\n");
};

이런 식으로 폭탄이 터지는 위치에 대한 값을 지속적으로 확인해 처리해주는 방식으로 문제를 해결할 수 있었습니다.

---

🔎 현재 사용한 방식은 그래프 순회를 하는 방식을 적극적으로 사용하지는 않은 것이라 다른 방법에 대한 고민이 더 필요하기는 합니다!

GITHUB  EMAIL