[BOJ/16947/Golang] 백준 16947 - 서울 지하철 2호선

문제로 이동하기

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

접근 방식

큰 순서는 다음과 같습니다.

1. 그래프 내의 모든 사이클과 사이클에 속한 정점을 구한다.
2. 사이클에 속한 정점에 연결된 정점들 중 사이클에 속하지 않은 정점을 방문하며 거리를 구한다.

하지만 이 문제에서 핵심은 사이클을 찾고, 사이클에 속한 정점을 구하는 과정입니다. 위 2번은 그저 찾아낸 정점으로부터 DFS 또는 BFS를 수행하면 쉽게 찾을 수 있습니다. 물론 DFS보다는 BFS로 찾는게 더 효율적입니다. 이유는 후에 설명 드리겠습니다.

트리

• N개의 정점과 N-1개의 간선으로 이루어진 그래프는 트리입니다.
• 트리는 사이클이 없으며, 최단 경로를 DFS와 BFS로 구할 수 있습니다.
• 만약 이 트리에 간선이 하나 더 추가 된다면, 사이클은 반드시 하나 있게 됩니다.

사이클

사이클은 시작과 끝이 같은 경로를 의미합니다.

사이클 구하기

사이클을 찾는 큰 틀은 DFS를 따라갑니다. 그리고 방문 여부를 판단하기 위한 check[] 배열에 0과 1뿐만 아니라, 해당 정점이 사이클에 속하는지 판단할 수 있도록 2라는 값도 주려고 합니다. 정리하면 check[] 배열은 다음의 값을 갖습니다.

• 0 : 아직 방문하지 않았음
• 1 : 방문하였고 해당 정점은 사이클에 속하지 않음
• 2 : 방문하였고 해당 정점이 사이클에 속함

이제 사이클을 찾는 함수를 작성해보겠습니다.

func solve(node, prev int) int {
    if check[node] == 1 {
        return node
    }
    check[node] = 1
    for i := range G[node] {
        next := G[node][i]
        if next == prev {
            continue
        }
        res := solve(next, node)
        if res == -2 {
            return -2
        }
        if res >= 0 {
            check[node] = 2
            if node == res {
                return -2
            }
            return res
        }
    }
    return -1
}

함수의 인자

먼저 사이클을 구하는 함수는 인자로 현재 정점과 현재 정점으로 오기 직전의 부모 정점 정보를 받습니다. 부모 정점 정보를 받는 이유는 이 문제에서 주어진 그래프가 양방향 그래프이기 때문입니다. 부모 정점에서 현재 정점으로 올 수 있었다면, 양방향 그래프에선 당연하게도 현재 정점에서 부모 정점으로도 이동할 수 있습니다. 이러한 함정을 피하기 위해 두 인자를 받습니다.

함수의 리턴값

• -2 : 주어진 그래프에서 사이클이 발견되었지만, 현재 정점은 사이클에 속하는 정점이 아님을 의미.
• -1 : 주어진 그래프에서 사이클이 발견되지 않았음.
• 0 ~ n-1 : 주어진 그래프에서 사이클이 발견되었으며, 현재 정점은 사이클에 속하는 정점임. 주어지는 값은 사이클의 시작 정점 번호를 의미함

중복 확인

함수가 호출되면 가장 먼저, 현재 확인하려는 정점을 이미 방문한 정점인지 확인해야 합니다. 특히, 현재 정점이 사이클에 속하지 않은 정점(1)이라면 더 탐색할 이유가 없습니다. 그대로 현재 정점을 리턴하고 종료합니다.

방문 기록

현재 정점에 처음 방문했다면, 방문 이력을 기록합니다. 이 때 현재 정점이 사이클에 속하는지 속하지 않는지를 아직 판단할 수 없기 때문에 방문했다는 표시만 남기기 위해 1로 기록합니다.

현재 정점과 간선으로 연결된 이웃 정점 탐색

현재 정점과 간선으로 연결된 이웃 정점을 탐색합니다. 이 때 아래와 같은 조건에 따라 상황을 구분합니다.

1. 이웃 정점이 부모 정점일 때(next == prev)
   이 때는 해당 간선을 타고 이동하면 안되므로, 아무런 작업을 하지 않고 넘깁니다.
2. 이웃 정점을 탐색하고 온 값이 X일 때
   1. X == -2
X가 -2일 때는 해당 정점이 사이클에 속하지 않는 정점이라는 것을 의미합니다.
   2. X >= 0
X가 0 이상이라는 것은 X의 값과 일치하는 정점이 나올 때까지 탐색한 정점들은 사이클에 속하는 정점이라는 것을 의미합니다. 따라서 해당 정점의 방문 이력을 2로 수정합니다.
      만약 X의 값과 일치하는 정점이 나오면, 그 이후의 정점부터는 사이클에 속하지 않는 정점이므로, -2를 리턴합니다.

그 무엇에도 속하지 않은 경우

현재 그래프에 사이클이 없음을 의미합니다. 따라서 값으로 -1을 리턴합니다.

사이클에 포함된 정점을 시작 정점으로 하여 거리 계산

이제 모든 사이클의 정점을 찾았으니, 사이클에 속한 정점들로부터 사이클에 속하지 않은 정점들의 최단 거리들을 구해봅니다. 이 과정은 기존 문제에서 많이 사용한 BFS로 해결할 수 있습니다.

참고로, DFS와 BFS 모두 사용할 수 있으나, BFS를 사용한 이유는 시작 정점이 1개가 아니기 때문입니다. BFS는 큐에 모든 시작 정점을 넣어두면 자동으로 해당 정점으로부터의 모든 거리를 찾아주지만, DFS는 시작 정점마다 각각 DFS를 호출해주는 번거로움이 있습니다. 따라서 본 문제를 해결할 때는 BFS를 사용했습니다. 우선 코드를 보겠습니다.

for i := 1; i <= N; i++ {
        if check[i] == 2 && !check2[i] {
            q := make([]int, 0)
            q = append(q, i)
            check2[i] = true
            for len(q) != 0 {
                cur := q[0]
                q = q[1:]
                for j := range G[cur] {
                    next := G[cur][j]
                    if check[next] != 2 && !check2[next] {
                        check2[next] = true
                        D[next] = D[cur] + 1
                        q = append(q, next)
                    }
                }
            }
        }
    }

일반적인 BFS 과정과 같습니다. 추가 조건이 있다면, 탐색을 할 때, 사이클에 속한 정점은 탐색하지 않아야 한다는 점입니다. 사이클에 속한 정점은 시작 정점이 되어야 하기 때문입니다. 이를 위해 조건문으로 check[i] != 2 라는 조건을 넣어주었습니다.

한 가지 만족스럽지 못한 점은 check2[] 배열입니다. 실은 check2[] 배열을 이용하지 않고 D[] 배열을 이용해서 BFS 방문 여부를 확인할 수 있지만, 이 문제를 풀 때는 그 내용을 생각하지 못했습니다. 코드를 개선한다면 check2[] 배열부터 없앨 수 있겠습니다.

코드

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

var (
    w  = bufio.NewWriter(os.Stdout)
    sc = bufio.NewScanner(os.Stdin)
)

var (
    N      int
    check  []int
    check2 []bool
    D      []int
    G      [][]int
)

func init() {
    sc.Split(bufio.ScanWords)
}

func main() {
    defer w.Flush()
    N = scanInt()
    check = make([]int, N+1)
    check2 = make([]bool, N+1)
    D = make([]int, N+1)
    G = make([][]int, N+1)
    for i := 0; i < N; i++ {
        u, v := scanInt(), scanInt()
        G[u] = append(G[u], v)
        G[v] = append(G[v], u)
    }

    // cycle부터 찾는다.
    solve(1, -1)

    // cycle에서 시작하여 연결된 노드를 찾는다.
    for i := 1; i <= N; i++ {
        if check[i] == 2 && !check2[i] {
            q := make([]int, 0)
            q = append(q, i)
            check2[i] = true
            for len(q) != 0 {
                cur := q[0]
                q = q[1:]
                for j := range G[cur] {
                    next := G[cur][j]
                    if check[next] != 2 && !check2[next] {
                        check2[next] = true
                        D[next] = D[cur] + 1
                        q = append(q, next)
                    }
                }
            }
        }
    }

    for i := 1; i <= N; i++ {
        fmt.Fprintf(w, "%d ", D[i])
    }
}

func solve(node, prev int) int {
    if check[node] == 1 {
        return node
    }
    check[node] = 1
    for i := range G[node] {
        next := G[node][i]
        if next == prev {
            continue
        }
        res := solve(next, node)
        if res == -2 {
            return -2
        }
        if res >= 0 {
            check[node] = 2
            if node == res {
                return -2
            }
            return res
        }
    }
    return -1
}

func scanInt() int {
    sc.Scan()
    n, _ := strconv.Atoi(sc.Text())
    return n
}

마무리

여기까지 따라오시느라 고생 많으셨습니다. 만약 이 글이 도움이 되셨다면 글 좌측 하단의 하트❤를 눌러주시면 감사하겠습니다.

혹시라도 글에 이상이 있거나, 이해가 가지 않으시는 부분, 또는 추가적으로 궁금하신 내용이 있다면 주저 마시고 댓글💬을 남겨주세요! 빠른 시간 안에 답변을 드리겠습니다 😊