[백준] (Swift) 16947번 - 서울 지하철 2호선 (BFS, DFS 동시에 사용하는 문제)

 

🟣 문제 링크

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

16947번: 서울 지하철 2호선

 

🟣 문제 풀이

우선 문제를 이해하는데 어려웠다. 그림을 그리면서 + 그리고 인터넷을 찾아보면서 문제를 이해했다.

우선, '순환선 = 사이클'을 찾아야한다. 

이 지하철 노선도로 보면, '신도림'역은 이미 순환선 (사이클) 내부에 있기 때문에 순환선까지의 거리가 0이다. 하지만 '까치산'역인 경우, 순환선이 아니라 지선에 속한다. 이 까치산역은 '순환선'까지 4개의 거리가 있다.

이처럼 순환선과 지선을 구별하여, 지선에 위치한 역인 경우 순환선까지의 거리를 구하면 되는 문제이다.

---

그럼 이 문제를 해결하기 위해서는, 해당역이 순환선에 위치하는지, 지선에 위치하는지 알아야하기 때문에 이것을 먼저 판단해줘야한다.

🟣 순환선 찾기 → DFS 이용

순환선이되기 위한 조건이 있다. '시작점'으로 다시 돌아와야한다는 것이다.

1번역 → 2번역 → 3번역 → 1번역 

이렇게 된다면, 위 1,2,3번역은 모두 순환선에 위치한다.

⭐️ 하지만 1번역 → 2번역  → 1번역 이렇게 되는 경우, 순환선이라고 볼 수없다. 그냥 앞으로 갔다가 뒤로 돌아간것이기때문이다. 따라서 두번 이상 다른역에 방문해야만! 순환선에 해당된다.⭐️ 이 경우를 생각해내는게 포인트인것 같다...

결론은 "현재역 == 시작역  and 두번 이상 다른 역 방문" 해당 조건을 만족해야만 순환선이 된다.

 

🟣 순환선까지의 거리 구하기  → BFS 이용

일단 순환선에 속하는 역은 모두 distance를 0으로 넣어주고 BFS탐색을 해줄 것이다. 순환역에 속하지 않는 역은 방문한 적이 없는 역들만 방문하면서 현재 역의 거리 + 1을 해주면서 다음 역에 저장해준다.

---

🟣 문제 소스코드

인터넷 참고하면서 풀었고, 생각하는데 좀 힘들었다. 많이 풀어봤다고 생각되는데 왜 bfs/dfs 는 어렵게 느껴지지 ㅠㅠ

https://github.com/deslog/Algorithm/blob/main/Algorithm/Boj/16947_%EC%84%9C%EC%9A%B8%EC%A7%80%ED%95%98%EC%B2%A02%ED%98%B8%EC%84%A0/main.swift

GitHub - deslog/Algorithm

//
//  main.swift
//  Algorithm
//
//  Created by 이지수 on 2022/06/30.
//

let n = Int(readLine()!)!
var graph = Array(repeating: [Int](), count: n+1)
var visited = Array(repeating: false, count: n+1)
var cycle = Array(repeating: false, count: n + 1)
var dist = Array(repeating: 0, count: n + 1)

// 순환선?
func dfs(depth: Int, startIdx: Int, currentIdx: Int) {
    if currentIdx == startIdx && depth >= 2 {
        cycle[currentIdx] = true
        return
    }
    visited[currentIdx] = true
    
    for i in graph[currentIdx] {
        if !visited[i] {
            dfs(depth: depth+1, startIdx: startIdx, currentIdx: i)
        } else { //이미 방문한 역이라면
            if depth >= 2, startIdx == i {
                dfs(depth: depth, startIdx: startIdx, currentIdx: i)
            }
        }
    }
}

// 순환선 아닌애들 dfs돌려서 dist 찾아줘
func bfs(x: Int) -> Int {
    var bfsVisited = Array(repeating: false, count: 3001)
    var queue = [[Int]]()
    queue.append([x, 0])
    while !queue.isEmpty {
        let pop = queue.removeFirst()
        if cycle[pop[0]] {  // 사이클에 포함 -> 사이클에 도달한거임
            return pop[1]
        }
        for i in graph[pop[0]] {
            if !bfsVisited[i] {
                queue.append([i, pop[1] + 1])
                bfsVisited[i] = true
            }
        }
    }
    return 0
}

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

// dfs함수 실행
for i in 1...n {
    visited = Array(repeating: false, count: 3001)
    dfs(depth: 0, startIdx: i, currentIdx: i)
}

// cycle 안에있으면 거리 0 아니면 bfs적용
for i in 1...n {
    if !cycle[i] {
        dist[i] = bfs(x: i)
    } else {
        dist[i] = 0
    }
}

dist.removeFirst()
print(dist.map{ String($0) }.joined(separator: " "))