[Swift] 백준 20208 - 진우의 민트초코우유

문제

https://www.acmicpc.net/problem/20208

20208번: 진우의 민트초코우유

https://www.acmicpc.net/problem/22944

22944번: 죽음의 비

처음엔 이문제랑 비슷하다 생각했는데 아니었다. 두 유형이 어떻게 다르고 접근 방법이 어떻게 다른지를 기록해보고자 한다.

 

틀린 코드 (처음 접근한 방식)

import Foundation

let input = readLine()!.split(separator:" ").map { Int(String($0))! }
let n = input[0], m = input[1], h = input[2]

var dx = [-1, 1, 0, 0]
var dy = [0, 0, -1, 1]

var nx = 0
var ny = 0

var board:[[Int]] = []
for _ in 0..<n {
  board.append(readLine()!.split(separator:" ").map { Int(String($0))! })
}

var house:(Int, Int) = (0, 0)

loop: for i in 0..<n {
  for j in 0..<n {
    if board[i][j] == 1 {
      house = (i, j)
      break loop
    }
  }
}

var q = [(house.0, house.1, m, 0)] // x/y 좌표, 초기체력, 민초 개수
var visited = Array(repeating: Array(repeating:0, count:n), count: n)
var answer = 0

func bfs(){
  visited[house.0][house.1] = m

  while !q.isEmpty {
    let (x, y, curM, curC) = q.removeFirst()

    for i in 0..<4 {
      nx = x + dx[i]
      ny = y + dy[i]

      guard 0..<n ~= nx && 0..<n ~= ny else { continue }

      var nxtM = curM
      var nxtC = curC

      if visited[nx][ny] == 0 {
        if board[nx][ny] == 0 {
          nxtM -= 1
        } else if board[nx][ny] == 2 {
          nxtC += 1
          nxtM += h - 1
        }
      }

      if board[nx][ny] == 1 {
        answer = max(answer, nxtC)
      }

      if nxtM == 0 { continue } //체력이 0이되는 순간 그 다음으로 이동할 수 없음
      visited[nx][ny] = nxtM
      q.append((nx, ny, nxtM, nxtC))
      
    }
  }
}

bfs()
print(answer)

- BFS를 기반으로 처음 출발점을 집으로 해서 순차적으로 보드에서 2를 마주치면 체력을 계산하고, 만약 체력이 0이 아니라면 각각 visited 배열에 체력을 기록해나가는 방식으로 구현했었다.

- 아얘 코드가 돌기만 하고 정답이 출력되지 않았는데, 이 코드는 체력이 0이 되지 않는 모든 정점을 방문하면서 최대값을 구하는 코드이므로 시간이 매우 많이 걸리는 것으로 보인다.

- 풀이를 찾아보니 차례대로 그래프 탐색을 하는게 아니라 민트초코 위치들의 좌표를 기준으로 집과의 거리를 계산하면서 "체력이 0이 되는 순간 이동할 수 없다" 라는 조건을 따질수 있느냐로 접근할 수 있었다. 즉 이 문제는 백트래킹으로 접근해야함 (중간에 체력이 0이되면 해당 경우의 수는 더이상 따지지 않으니까!)

 

시간 초과 코드

import Foundation

let nmh = readLine()!.split(separator: " ").map { Int($0)! }
let n = nmh[0], m = nmh[1], h = nmh[2] //마을 크기, 초기 체력, 증가하는 h양
var board:[[Int]] = []

for _ in 0..<n {
  board.append(readLine()!.split(separator: " ").map { Int($0)! })
}

var visited = Array(repeating: Array(repeating: false, count:n), count:n)

var milks = [(Int, Int)]()
var house = (0, 0)

for i in 0..<n {
  for j in 0..<n {
    if board[i][j] == 1 {
      house = (i, j)
    } else if board[i][j] == 2 {
      milks.append((i, j))
    }
  }
}

var answer = 0
//num: 초코우유 개수
func dfs(_ num: Int, _ x: Int, _ y: Int, _ hp: Int) {
  if hp - (abs(house.0-x) + abs(house.1-y)) >= 0 { //현재 체력으로 집으로 갈 수 있다면 맞는 경우의 수이므로 최대 갯수 계산
    answer = max(answer, num)
  }

  for (i, j) in milks {
    if visited[i][j] { continue }
    let diff = hp - (abs(x-i) + abs(y-j))
    if diff < 0 { continue } //체력이 0 이하로 떨어지면 우리가 찾는 경우의 수가 아니므로 백트랙

    visited[i][j] = true
    dfs(num+1, i, j, diff + h) //민트초코를 마시고 민트초코 갯수 + 1, 마셨으므로 계산한 체력 + h
    visited[i][j] = false
  }
}

dfs(0, house.0, house.1, m)
print(answer)

- 우유의 좌표들을 전수조사하면서, 현재 남은 체력과의 거리를 계산하여 (체력이 1만큼 줄어드므로, 그 다음 우유 후보와의 거리를 빼면 곧 남은 체력과 같아진다) 0 미만이면 우리가 찾는 경우의 수가 아니므로 더이상 탐색하지 않고, 체력이 남아있다면 그 다음 우유를 탐색한다.

- dfs를 재귀로 넘겨줄 때 민트초코우유 갯수, 현재 우유 좌표와 남은 체력을 넘겨주어 그때그때 집과의 거리가 0인지를 확인하며 최대값을 구해주도록 했다.

- 그러나 이 코드는 37%쯤에 시간초과로 오답이 나온 코드인데, 이유는 해당 코드의 시간복잡도가 O(n^n) 이라고 한다. 백트래킹을 돌 때 O(n!) 로 시간복잡도를 줄일 수 있는 알고리즘이 있다고 하여 찾아보았다. (정리한 포스팅은 여기!)

 

통과 코드

import Foundation

let nmh = readLine()!.split(separator: " ").map { Int($0)! }
let n = nmh[0], m = nmh[1], h = nmh[2] //마을 크기, 초기 체력, 증가하는 h양
var board:[[Int]] = []

for _ in 0..<n {
  board.append(readLine()!.split(separator: " ").map { Int($0)! })
}

var visited = Array(repeating: Array(repeating: false, count:n), count:n)

var milks = [(Int, Int)]()
var house = (0, 0)

for i in 0..<n {
  for j in 0..<n {
    if board[i][j] == 1 {
      house = (i, j)
    } else if board[i][j] == 2 {
      milks.append((i, j))
    }
  }
}

if milks.isEmpty {
  print(0)
  exit(0)
}

func permutation(_ left:Int, _ right: Int){
  if left == right {
    simulation()
    return
  }

  for i in left...right {
    milks.swapAt(i, left)
    permutation(left+1, right)
    milks.swapAt(i, left)
  }
}

var answer = 0
//num: 초코우유 개수
func simulation() {
  var hp = m
  var count = 0

  var nx = house.0
  var ny = house.1

  for (i, j) in milks {
    let dist = abs(nx-i) + abs(ny-j)
    if hp - dist < 0 { return } //체력에서 민트초코간의 거리(민트초코로 이동하기 까지의 소모 체력)을 뺐을 때 떨어지면 찾는 경우의 수가 아니므로 백트랙

    hp -= dist //잔여 체력
    hp += h //민트초코 먹었으므로 +h
    count += 1 //민트초코 개수 + 1

    if hp >= abs(house.0-i) + abs(house.1-j) { //현재 체력으로 집으로 갈 수 있다면
      answer = max(answer, count)
    }

    nx = i //그 다음 우유로 이동
    ny = j
  }
}

permutation(0, milks.count-1)
print(answer)

- 같이 스터디 하시는분의 풀이를 참고해서 다시 풀어보았다.

- 우유 좌표에서 순열을 구하는 알고리즘을 수정했고, 그 순열에 들어있는 우유마다 돌면서 남은 체력을 계산해나간다. (남은 체력 구하는 로직은 위와 동일함)

- 여기서 백트래킹 하는 코드는 if hp - dist < 0 { return } 이부분이다. 문제에서 "체력이 0이 되는 순간 진우는 이동할 수 없다. 체력이 0이 되어 집으로 못 돌아가는 상황은 만들어져서는 안되며, 얼마나 많은 민트초코우유를 마시고 집에 돌아오는가?" 라고 되어있으므로, 체력이 0이 되는 경우의 수는 우리가 찾는 경우의 수가 아니므로 그대로 return 해준다.

- 우유를 먹을때마다, 잔여 체력을 계산해서 만약에 체력이 집으로 돌아갈 수 있을만한 체력이 남아있다면 그때 민트초코 우유 갯수의 최대값을 갱신해준다.

 

🚨 죽음의 비 문제 (백준 22944) 와의 차이점

유사하게 "체력, 내구도" 라는 키워드가 있어서 비슷할줄 알았는데 아니었다.

 

순서대로 탐색하는가 VS 아닌가

 

백트래킹을 문제에서 어떤 키워드를 뽑고 백트래킹이라고 알 수 있을지 다시 정리해보는 계기가 되어 좋은 문제였다.

어려웠다.... 잊을만하면 다시 풀어봐야지