[Swift][DFS][BFS] 백준 16947번 (서울 지하철 2호선)

요구능력 : DFS & BFS

 

코드설명 : 

 

이 문제에서 요구하는 핵심사항

1. 인접리스트

2. 순환선

3. 역과 순환선 사이의 거리

 

1. 인접리스트

인접리스트는 해당 인덱스번호와 이어진 노드들을 해당인덱스의 배열에 넣으면 완성된다.

정점과 간선이 주어진다면 인접리스트를 생각하는 습관을 들이는게 좋다.

var graph : [[Int]] = Array(repeating: [], count: n + 1)
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()
}

 

2. 순환선

순환선이라하면 시작노드에서 다시 시작노드로 돌아올때가 순환선이된다.

예를 들어서, 1 -> 2 -> 3 -> 1 과 같은경우 순환선이다.

하지만 주의할 점이 있다.

1 -> 2 -> 1 과 같은경우에는 순환선이 될 수 없다.

그림으로 그려보면 알것이다. 순환선이 아닌 그냥 일직선이라는것을..

 

위의 설명으로봤을때 도출한결과

시작노드와 현재노드가 같아지면 순환선이 되지만, 1->2->1같은 경우를 걸러야한다.

이미 방문한곳을 재방문할 때 dfs를 3번이상 들어오고 현재노드와 시작노드가 같다면 그건 순환선일 수 밖에없다.

dfs를 3번이상 돌았다는건 적어도 3개의 노드를 돌았다는 말이기 때문이다.

 

func dfs(_ depth: Int, _ startNode: Int, _ currentNode: Int){
    
    if depth >= 2 && currentNode == startNode{
        checked[currentNode] = true
        return
    }
    visited[currentNode] = true
    for i in graph[currentNode]{
        if !visited[i]{
            dfs(depth + 1, startNode, i)
        }else{
            if depth >= 2 && startNode == i{
                dfs(depth, startNode, i)
            }
        }
    }
}
for i in 1...n{
    visited = Array(repeating: false, count: 3001)
    dfs(0, i, i)
}

 

3. 역과 순환선 사이의 거리

BFS로 탐색하여 거리를 찾아주었다.

나는 위의 DFS에서 checked[]배열을 사용해서 순환선에 해당하는 노드들은 true를 넣어주었다.

그래서 BFS의 종료조건으로 queue에서 뺀 값으로 checked[queue에서 뺀 값]를 활용하여 true이면 순환선에 닿은것이므로 방문횟수(pop.1)을 리턴해줬다.

func bfs(_ x: Int) -> Int{
    var bfsVisit = Array(repeating: false, count: 3001)
    var queue = [(Int, Int)]() //노드, 방문횟수
    queue.append((x, 0))
    while !queue.isEmpty{
        let pop = queue.removeFirst()
        if checked[pop.0]{//사이클에 닿은거임.
            return pop.1
        }
        for i in graph[pop.0]{
            if !bfsVisit[i]{
                queue.append((i, pop.1 + 1))
                bfsVisit[i] = true
            }
        }
        
    }
    return 0
}
result.removeFirst()
print(result.map{String($0)}.joined(separator: " "))

 

 

후기 : 그래프문제는 그렇게 많이 안풀어봐서 힘들게풀었다.. 골드3정도는 아닌거같다

let n = Int(String(readLine()!))!
var graph : [[Int]] = Array(repeating: [], count: n + 1)
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()
}

var visited = Array(repeating: false, count: 3001)
var checked = Array(repeating: false, count: n + 1)
var result = Array(repeating: 0, count: n + 1)
func dfs(_ depth: Int, _ startNode: Int, _ currentNode: Int){
    
    if depth >= 2 && currentNode == startNode{
        checked[currentNode] = true
        return
    }
    visited[currentNode] = true
    for i in graph[currentNode]{
        if !visited[i]{
            dfs(depth + 1, startNode, i)
        }else{
            if depth >= 2 && startNode == i{
                dfs(depth, startNode, i)
            }
        }
    }
}
for i in 1...n{
    visited = Array(repeating: false, count: 3001)
    dfs(0, i, i)
}
for i in 1...n{
    if !checked[i]{
        result[i] = bfs(i)
    }else{
        result[i] = 0
    }
}

func bfs(_ x: Int) -> Int{
    var bfsVisit = Array(repeating: false, count: 3001)
    var queue = [(Int, Int)]()
    queue.append((x, 0))
    while !queue.isEmpty{
        let pop = queue.removeFirst()
        if checked[pop.0]{//사이클에 닿은거임.
            return pop.1
        }
        for i in graph[pop.0]{
            if !bfsVisit[i]{
                queue.append((i, pop.1 + 1))
                bfsVisit[i] = true
            }
        }
        
    }
    return 0
}
result.removeFirst()
print(result.map{String($0)}.joined(separator: " "))