[boj] 21608. 상어 초등학교 (node.js)

문제 요약

[boj] 21608. 상어 초등학교 (node.js)

• 조건을 만족하도록 알고리즘을 구현하고 결과를 하나의 값으로 출력하는 문제

풀이

• 아래 코드는 길지만, 요구조건을 - solution() 함수 내에 쪼개 두었기 때문에 함수를 접어보면 상당히 간단하다.
• 먼저 입력을 받아두고, 해당 입력을 재사용해야 하므로 저장해 둔다.
• cond() 함수를 통해서 모든 조건을 만족하는 자리를 구하고, 해당 자리에 사람을 앉힌다.
• cond() 함수 내부에서 문제에서 제시한 3개의 조건을 확인한다. 조건들은 답이 하나가 아닌 경우 다음 조건을 수행하므로, 중간에 답을 찾으면 바로 반환하여 불필요한 탐색을 줄인다.
• getScore() 함수로 점수를 계산한다.
• 끝!

내 풀이

const readline = require("readline")
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
})

const dir = [
  [-1, 0],
  [0, 1],
  [1, 0],
  [0, -1],
]

const solution = () => {
  const N = Number(input())
  let student = []
  let seat = []
  let inputArr = []
  for (let i = 0; i < N; i++) seat[i] = []
  for (let i = 0; i < N ** 2; i++) {
    let temp = input().split(" ").map(Number)
    inputArr[i] = temp[0]
    student[temp[0]] = [temp[1], temp[2], temp[3], temp[4]]
  }
  inputArr.forEach(num => {
    let [r, c] = cond(num)
    seat[r][c] = num
  })
  let result = getScore()
  console.log(result)

  function cond(num) {
    let result = adjacentChecker(num)
    if (result.length == 1) return result[0]
    result = emptyChecker(result)
    if (result.length == 1) return result[0]
    result = indexChecker(result)
    return result
  }

  function adjacentChecker(num) {
    let result = []
    let max = 0
    for (let i = 0; i < N; i++) {
      for (let j = 0; j < N; j++) {
        if (seat[i][j] > 0) continue
        let cnt = 0
        for (let k = 0; k < dir.length; k++) {
          let nr = i + dir[k][0]
          let nc = j + dir[k][1]
          if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue
          if (!seat[nr][nc]) continue
          if (student[num].includes(seat[nr][nc])) cnt++
        }
        // 해당 위치에 대한 인접 계산이 완료되었으므로
        if (cnt < max) continue
        if (cnt > max) result = [] // 아예 갱신되었으므로 비우기
        result.push([i, j]) // 후보에 더하기
        max = cnt
      }
    }
    // 후보가 될 수 있는 칸들의 배열 반환 [[i, j], [i, j], ...]
    return result
  }

  function emptyChecker(arr) {
    let result = []
    let max = 0
    if (arr.length == 0) {
      for (let i = 0; i < N; i++) {
        for (let j = 0; j < N; j++) {
          if (seat[i][j] > 0) continue
          arr.push([i, j])
        }
      }
    }
    for ([r, c] of arr) {
      let cnt = 0
      for (let i = 0; i < dir.length; i++) {
        let nr = r + dir[i][0]
        let nc = c + dir[i][1]
        if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue
        if (seat[nr][nc] > 0) continue
        cnt++
      }
      if (cnt < max) continue
      if (cnt > max) result = []
      result.push([r, c])
      max = cnt
    }
    return result
  }

  function indexChecker(arr) {
    arr.sort(([ar, ac], [br, bc]) => ac - bc)
    arr.sort(([ar, ac], [br, bc]) => ar - br)
    return arr[0]
  }

  function getScore() {
    let score = 0
    for (let i = 0; i < N; i++) {
      for (let j = 0; j < N; j++) {
        let cnt = 0
        for (let k = 0; k < dir.length; k++) {
          let nr = i + dir[k][0]
          let nc = j + dir[k][1]
          if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue
          if (student[seat[i][j]].includes(seat[nr][nc])) cnt++
        }
        if (cnt == 0) score += 0
        else if (cnt == 1) score += 1
        else if (cnt == 2) score += 10
        else if (cnt == 3) score += 100
        else if (cnt == 4) score += 1000
      }
    }
    return score
  }
}

let line = 0
const input = () => stdin[line++]
let stdin = []
rl.on("line", function (line) {
  stdin.push(line)
}).on("close", function () {
  solution()
  process.exit()
})

주절주절

• 처음으로 풀어보는 구현 문제! 백준 문제집 중 맨 첫 번째, 그 중에서도 solved.ac 랭크가 실버인 걸 보고 전에 도전했었는데, 조금 읽어보다 문제의 까다로운 요구사항에 바로 다른 문제를 풀러 떠났던 기억이 있다.
• 당시에는 '구현' 을 요구하는 알고리즘 문제가 존재한다는 걸 몰랐다. 때문에 어떤 알고리즘을 적용하는 게 키포인트일지 고심하다가 답이 없는 것 같아서 이게 정말 일일이 구현하는 게 맞나? 라고 생각했던 기억이 있다. 지금 생각해보면, 특히 이 문제같은 경우 시간복잡도 조건이 까다롭지 않기 때문에 말 그대로 요구사항을 모두 만족할 수 있도록 코드를 짜면 된다.
• 오늘도 깨달은 알고리즘의 필승법은 처음부터 끝까지 풀이의 대략적인 흐름을 떠올리고 - 해당 풀이의 시간, 공간 복잡도를 파악하고 - 문제가 없다면 구체적으로 생각한 후 코드를 짜는 것이다. 그러니까, 차근차근 하면 된다!