작은 단위부터 구현하기, 데이터는 리턴하기

이 문제, 나를 울게 만들었다. 분하다. 정말 다시는 잊고 싶지 않은 문제였기에 포스팅을 합니다. 자바스크립트로 풀이하면서 자바스크립트 자체에 대해 좀 더 알게 되는 문제이기도 한 의미있는 문제입니다.

1. 문제: 감시

문제풀이를 보기 전에 문제를 잘 읽고 오면 좋습니다!

2. 문제풀이 접근법

옳은 발상

• (1) 감시카메라의 위치를 탐색해서 좌표와 감시카메라 번호를 배열에 담아놓는다.
• (2) 각 감시카메라가 볼 수 있는 각도를 카메라별로 모두 탐색한다.
  - 가령
  다음과 같이 2,2,5 이렇게 3개의 시시티비가 존재하는 경우, 총 4가지의 각도 조합이 가능할 것이다. 모든 각도 조합의 경우를 탐색한다는 뜻이다. => 완전탐색
• (3) 나는 재귀를 통한 DFS방식을 통해 CCTV가 볼 수 있는 영역을 '#'표시하면서 탐색을 진행하기로 결정했다.
  - 가령, '첫 번째 2번 카메라는 (좌,우) (상,하) 이렇게 두 가지 방향을 볼 수 있으니, (좌,우)를 보는 경우를 고정해두고 '#'을 체크한 뒤, 다음 카메라로 넘어가서 또 그 카메라가 보는 곳을 표시해주고...'의 식으로 진행하는 것이다.
• (4) 재귀의 반환조건 안에 완성된 그래프를 순회하며 사각지대인 0 의 개수를 센다.
  - 이 때, 사각지대인 0의 개수가 기존의 개수보다 더 작다면 갱신해준다.
• (5) 재귀함수가 한 번 끝났다면 graph는 현재 무수한 '#'들로 가득차 있는 상태일 것이다. 다음 탐색을 위해서 이전 재귀함수가 호출되기 전 상태의 그래프로 돌려놓는다. => 백트랙킹

1차 구현 (삽질의 연속 - 틀린 구현이었습니다)

const [[N, M], ...graph] = require('fs')
  .readFileSync('/dev/stdin')
  .toString()
  .trim()
  .split('\n')
  .map((s) => s.split(' ').map(Number))

const cameraMap = {
  1: [[[0, 1]], [[1, 0]], [[-1, 0]], [[0, -1]]],
  2: [
    [
      [0, 1],
      [0, -1],
    ],
    [
      [1, 0],
      [-1, 0],
    ],
  ],
  3: [
    [
      [-1, 0],
      [0, 1],
    ],
    [
      [0, 1],
      [1, 0],
    ],
    [
      [1, 0],
      [0, -1],
    ],
    [
      [0, -1],
      [-1, 0],
    ],
  ],
  4: [
    [
      [0, -1],
      [-1, 0],
      [0, 1],
    ],
    [
      [1, 0],
      [-1, 0],
      [0, 1],
    ],
    [
      [1, 0],
      [0, -1],
      [0, 1],
    ],
    [
      [0, -1],
      [1, 0],
      [-1, 0],
    ],
  ],
  5: [
    [
      [0, -1],
      [1, 0],
      [-1, 0],
      [0, 1],
    ],
  ],
}

const setCamera = (row, col) => {
  const cNumber = graph[row][col]
  let counter = 0
  let remember = []
  for (const deltas of cameraMap[cNumber]) {
    let tempCounter = 0
    for (const [dRow, dCol] of deltas) {
      let nextRow = row + dRow
      let nextCol = col + dCol
      while (nextRow < N && nextRow >= 0 && nextCol < M && nextCol >= 0) {
        if (graph[nextRow][nextCol] === 6) break
        if (graph[nextRow][nextCol] === 0) tempCounter++
        nextRow += dRow
        nextCol += dCol
      }
    }
    if (counter <= tempCounter) {
      remember = deltas
      counter = tempCounter
    }
  }
  for (const [dRow, dCol] of remember) {
    let nextRow = row + dRow
    let nextCol = col + dCol
    while (nextRow < N && nextRow >= 0 && nextCol < M && nextCol >= 0) {
      if (graph[nextRow][nextCol] === 6) break
      if (graph[nextRow][nextCol] === 0) graph[nextRow][nextCol] = -1
      nextRow += dRow
      nextCol += dCol
    }
  }
}

for (let row = 0; row < N; row++) {
  for (let col = 0; col < M; col++) {
    if (graph[row][col] === -1 || graph[row][col] === 6 || graph[row][col] === 0) continue
    setCamera(row, col)
  }
}

let answer = 0
for (let i = 0; i < N; i++) {
  for (let j = 0; j < M; j++) {
    answer += graph[i][j] === 0 ? 1 : 0
  }
}
console.log(answer)

구현에서 첫째로 문제가 되었던 부분은 카메라마다 볼 수 있는 각도가 다른데 이것을 어떻게 처리해야하는가?였습니다.

문제에서 카메라는 다음과 같이 총 5가지 종류이고, 각 카메라가 한 번에 볼 수 있는 각도는 그림과 같습니다. 그래프 상에서 보자면, 이것은 상하좌우 움직임들 중 하나씩에 대응합니다. 상하좌우 움직임이라는 것은 그래프에서는 행의 변화값과 열의 변화값으로 표현할 수 있습니다. [dRow,dCol] 을 [행의 움직임, 열의 움직임] 이라 한다면, 상 하 좌 우 는 각각 [-1,0][1,0] [0,-1][0,1] 로 표현할 수 있을 것입니다.

저는 이것을 cameraMap이라는 객체 속에 카메라별로 볼 수 있는 각도의 경우의 수를 다 담아서, 카메라 번호별로 이 배열을 순회하며 보는 방향에 따라 '#'을 찍도록 코드를 짰습니다.

하지만 문제가 있었습니다. 제 로직 자체가 틀렸던 것이지요. 제가 구현한 코드는 완전탐색같지만 완전탐색이 아닙니다. 오히려 그리디 로직에 가깝죠.

함수 setCamera의 동작은 각 카메라가 볼 수 있는 모든 각도를 살펴보고 가장 많은 부분을 감시할 수 있는 각도를 선택하는 로직이 담겨 있습니다. counter변수와 tempCounter를 비교하면서 말이죠. 얼핏 보면 괜찮아 보이기도 합니다.

하지만 제 풀이는 틀렸습니다를 뱉어내었고, 생각해보니 제 풀이는 카메라의 탐색 순서에 따른 반례가 존재했습니다.

다음과 같은 경우를 생각해봅시다.

먼저 1번 카메라는 오른쪽이든 아래쪽이든 똑같이 2영역을 감시할 수 있습니다. 제 코드상에서는 오른쪽을 먼저 보기로 되어 있으니, 한 번 1번카메라가 오른쪽을 보는 것으로 설정을 해 보죠.

그렇다면 그래프는 이렇게 될 것입니다.

이제 다음 (2,2)에 존재하는 2번 카메라를 살펴보죠. 2번 카메라는 왼쪽을 보면 2 영역을 감시할 수 있으니, 왼쪽을 선택할 것입니다.

이런 논리로 마지막 2번 카메라는 위쪽을 바라봐야겠네요.

그 결과 그래프는 이렇게 형성됩니다. 4칸의 사각지대가 존재하네요.

하지만 사실 1번 카메라가 오른쪽이 아닌 아래쪽을 먼저 보았다면 다음과 같이 3칸의 사각지대만 존재하도록 만들 수 있습니다.

그래서 완전탐색로직으로 선회하게 됩니다.

2차 구현 (맞았습니다!)

let [[N, M], ...graph] = require('fs')
  .readFileSync('/dev/stdin')
  .toString()
  .trim()
  .split('\n')
  .map((s) => s.split(' ').map(Number))

let answer = 0

const solution = (N, M, graph) => {
  const cameras = []
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
      if (graph[i][j] === 0) answer++
      if (graph[i][j] !== 0 && graph[i][j] !== 6) cameras.push([i, j, graph[i][j]])
    }
  }
  recursion(0, cameras, graph)
}

const recursion = (depth, cameras, graph) => {
  if (depth === cameras.length) {
    //recursion ends
    let tempAnswer = 0
    graph.forEach((row, i) => {
      row.forEach((_, j) => {
        tempAnswer += graph[i][j] === 0 ? 1 : 0
      })
    })
    answer = Math.min(answer, tempAnswer)
    return
  }
  const [cRow, cCol, cameraNum] = cameras[depth]
  const originalGraph = deepCopyGraph(graph)
  switch (cameraNum) {
    case 1:
      //4군데를 recursion
      fillGraph(cRow, cCol, graph, 1)
      recursion(depth + 1, cameras, graph)
      graph = deepCopyGraph(originalGraph)
      fillGraph(cRow, cCol, graph, 2)
      recursion(depth + 1, cameras, graph)
      graph = deepCopyGraph(originalGraph)
      fillGraph(cRow, cCol, graph, 3)
      recursion(depth + 1, cameras, graph)
      graph = deepCopyGraph(originalGraph)
      fillGraph(cRow, cCol, graph, 4)
      recursion(depth + 1, cameras, graph)
      graph = deepCopyGraph(originalGraph)
      break
    case 2:
      //2각도 recursion
      fillGraph(cRow, cCol, graph, 1, 3)
      recursion(depth + 1, cameras, graph)
      graph = deepCopyGraph(originalGraph)
      fillGraph(cRow, cCol, graph, 2, 4)
      recursion(depth + 1, cameras, graph)
      graph = deepCopyGraph(originalGraph)
      break
    case 3:
      //4각도 recursion
      fillGraph(cRow, cCol, graph, 1, 2)
      recursion(depth + 1, cameras, graph)
      graph = deepCopyGraph(originalGraph)
      fillGraph(cRow, cCol, graph, 2, 3)
      recursion(depth + 1, cameras, graph)
      graph = deepCopyGraph(originalGraph)
      fillGraph(cRow, cCol, graph, 3, 4)
      recursion(depth + 1, cameras, graph)
      graph = deepCopyGraph(originalGraph)
      fillGraph(cRow, cCol, graph, 4, 1)
      recursion(depth + 1, cameras, graph)
      graph = deepCopyGraph(originalGraph)
      break
    case 4:
      //4각도 recurse
      fillGraph(cRow, cCol, graph, 1, 2, 3)
      recursion(depth + 1, cameras, graph)
      graph = deepCopyGraph(originalGraph)
      fillGraph(cRow, cCol, graph, 2, 3, 4)
      recursion(depth + 1, cameras, graph)
      graph = deepCopyGraph(originalGraph)
      fillGraph(cRow, cCol, graph, 3, 4, 1)
      recursion(depth + 1, cameras, graph)
      graph = deepCopyGraph(originalGraph)
      fillGraph(cRow, cCol, graph, 4, 1, 2)
      recursion(depth + 1, cameras, graph)
      graph = deepCopyGraph(originalGraph)
      break
    default:
      //5인 경우
      fillGraph(cRow, cCol, graph, 1, 2, 3, 4)
      recursion(depth + 1, cameras, graph)
      graph = deepCopyGraph(originalGraph)
  }
}

const fillGraph = (cRow, cCol, graph, ...directions) => {
  const angles = { 1: [-1, 0], 2: [0, 1], 3: [1, 0], 4: [0, -1] }
  for (const direction of directions) {
    let row = cRow
    let col = cCol
    const [dx, dy] = angles[direction]
    let isStop = false
    while (!isStop) {
      let nextRow = row + dx
      let nextCol = col + dy
      if (nextRow >= 0 && nextRow < N && nextCol >= 0 && nextCol < M) {
        if (graph[nextRow][nextCol] === 6) {
          isStop = true
          break
        }
        if (graph[nextRow][nextCol] === 0) {
          graph[nextRow][nextCol] = '#'
        }
        row = nextRow
        col = nextCol
        continue
      }
      isStop = true
    }
  }
}

const deepCopyGraph = (graph) => {
  const newGraph = []
  graph.forEach((row) => {
    newGraph.push([...row])
  })
  return newGraph
}

solution(N, M, graph)
console.log(answer)

2차 구현에서는 위에 언급했던 발상의 순서대로 차근차근 구현을 해보기로 결심했습니다. 개인적으로 재귀에 참 약하다고 느꼈기 때문에, 다른 사람의 풀이를 보지 않고, 혼자서 끙끙대더라도 나만의 로직을 작성하도록 애를 써봤습니다.

카메라 위치 담기

먼저 카메라위치와 카메라 번호를 따로 cameras배열에 담았습니다. 이제 이 배열은 재귀함수에 전달되면서 재귀함수가 몇 번째 카메라를 바라보고 있는지를 알 수 있게 해줄겁니다.

재귀함수 짜기

이 코드를 이해하기 위해서는 재귀함수 recursion을 잘 이해해야 합니다.
저는 재귀함수를 짤 때, 먼저 언제 재귀가 종료되는지 를 작성합니다. 이 경우에는 마지막 카메라를 바라본 이후가 되겠네요. 그래서 현재 몇 번째 카메라를 바라보고 있었는지를 기록하는(cameras의 인덱스 역할을 하는) 파라미터 depth를 생각하게 됩니다. 그리고 현재 그래프 상태를 전달해야 하기 때문에 graph라는 인자도 생각하게 되었구요. 그래서 이 함수는 총 3개의 인자를 가지게 됩니다.

종료조건은 depth가 cameras의 범위를 넘어가게 되는 시점입니다. 이 때는 모든 카메라들이 각자의 각도를 가지고, 바라보고 있는 곳을 '#'표시를 했기 때문에, 사각지대를 계산하게 됩니다. 그리고 기존의 사각지대보다 값이 작다면, 좀 더 나은 결과를 낸 조합이기 때문에 값을 갱신해줍니다.

그렇지만 만약 살펴볼 카메라가 남아있는 경우라면, 해당 카메라를 선택하고, 볼 수 있는 각도를 하나씩 하나씩 살펴봐야겠죠. 이후에 나오는 switch 문이 해당 로직입니다.

1번 카메라의 경우, 2번 카메라의 경우 ,....5번 카메라의 경우까지 다 살펴보는 DFS형식의 로직입니다. 조금은 무식하게 짠 것 같네요.

카메라가 보고 있는 부분을 채우고, 하위 재귀함수 호출하기

각 카메라의 경우 보는 각도에 따라서 벽이 존재하거나 배열의 끝까지 '#'을 체크해줍니다.

여기서의 포인트는 fillGraph의 인자를 레스트 파라미터를 사용하여, 유동성있는 directions인자를 받도록 한 점, 그리고 상하좌우를 angles 객체에 따로 빼서 정의해 둔 점입니다.

하위 재귀함수가 끝났다면, 이전 상태로 그래프 되돌리기

switch문의 경우, 케이스가 3개 이상일 때 사용하는 편입니다. if else 문보다 가독성이 더 높아지거든요.

switch문 로직의 포인트는, 그리고 제가 스스로 잘했다고 생각하는 부분은 바로 '어떻게 이전 상태로 그래프를 되돌리냐'를 구현한 부분입니다.

자바스크립트에서 배열객체는 참조형이기 때문에, graph = originalGraph 처럼 코드를 짰다면, originalGraph의 값이 아닌, 주소값만 받아와 graph가 오염되었을 것입니다. 즉, 저는 깊은 복사가 필요했지만 얕은 복사만 하게 된 것이지요.

실제로 저는 이렇게 코드를 짰고 '틀렸습니다!'의 이유를 한참동안 찾았었습니다.

자바스크립트에서 2차원 배열을 깊게 복사하는 것은 참으로 귀찮고, 또 어려운 일이었습니다. JSON객체로 만들어서 다시 파스하는 방법이 있지만, 뭔가 마음에 들지 않았습니다.

그래서 생각한 것이 '데이터는 리턴한다'였습니다. deepCopy라는 함수를 구현하여 새로운 배열을 리턴하는 방식으로 코드를 작성하였고, 이제는 이후 수행에 영향을 받지 않고, 정말로 새로운 주소값을 지닌 2차원 배열의 주소값이 graph에 전달되었습니다.

3. 구현 시 어려웠던 점과 깨달음

• 자바스크립트에서 배열은 단순 할당 시, 참조형으로 전달됩니다(얕은 복사). 그래서 백트랙킹 시에, 원래의 그래프를 단순히 할당하게 되면, 원래 그래프의 주소값이 전달되어 원래 그래프가 오염이 됩니다.
• 이를 해결하려면 그래프를 완전히 새로운 주소값으로 재할당해주어야 합니다. 이를 위해 deepCopy함수를 구현하여 함수로 데이터를 리턴하였습니다.
• 변수의 스코프에 대해 충분히 생각을 하지 않고 코드를 짜지 않아, 어려움을 겪었습니다.

코드에 대한 질문과 개선점 제시는 얼마든지 환영입니다!
알고리즘 학습 레포: https://github.com/SeungrokYoon/Algorithm-Test-Practice