<div id="readability-page-1" class="page"><div>            <h2>접근 방식</h2>
<p>오랜만에 풀어본 BFS 문제입니다. 일반 숨바꼭질 문제와 똑같습니다만 추가로 이동 방법까지 출력해야 하는 문제입니다. 이동 방법을 구하는 문제라면 이전에도 살펴보았듯이 이전 부모의 이력을 계속 기록해놓았다가 마지막에 역순으로 출력하는 식으로 해결할 수 있습니다. </p>
<p>이 문제에서는 <code>visited</code> 를 확인하는 배열을 따로 두지 않았습니다. 이유는 부모 이력을 기록하는 배열에 이력이 기록된 상태라면 이미 방문한 노드임을 확신할 수 있기 때문입니다. </p>
<p>BFS를 수행하는 과정은 쉬운 BFS 문제들과 거의 유사하기 때문에 코드를 보면서 이해하시는 편이 빠를 것이라 생각합니다.</p>
<h2>개선 사항</h2>
<pre><code>func printRoute(S int) {
    if P[S] == -1 {
        fmt.Fprintf(w, "%d ", S)
        return
    }
    printRoute(P[S])
    fmt.Fprintf(w, "%d ", S)
}</code></pre>
<p>이력을 출력해주는 함수를 만들었습니다만, 이 함수는 개선할 수 있습니다. 종료 조건을 <code>P[S] == -1</code> 이 아니라, <code>S == N</code> 으로 두면 됩니다. 그러면, 다음과 같이 개선할 수 있습니다.</p>
<pre><code>func printRoute(S) {
    if S != N {
        printRoute(P[S])
    }
    fmt.Fprintf(w, "%d ", S)
}</code></pre>
<h2>코드</h2>
<pre><code>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 &lt;= 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 &lt;= 100000 {
            if P[nx+1] == -2 {
                q = append(q, nx+1)
                D[nx+1] = D[nx] + 1
                P[nx+1] = nx
            }
        }
        if 2*nx &lt;= 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
}</code></pre>
<h2>마무리</h2>
<p>여기까지 따라오시느라 고생 많으셨습니다. 만약 이 글이 도움이 되셨다면 글 좌측 하단의 하트❤를 눌러주시면 감사하겠습니다.</p>
<p>혹시라도 글에 이상이 있거나, 이해가 가지 않으시는 부분, 또는 추가적으로 궁금하신 내용이 있다면 주저 마시고 댓글💬을 남겨주세요! 빠른 시간 안에 답변을 드리겠습니다 😊</p>
                        
</div></div>

욱이의 IT 생존일지

Jaewook Oh

접근 방식
오랜만에 풀어본 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
}
마무리
여기까지 따라오시느라 고생 많으셨습니다. 만약 이 글이 도움이 되셨다면 글 좌측 하단의 하트❤를 눌러주시면 감사하겠습니다.
혹시라도 글에 이상이 있거나, 이해가 가지 않으시는 부분, 또는 추가적으로 궁금하신 내용이 있다면 주저 마시고 댓글 을 남겨주세요! 빠른 시간 안에 답변을 드리겠습니다

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

댓글