[DFS] 백준 11725번: 트리의 부모 찾기(Swift)

난이도: 실버 2

사용 언어: Swift

카테고리: DFS

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

Code

let n = Int(readLine()!)!

var links: [[Int]] = Array(repeating: [], count: n + 1)
var visited = Array(repeating: false, count: n + 1)

for _ in 1..<n {
  let value = readLine()!.split(separator: " ").map { Int($0)! }
  links[value[0]].append(value[1])
  links[value[1]].append(value[0])
}

var parents = Array(repeating: 0, count: n + 1)

func dfs(start: Int, parent: Int) {
  visited[start] = true
  parents[start] = parent
  
  for i in links[start] {
    if !visited[i] {
      dfs(start: i, parent: start)
    }
  }
}

dfs(start: 1, parent: 0)

for i in 2...n {
  print(parents[i])
}

💡 첫 제출에 메모리 초과 라는 결과가 나왔다...

문제는,

var link = Array(repeating: Array(repeating: false, count: n + 1), count: n + 1)

for _ in 1..<n {
  let value = readLine()!.split(separator: " ").map { Int($0)! }
  link[value[0]][value[1]] = true
  link[value[1]][value[0]] = true
}

위와 같이 꽉찬 이중 배열이 문제였다. 위 문제에서 최대 노드의 수는 100,000개 즉 노드의 개수가 최대이면 배열의 크기는 100,000 x 100,000가 된다. 즉, 256MB를 초과한다.

때문에,

var links: [[Int]] = Array(repeating: [], count: n + 1)

for _ in 1..<n {
  let value = readLine()!.split(separator: " ").map { Int($0)! }
  links[value[0]].append(value[1])
  links[value[1]].append(value[0])
}

위와 같이 각 노드 별로 배열을 만들고 자식 노드를 추가하여, 잉여 메모리가 없도록 하였다.