[BOJ/13913/Golang] 백준 13913 - 숨바꼭질 4

접근 방식

오랜만에 풀어본 BFS 문제입니다. 일반 숨바꼭질 문제와 똑같습니다만 추가로 이동 방법까지 출력해야 하는 문제입니다. 이동 방법을 구하는 문제라면 이전에도 살펴보았듯이 이전 부모의 이력을 계속 기록해놓았다가 마지막에 역순으로 출력하는 식으로 해결할 수 있습니다.

이 문제에서는 visited 를 확인하는 배열을 따로 두지 않았습니다. 이유는 부모 이력을 기록하는 배열에 이력이 기록된 상태라면 이미 방문한 노드임을 확신할 수 있기 때문입니다.

BFS를 수행하는 과정은 쉬운 BFS 문제들과 거의 유사하기 때문에 코드를 보면서 이해하시는 편이 빠를 것이라 생각합니다.

개선 사항

func printRoute(S int) {
    if P[S] == -1 {
        fmt.Fprintf(w, "%d ", S)
        return
    }
    printRoute(P[S])
    fmt.Fprintf(w, "%d ", S)
}

이력을 출력해주는 함수를 만들었습니다만, 이 함수는 개선할 수 있습니다. 종료 조건을 P[S] == -1 이 아니라, S == N 으로 두면 됩니다. 그러면, 다음과 같이 개선할 수 있습니다.

func printRoute(S) {
    if S != N {
        printRoute(P[S])
    }
    fmt.Fprintf(w, "%d ", S)
}

코드

package main

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

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

var (
    P [100001]int
    D [100001]int
)

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

func main() {
    defer w.Flush()
    N, K := scanInt(), scanInt()
    for i := range P {
        P[i] = -2
    }
    q := make([]int, 0)
    q = append(q, N)
    P[N] = -1
    D[N] = 0
    for len(q) != 0 {
        nx := q[0]
        q = q[1:]
        if 0 <= nx-1 {
            if P[nx-1] == -2 {
                q = append(q, nx-1)
                D[nx-1] = D[nx] + 1
                P[nx-1] = nx
            }
        }
        if nx+1 <= 100000 {
            if P[nx+1] == -2 {
                q = append(q, nx+1)
                D[nx+1] = D[nx] + 1
                P[nx+1] = nx
            }
        }
        if 2*nx <= 100000 {
            if P[2*nx] == -2 {
                q = append(q, 2*nx)
                D[2*nx] = D[nx] + 1
                P[2*nx] = nx
            }
        }
        if P[K] != -2 {
            break
        }
    }
    fmt.Fprintln(w, D[K])
    printRoute(K)
}

func printRoute(S int) {
    if P[S] == -1 {
        fmt.Fprintf(w, "%d ", S)
        return
    }
    printRoute(P[S])
    fmt.Fprintf(w, "%d ", S)
}

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

마무리

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

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