Advent of Code 2025 Day 4

벌써 별이 8개네요.
오늘부터는 출력되는 정답과 코드 실행시간까지 작성해볼게요.
코드 실행시간은 각자 cpu의 연산능력에 따라서 달라질거에요.
제 기준에서 오버됐을 경우 알고리즘을 개선하도록하겠습니다.

Part 1

--- 4일차: 인쇄부 ---
에스컬레이터를 타고 인쇄소로 내려갑니다. 그들은 분명히 크리스마스를 준비하고 있습니다. 곳곳에 큰 종이 롤이 많이 있고 구석에는 (정말 큰 인쇄 작업을 처리하기 위해) 거대한 프린터도 있습니다.

여기서 꾸미는 것은 쉽습니다: 직접 장식을 만들 수 있습니다. 엘리베이터가 오프라인 상태일 때 북극 기지로 더 깊이 들어갈 수 있는 방법이 정말 필요합니다.

"사실, 우리가 도와줄 수 있을지도 몰라요." 엘프 중 한 명이 도움을 요청하면 대답합니다. "우리는 뒷벽 반대편에 카페테리아가 있을 거라고 확신해요. 벽을 뚫을 수 있다면 계속 움직일 수 있을 거예요. 우리 지게차들이 큰 종이 롤을 옮기느라 너무 바빠서 안타깝네요."

지게차가 하고 있는 작업을 최적화할 수 있다면, 벽을 뚫을 시간이 있을지도 모릅니다.

종이 롤(@)은 큰 격자 위에 배열되어 있으며, 엘프들은 모든 것이 어디에 있는지를 나타내는 유용한 다이어그램(퍼즐 입력)도 있습니다.

예를 들어:

..@@.@@@@.
@@@.@.@.@@
@@@@@.@.@@
@.@@@@..@.
@@.@@@@.@@
.@@@@@@@.@
.@.@.@.@@@
@.@@@.@@@@
.@@@@@@@@.
@.@.@@@.@.
지게차는 인접한 8개의 위치에 종이 롤이 4개 미만인 경우에만 종이 롤에 접근할 수 있습니다. 지게차가 어떤 종이 롤에 접근할 수 있는지 알아낼 수 있다면 지게차는 찾는 데 더 많은 시간을 할애하고 카페테리아로 가는 벽을 허무는 데 더 많은 시간을 할애할 수 있습니다.

이 예시에서는 지게차(x 표시)로 접근할 수 있는 종이 롤이 13개 있습니다:

..xxx.xx@x.
x@@@@@@@
@@@@@.x.@
@.@@@@..@.
x@@@@@x
.@@@@@@@.@
.@.@.@.@@@
x.@@@@@@
.@@@@@@@@.
x.x.@@@.x.
종이 롤 위치에 대한 전체 다이어그램을 고려해 보세요. 지게차로 접근할 수 있는 종이 롤은 몇 개인가요?

정답

function main(input) {
  const map = input.split("\n").map((line) => line.trim().split(""));
  let answer = 0;

  const row = map.length;
  const col = map[0].length;

  const isInside = (x, y) => x >= 0 && x < col && y >= 0 && y < row;

  const directions = [
    [0, 1],
    [1, 0],
    [0, -1],
    [-1, 0],
    [1, 1],
    [1, -1],
    [-1, 1],
    [-1, -1],
  ];

  for (let i = 0; i < row; i++) {
    for (let j = 0; j < col; j++) {
      if (map[i][j] === "@") {
        let count = 0;
        for (const [dx, dy] of directions) {
          if (isInside(j + dx, i + dy) && map[i + dy][j + dx] === "@") {
            count += 1;
          }
        }

        if (count < 4) {
          answer += 1;
        }
      }
    }
  }

  console.log(answer);
}

const input = `..@@.@@@@.
@@@.@.@.@@
@@@@@.@.@@
@.@@@@..@.
@@.@@@@.@@
.@@@@@@@.@
.@.@.@.@@@
@.@@@.@@@@
.@@@@@@@@.
@.@.@@@.@.`;

main(input);

해설

가장자리의 경계 처리를 할 수 있는지를 묻는 문제.
순차적으로 위에서 오른쪽으로 반복하며 종리 롤이 있을 경우 인근 8개의 범위에 롤이 몇개 있나 체크하면 끝!
리트코드에서 정말 자주 풀던 문제 유형

Part 2

--- 파트 2 ---
이제 엘프들은 가능한 한 많은 논문에 접근하는 데 도움이 필요합니다.

지게차가 종이 롤에 접근할 수 있으면 제거할 수 있습니다. 종이 롤이 제거되면 지게차는 더 많은 종이 롤에 접근할 수 있으며, 포크레인도 이를 제거할 수 있습니다. 엘프가 이 과정을 계속 반복하면 총 몇 개의 종이 롤을 제거할 수 있을까요?

위와 같은 예제부터 시작하여 가능한 한 많은 종이 롤을 제거할 수 있는 한 가지 방법이 있습니다. 강조 표시된 @를 사용하여 종이 롤이 곧 제거될 것임을 나타내고, x를 사용하여 종이 롤이 방금 제거되었음을 나타낼 수 있습니다:

초기 상태:
..@@.@@@@.
@@@.@.@.@@
@@@@@.@.@@
@.@@@@..@.
@@.@@@@.@@
.@@@@@@@.@
.@.@.@.@@@
@.@@@.@@@@
.@@@@@@@@.
@.@.@@@.@.

종이 13롤을 제거합니다:
..xxx.xx@x.
x@@@@@@@
@@@@@.x.@
@.@@@@..@.
x@@@@@x
.@@@@@@@.@
.@.@.@.@@@
x.@@@@@@
.@@@@@@@@.
x.x.@@@.x.

종이 12롤을 제거합니다:
........x..
.@@x.x.x.@x
x@@@...@@
x.@@@..x.
.@@@@.x.
.x@@@@.x
.x.@@@@
..@@@.@@@@
.x@@@@@.
....@@@...

종이 7롤을 제거합니다:
..........
.x@....x.
.@@@...xx
..@@@@....
.x.@@@...
..@@@@@@..
...@@@@x
..@@@.@@@@
.x@@@@@.
....@@@...

종이 5롤을 제거합니다:
..........
....x.......
.x@@.......
..@@@@....
...@@@@...
..x@@@@..
...@.@.@@.
..x@@@@@x
...@@@@@@.
....@@@...

종이 두 롤을 제거합니다:
..........
..........
..x@@.......
..@@@@....
...@@@@...
...@@@@@..
...@.@.@@.
...@@.@@@.
...@@@@x.
....@@@...

종이 한 롤을 제거합니다:
..........
..........
...@@.....
....x@@....
...@@@@...
...@@@@@..
...@.@.@@.
...@@.@@@.
...@@@@@..
....@@@...

종이 한 롤을 제거합니다:
..........
..........
...x@.......
...@@@....
...@@@@...
...@@@@@..
...@.@.@@.
...@@.@@@.
...@@@@@..
....@@@...

종이 한 롤을 제거합니다:
..........
..........
....x.......
...@@@....
...@@@@...
...@@@@@..
...@.@.@@.
...@@.@@@.
...@@@@@..
....@@@...

종이 한 롤을 제거합니다:
..........
..........
..........
...x@@....
...@@@@...
...@@@@@..
...@.@.@@.
...@@.@@@.
...@@@@@..
....@@@...
지게차로 더 이상 종이 롤에 접근할 수 없게 되면 멈춰주세요. 이 예시에서는 총 43롤의 종이를 제거할 수 있습니다.

원본 다이어그램부터 시작하세요. 엘프와 지게차는 총 몇 롤의 종이를 제거할 수 있나요?

정답

function main(input) {
  const map = input.split("\n").map((line) => line.trim().split(""));
  let answer = 0;

  const row = map.length;
  const col = map[0].length;
  const isInside = (x, y) => x >= 0 && x < col && y >= 0 && y < row;

  const directions = [
    [0, 1],
    [1, 0],
    [0, -1],
    [-1, 0],
    [1, 1],
    [1, -1],
    [-1, 1],
    [-1, -1],
  ];

  while (true) {
    const res = rmRole();

    if (res === 0) break;

    answer += res;
  }

  console.log(answer);

  function rmRole() {
    let res = 0;

    for (let i = 0; i < row; i++) {
      for (let j = 0; j < col; j++) {
        if (map[i][j] === "@") {
          let count = 0;
          for (const [dx, dy] of directions) {
            if (isInside(j + dx, i + dy) && map[i + dy][j + dx] === "@") {
              count += 1;
            }
          }

          if (count < 4) {
            res += 1;

            map[i][j] = ".";
          }
        }
      }
    }

    return res;
  }
}

const input = `..@@.@@@@.
@@@.@.@.@@
@@@@@.@.@@
@.@@@@..@.
@@.@@@@.@@
.@@@@@@@.@
.@.@.@.@@@
@.@@@.@@@@
.@@@@@@@@.
@.@.@@@.@.`;

main(input);

해설

Part1의 코드를 재사용해 간단하게 문제를 해결했습니다.
Brute Force 방법말고 이번에는 BFS/DFS 방법으로도 풀 수 있겠네요. 실제 지게차가 이동하면서 Role을 지운다는 생각으로 코드를 작성하면 좋을 것 같아요.
다만 DFS의 경우에는 깊이가 너무 깊게들어가지않도록 최대 입력값을 항상 확인해 콜스택에러가 발생하지않도록 주의해야합니다.