[백준/Swift] 24445: 알고리즘 수업 - 너비 우선 탐색 2

문제

24445번: 알고리즘 수업 - 너비 우선 탐색 2

간단한 문제 요약

시작 정점을 기준으로 주어진 정점을 탐색할 때 한 정점에서 갈 수 있는 여러개의 정점이 존재합니다. 이때 내림차순으로(큰 번호부터) 탐색을 이어나갑니다.

문제 풀이,  느낀점

var graph = Array(repeating: [Int](), count: n)
_=(0..<m).map{_ in
  let input = readLine()!.split{$0==" "}.map{Int(String($0))! - 1}
  graph[input[0]].append(input[1])
  graph[input[1]].append(input[0])
}

 

그래프의 노드간 순서가 없습니다. 그래서 서로 연결해야 합니다.

graph = graph.map{$0.sorted(by:>)}

 

또한 내림차순으로 탐색하기 위해서 문제에서 입력받은 노드의 크기를 내림차순으로 소팅해주면 됩니다. 그리고 bfs 탐색을 할 때마다 방문하는 노드의 순서를 매겨주면 됩니다.

 

한 가지 느낀점은 오랜만에 다시 알고리즘 문제 풀기를 시작했는데 분명 올바른 로직임에도 연속해서 틀렸는데.... 그 이유는 문제의 예제에 초점을 맞췄다는 것입니다. 그래프의 시작 노드는 문제에서 주어져야 하는데 제가 1로 고정해버렸다는...ㅋㅋㅋ;;

코드

import Foundation

let nmr = readLine()!.split{$0==" "}.map{Int(String($0))!}
let n = nmr[0], m = nmr[1], s = nmr[2] - 1

var graph = Array(repeating: [Int](), count: n)
_=(0..<m).map{_ in
  let input = readLine()!.split{$0==" "}.map{Int(String($0))! - 1}
  graph[input[0]].append(input[1])
  graph[input[1]].append(input[0])
}
graph = graph.map{$0.sorted(by:>)}
func bfs() {
  var visited = Array(repeating: 0, count: n)
  var queue = [s]
  var count = 1
  var idx = 0
  visited[s] = count
  while idx < queue.count {
    let vertex = queue[idx]
    idx += 1
    _=graph[vertex].map {
      if visited[$0] != 0 { return }
      count += 1
      queue.append($0)
      visited[$0] = count
    }
  }
  print(visited.map{String($0)}.joined(separator: "\n"))
}
bfs()