白駿16947号:ソウル地下鉄2号線-Swift

https://www.acmicpc.net/problem/16947
難易度金貨3🥇
アルゴリズム分類:bfs、dfs
🧐 質問へのアクセス
この問題を解決するには2つのステップが必要です.
図

の周期部分を求めなければならない.

すべての点とグラフィックサイクルの距離を求める必要があります.最初の問題はdfsで、2番目の問題はbfsです.
コード#コード#
1.図形の周期を求める
どのようにしてまず図形の周期を求めますか?
基本的な考え方はvisitにフィルタリングする前に、すでにアクセスした場所がまたアクセスしたかどうかを確認することです.
しかしながら、1−>2−>1のようなナビゲーションはcycleとは呼べないため、前にアクセスしたbefore変数を使用して前のアクセスの場所をフィルタリングする.
すべてのナビゲーションはログ配列に格納され、ループが発生すると、ログ配列を使用してループを組織するドメインがループ配列に格納されます.
cycleが見つかった場合は、ナビゲーションする必要はありません.
(頂点と幹線の数は同じで、すべての接続されたグラフィックには1サイクルしかありません.)
したがって、dfs再帰条件にflag変数を設定して、不要な再帰を阻止する.

var log = [1]
var flag = false

func dfs(_ x: Int, _ before: Int) {
    visit[x] = true
    //다음에 방문할 곳 확인
    for nx in graph[x] {
        if nx != before && log.contains(nx) {
            let idx = log.firstIndex(of: nx)!
            log[idx...].forEach{cycle[$0] = true}
            flag = true
        }
        
        if !visit[nx] && !flag {
            log.append(nx)
            dfs(nx,x)
            log.removeLast()
        }
        
    }
}

2.全駅から環状線までの距離を求める
最初に,bfs中のすべての点(ループではなく)にナビゲートし,それぞれの距離を求めた.
時間を超えていませんが、一見非効率的な方法で、時間も他の人より10倍ほど遅れています.
ループラインの頂点をキューに入れてbfsナビゲーションを行うだけで、1回のナビゲーションで答えを得ることができます.
すべてのループラインをキューに入れ、dist配列を使用して処理する場合は、エンドポイントを探す必要はありません.

var dist = Array(repeating: -1, count: n+1)
var queue = [Int]()
for i in 1...n where cycle[i] {
    dist[i] = 0
    queue.append(i)
}

func bfs(_ queue: [Int]) {
    var queue = queue
    var idx = 0
    
    while queue.count > idx {
        let cur = queue[idx]
        idx += 1
        
        for nx in graph[cur] {
            if dist[nx] == -1 {
                queue.append(nx)
                dist[nx] = dist[cur] + 1
            }
        }
    }
}

完全なコード

//16947번 서울 지하철 2호선

let n = Int(readLine()!)!

var graph = Array(repeating: [Int](), count: n+1)
var visit = Array(repeating: false, count: n+1)
var cycle = Array(repeating: false, count: n+1)

for _ in 0..<n {
    let t = readLine()!.split(separator: " ").map{Int(String($0))!}
    let (a,b) = (t[0],t[1])
    graph[a].append(b)
    graph[b].append(a)
}

//step 1 : 순환선을 찾는다
var log = [1]
var flag = false

func dfs(_ x: Int, _ before: Int) {
    visit[x] = true
    //다음에 방문할 곳 확인
    for nx in graph[x] {
        if nx != before && log.contains(nx) {
            let idx = log.firstIndex(of: nx)!
            log[idx...].forEach{cycle[$0] = true}
            flag = true
        }
        
        if !visit[nx] && !flag {
            log.append(nx)
            dfs(nx,x)
            log.removeLast()
        }
        
    }
}

dfs(1,0)

var dist = Array(repeating: -1, count: n+1)
var queue = [Int]()
for i in 1...n where cycle[i] {
    dist[i] = 0
    queue.append(i)
}

func bfs(_ queue: [Int]) {
    var queue = queue
    var idx = 0
    
    while queue.count > idx {
        let cur = queue[idx]
        idx += 1
        
        for nx in graph[cur] {
            if dist[nx] == -1 {
                queue.append(nx)
                dist[nx] = dist[cur] + 1
            }
        }
    }
}

bfs(queue)
print(dist[1...].map{String($0)}.joined(separator: " "))

単行評価:dfsとbfsが書かなければならない良い問題: