[백준/Kotlin] 우주 탐사선(17182)

🔗 문제 링크

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

백준 - 백트래킹 | 우주 탐사선(17182)

우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 발사되는 행성의 위치와 ana호가 행성 간 이동을 하는데 걸리는 시간이 2차원 행렬로 주어진다. 행성의 위치는 0부터 시작하여 0은 행렬에서 0번째 인덱스에 해당하는 행성을 의미한다. 2차원 행렬에서 i, j 번 요소는 i 번째 행성에서 j 번째 행성에 도달하는데 걸리는 시간을 나타낸다. i와 j가 같을 때는 항상 0이 주어진다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하여라.

탐사 후 다시 시작 행성으로 돌아올 필요는 없으며 이미 방문한 행성도 중복해서 갈 수 있다.

---

✔️ 소요된 시간

3시간

---

✨ 수도 코드

정답 비율이 50%가 넘길래 호기롭게 도전했다가 결국 솔루션을 찾아봤습니다 🥲

1️⃣차 시도 방법 (메모리 초과)

현재 행성에서 자기자신을 제외한 다른 행성으로 가는 경우의 수를 다 체크하면서 반복하다가 모든 행성을 다 탐색했을 때 소요된 시간을 비교하면서 최소 시간을 찾아갔습니다!

모든 행성을 다 탐색해야 하지만, 같은 행성을 여러번 탐색해도 된다는 조건이 있어서 지금까지 탐색한 행성의 수와 각 행성의 방문 유무를 함께 체크해줬습니다

data class Path(
  val position: Int, // 현재 있는 행성 위치
  val time: Int, // 지금까지 이동에 소요된 시간
  val visitedCnt: Int, // 지금까지 방문한 행성의 수
  val visited: Array<Boolean>, // 행성들 방문 체크
)

 

이렇게 data class를 정의해두고, 행성 하나를 탐색할 때마다 queue에 넣어서 bfs로 탐색해줬습니다

대신 이렇게 실행하다보면 너무 많은 연산이 반복될 수 있기 때문에 이미 현재 구해둔 최소 소요시간보다 더 많은 시간을 썼다면 해당 경우의 수를 중간에 걸러주는 작업을 넣었습니다

var planetPath = LinkedList<Path>() as Queue<Path>
var visited = Array(N, {false})
visited[K] = true
planetPath.offer(Path(K, 0, 1, visited))

var answer = 1000 * 10

while(!planetPath.isEmpty()) {
  val current = planetPath.poll()

  // 모든 행성을 탐색했다면
  if(current.visitedCnt == N) {
    answer = min(answer, current.time)
    continue
  }
  
  for(i: Int in 0..N-1) {
    // 현재 위치랑 같거나 이미 현재의 최소 시간을 넘어섰다면 
    if(current.position == i || current.time >= answer) continue

    var newVisitedCnt = current.visitedCnt
    if(!current.visited[i]) newVisitedCnt++

    val newVisited = current.visited.clone()
    newVisited[i] = true

    planetPath.offer(
      Path(
        position = i,
        time = current.time + planet[current.position][i],
        newVisitedCnt,
        visited = newVisited
      )
    )
  }
}

 경로를 탐색할 때마다 visited 배열이 추가로 생성되는데, 계산되는 경로가 많아지거나 행성의 수가 많아질수록 메모리를 많이 사용하게 된다는 문제가 있어서 결국 메모리 초과가 발생했습니다 🥲

2️⃣차 시도 방법 (시간 초과)

메모리를 덜 사용하면서, 방문한 행성을 체크해주기 위해 고민하다가 비트마스킹을 적용해봤습니다

data class Path(
  val position: Int, // 현재 있는 행성 위치
  val time: Int, // 지금까지 이동에 소요된 시간
  val visitedCnt: Int, // 지금까지 방문한 행성의 수
  val visitedMask: Int, // 행성들 방문 체크 - ⭐️ 비트마스킹
)

 

data class를 이렇게 변경해주었고, 방문 체크하는 방법이 비트마스킹으로 변경된 것 외에 다른 로직은 그대로 구현했습니다!

비트마스킹은 단어에서 유추해볼 수 있듯이 비트로 마스킹하여 무언가를 기록해두는 방식입니다 🤔

 

방문한 곳을 1, 방문하지 않은 곳을 0으로 체크하고 인덱스를 기준으로는 오른쪽 끝이 0번, 왼쪽 끝이 N-1번입니다

새롭게 방문한 행성을 체크 해주려면 해당 행성의 인덱스 위치에만 1을 놓고 OR 연산을 진행해주면 됩니다
예를 들어, 0번 행성만 방문한 상태인 00001에서 2번 행성을 추가로 방문했다면, 00001 OR 00100 = 00101로 체크해줄 수 있습니다

var planetPath = LinkedList<Path>() as Queue<Path>
var visitedMask = 1 shl K // ⭐️ ex) 0001이면 첫번째 행성만 방문한 것
planetPath.offer(Path(K, 0, 1, visitedMask))

var answer = 1000 * 10

while(!planetPath.isEmpty()) {
  val current = planetPath.poll()

  // 모든 행성을 탐색했다면
  if(current.visitedCnt == N) {
    answer = min(answer, current.time)
    continue
  }
  
  for(i: Int in 0..N-1) {
    // 현재 위치랑 같거나 이미 현재의 최소 시간을 넘어섰다면 
    if(current.position == i || current.time >= answer) continue

    var newVisitedCnt = current.visitedCnt
    if((current.visitedMask and (1 shl i)) == 0) newVisitedCnt++

    val newVisitedMask = current.visitedMask or (1 shl i)

    planetPath.offer(
      Path(
        position = i,
        time = current.time + planet[current.position][i],
        newVisitedCnt,
        visitedMask = newVisitedMask
      )
    )
  }
}

 메모리 초과 문제는 해결되었지만, 아무래도 같은 행성을 여러번 방문할 수 있다보니 경로 탐색을 너무 많이 하게 되어서 시간 초과가 발생한 것 같습니다

경로를 탐색하는 중간에 끊어줄 수 있는 방법을 고민하다가 도저히 떠오르지 않아서 솔루션을 찾아보게 되었습니다 🥺

3️⃣차 시도 방법 (솔루션 참고)

솔루션을 찾아보니 완전히 다른 방법으로 해결해내고 있었습니다...!

같은 행성을 여러번 방문할 수 있기 때문에 바로 가는 경우와 다른 행성을 거쳐서 가는 경우 중 더 시간이 적게 걸리는 경우를 미리 계산하고, 총 경로를 이후에 계산하는 방식으로 구현했습니다

A, B, C라는 행성이 있다고 할 때, A에서 C로 바로 가는 경우는 4의 시간이 걸리지만 A에서 B는 1, B에서 C는 2의 시간이 걸린다면 A -> B -> C로 가는 것이 총 3의 시간으로 더 적은 시간이 걸리게 됩니다

for(k: Int in 0..N-1) {
  for(i: Int in 0..N-1) {
    for(j: Int in 0..N-1) {
      if(i == j) continue // 출발과 도착이 같으면 패스
      // i에서 j로 바로 가는 것과 k를 거쳐서 가는 것 중 더 빠른 길을 저장
      planet[i][j] = min(planet[i][j], planet[i][k] + planet[k][j])
    }
  }
}

 

이렇게 미리 최소시간을 구해두고, 처음 방법처럼 경로를 구해줍니다.

대신 이번에는 이미 방문한 행성을 또 방문하지 않도록 막아주게 되어 시간이 단축되는 효과가 있습니다. 각 경우의 수마다 방문 유무를 체크하는 배열이 따로 필요하지 않기 때문에 저장 공간도 더 적게 사용하게 됩니다!

하지만 여기서 의문이 든 점은, '만약 A->D보다 A->B->C->D가 더 적은 시간이 걸린다면, 이 경우는 어떻게 처리해줄 수 있는가?' 입니다 🤔 이 의문점은 해소하지 못했지만 정답 처리가 되었습니다... 이 부분은 좀 더 고민이 필요할 것 같습니다...!

 

+) k가 결국 모든 행성을 체크하기 때문에 모든 경우의 수를 확인하고 최소 거리를 고려하게 되는 것이었습니다

---

✅ 정답 코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.StringTokenizer
import kotlin.math.min

var N: Int = 0
var K: Int = 0
lateinit var planet: Array<Array<Int>>
lateinit var visited: Array<Boolean>
var answer = Integer.MAX_VALUE

fun main() {
  // ✅ Input
  val br = BufferedReader(InputStreamReader(System.`in`))
  var st = StringTokenizer(br.readLine())

  N = st.nextToken().toInt() // 행성의 개수
  K = st.nextToken().toInt() // 발사되는 행성의 위치 = 시작점

  // 각 행성간 이동거리
  planet = Array(N, {Array(N, {0})})
  for(i: Int in 0..N-1) {
    st = StringTokenizer(br.readLine())
    for(j: Int in 0..N-1) {
      planet[i][j] = st.nextToken().toInt()
    }
  }

  // ✅ Solve
  visited = Array(N, {false})
  for(k: Int in 0..N-1) {
    for(i: Int in 0..N-1) {
      for(j: Int in 0..N-1) {
        if(i == j) continue // 출발과 도착이 같으면 패스
        // i에서 j로 바로 가는 것과 k를 거쳐서 가는 것 중 더 빠른 길을 저장
        planet[i][j] = min(planet[i][j], planet[i][k] + planet[k][j])
      }
    }
  }

  visited[K] = true
  dfs(1, K, 0)

  // ✅ Output
  print(answer)
}

// ✅ Solve
fun dfs(visitCnt: Int, position: Int, time: Int) {
  if(visitCnt == N) {
    answer = min(answer, time)
    return
  }

  for(i: Int in 0..N-1) {
    if(!visited[i]) {
      visited[i] = true
      dfs(visitCnt + 1, i, time + planet[position][i])
      visited[i] = false
    }
  }
}

---

📚 새롭게 알게된 내용

결국 정답 코드에서는 사용되지 않았지만 비트마스킹을 사용해보면서, 이후에 메모리 사용을 줄이기 위한 방법으로 적용해 보아야겠다는 생각을 했습니다!

 

+) 비트마스킹을 사용하면 속도 측면에서도 이득을 볼 수 있습니다

 

2-jung0115 by jung0115 · Pull Request #125 · AlgoLeadMe/AlgoLeadMe-4