<div id="readability-page-1" class="page"><div>            <h2>문제로 이동하기</h2>
<p><a href="https://www.acmicpc.net/problem/13549">https://www.acmicpc.net/problem/13549</a></p>
<h2>접근 방식</h2>
<p>앞서 소개 드렸던 이모티콘 문제와 마찬가지로, 이 문제도 BFS와 DP 모두 사용이 가능합니다. 저는 BFS로 해결했는데, 결과를 보니 DP에 비해 시간과 메모리 모든 면에서 처참했습니다 ㅜㅜ 추후 DP로 해결하는 방법도 포스팅하겠습니다.</p>
<p>이 문제에서 중요한 키워드는 <strong>"순간이동을 하는 경우에는 '0초' 후에 이동"</strong> 입니다. 즉, 가중치가 0인 간선이 존재한다는 것인데요, 지금까지 BFS로 풀 수 있는 중요한 키워드가 되는 말이 <strong>가중치가 모두 1이다.</strong> 라는 점이었다는 것을 생각해보면, 이 문제를 BFS로 접근할 수 없는 것이 아닌가 싶을 수 있는데요.</p>
<p>두 가지 방법을 생각해볼 수 있습니다.</p>
<ol>
<li>큐 두 개를 활용하여, 가중치에 대한 구분을 확실하게 해주는 방법</li>
<li>덱(앞 뒤 모두 push, pop이 가능한 자료구조)을 활용하는 방법</li>
</ol>
<p>덱을 활용하는 방법이 좀 더 명확하게 이해하기 좋아서 이번 포스트에서는 덱을 활용했습니다. </p>
<h2>Deque</h2>
<p>유감스럽게도 Go는 deque 자료구조를 제공하지 않습니다. 직접 구현해야 합니다. 다행히 그리 어렵지 않으니 아래의 코드를 활용해주세요.</p>
<pre><code>type deque struct {
    items []int
}

func (d *deque) pushFront(i int) {
    temp := []int{i}
    d.items = append(temp, d.items...)
}

func (d *deque) push(i int) {
    d.items = append(d.items, i)
}

func (d deque) top() int {
    return d.items[0]
}

func (d *deque) popFront() int {
    res := d.items[0]
    d.items = d.items[1:]
    return res
}</code></pre>
<h2>순서</h2>
<ol>
<li><p>우선 가중치가 0인 간선은 다음처럼 처리합니다.</p>
<pre><code> if 2*nx &lt;= 100_000 &amp;&amp; D[2*nx] == -1 {
     D[2*nx] = D[nx]
     q.pushFront(2 * nx)
 }</code></pre>
<p> 코드를 보시면, 간선 가중치가 0일 때는, 가중치에 1을 더하지 않습니다. 그리고, <code>pushFront()</code> 메서드를 활용하여, 현재 정점이 가중치가 1인 다른 정점보다 먼저 처리될 수 있게 queue의 맨 앞에 넣어줍니다. 이 점이 가장 중요합니다. </p>
</li>
<li><p>가중치가 1인 간선은 기존대로 처리합니다.</p>
<pre><code> if nx-1 &gt;= 0 &amp;&amp; D[nx-1] == -1 {
     D[nx-1] = D[nx] + 1
     q.push(nx - 1)
 }
 if nx+1 &lt;= 100_000 &amp;&amp; D[nx+1] == -1 {
     D[nx+1] = D[nx] + 1
     q.push(nx + 1)
 }</code></pre>
</li>
</ol>
<h2>코드</h2>
<pre><code>package main

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

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

var (
    D [100_001]int
)

type deque struct {
    items []int
}

func (d *deque) pushFront(i int) {
    temp := []int{i}
    d.items = append(temp, d.items...)
}

func (d *deque) push(i int) {
    d.items = append(d.items, i)
}

func (d deque) top() int {
    return d.items[0]
}

func (d *deque) popFront() int {
    res := d.items[0]
    d.items = d.items[1:]
    return res
}

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

func main() {
    defer w.Flush()
    N, K := scanInt(), scanInt()
    for i := range D {
        D[i] = -1
    }
    q := &amp;deque{}
    q.push(N)
    D[N] = 0
    for len(q.items) != 0 {
        nx := q.popFront()
        if 2*nx &lt;= 100_000 &amp;&amp; D[2*nx] == -1 {
            D[2*nx] = D[nx]
            q.pushFront(2 * nx)
        }
        if nx-1 &gt;= 0 &amp;&amp; D[nx-1] == -1 {
            D[nx-1] = D[nx] + 1
            q.push(nx - 1)
        }
        if nx+1 &lt;= 100_000 &amp;&amp; D[nx+1] == -1 {
            D[nx+1] = D[nx] + 1
            q.push(nx + 1)
        }
        if D[K] != -1 {
            break
        }
    }
    fmt.Fprintln(w, D[K])
}

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

문제로 이동하기
https://www.acmicpc.net/problem/13549
접근 방식
앞서 소개 드렸던 이모티콘 문제와 마찬가지로, 이 문제도 BFS와 DP 모두 사용이 가능합니다. 저는 BFS로 해결했는데, 결과를 보니 DP에 비해 시간과 메모리 모든 면에서 처참했습니다 ㅜㅜ 추후 DP로 해결하는 방법도 포스팅하겠습니다.
이 문제에서 중요한 키워드는 "순간이동을 하는 경우에는 '0초' 후에 이동" 입니다. 즉, 가중치가 0인 간선이 존재한다는 것인데요, 지금까지 BFS로 풀 수 있는 중요한 키워드가 되는 말이 가중치가 모두 1이다. 라는 점이었다는 것을 생각해보면, 이 문제를 BFS로 접근할 수 없는 것이 아닌가 싶을 수 있는데요.
두 가지 방법을 생각해볼 수 있습니다.
큐 두 개를 활용하여, 가중치에 대한 구분을 확실하게 해주는 방법
덱(앞 뒤 모두 push, pop이 가능한 자료구조)을 활용하는 방법
덱을 활용하는 방법이 좀 더 명확하게 이해하기 좋아서 이번 포스트에서는 덱을 활용했습니다. 
Deque
유감스럽게도 Go는 deque 자료구조를 제공하지 않습니다. 직접 구현해야 합니다. 다행히 그리 어렵지 않으니 아래의 코드를 활용해주세요.
type deque struct {
    items []int
}
func (d *deque) pushFront(i int) {
    temp := []int{i}
    d.items = append(temp, d.items...)
}
func (d *deque) push(i int) {
    d.items = append(d.items, i)
}
func (d deque) top() int {
    return d.items[0]
}
func (d *deque) popFront() int {
    res := d.items[0]
    d.items = d.items[1:]
    return res
}
순서
우선 가중치가 0인 간선은 다음처럼 처리합니다.
 if 2*nx <= 100_000 && D[2*nx] == -1 {
     D[2*nx] = D[nx]
     q.pushFront(2 * nx)
 }
 코드를 보시면, 간선 가중치가 0일 때는, 가중치에 1을 더하지 않습니다. 그리고, pushFront() 메서드를 활용하여, 현재 정점이 가중치가 1인 다른 정점보다 먼저 처리될 수 있게 queue의 맨 앞에 넣어줍니다. 이 점이 가장 중요합니다. 
가중치가 1인 간선은 기존대로 처리합니다.
 if nx-1 >= 0 && D[nx-1] == -1 {
     D[nx-1] = D[nx] + 1
     q.push(nx - 1)
 }
 if nx+1 <= 100_000 && D[nx+1] == -1 {
     D[nx+1] = D[nx] + 1
     q.push(nx + 1)
 }
코드
package main
import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)
var (
    w  = bufio.NewWriter(os.Stdout)
    sc = bufio.NewScanner(os.Stdin)
)
var (
    D [100_001]int
)
type deque struct {
    items []int
}
func (d *deque) pushFront(i int) {
    temp := []int{i}
    d.items = append(temp, d.items...)
}
func (d *deque) push(i int) {
    d.items = append(d.items, i)
}
func (d deque) top() int {
    return d.items[0]
}
func (d *deque) popFront() int {
    res := d.items[0]
    d.items = d.items[1:]
    return res
}
func init() {
    sc.Split(bufio.ScanWords)
}
func main() {
    defer w.Flush()
    N, K := scanInt(), scanInt()
    for i := range D {
        D[i] = -1
    }
    q := &deque{}
    q.push(N)
    D[N] = 0
    for len(q.items) != 0 {
        nx := q.popFront()
        if 2*nx <= 100_000 && D[2*nx] == -1 {
            D[2*nx] = D[nx]
            q.pushFront(2 * nx)
        }
        if nx-1 >= 0 && D[nx-1] == -1 {
            D[nx-1] = D[nx] + 1
            q.push(nx - 1)
        }
        if nx+1 <= 100_000 && D[nx+1] == -1 {
            D[nx+1] = D[nx] + 1
            q.push(nx + 1)
        }
        if D[K] != -1 {
            break
        }
    }
    fmt.Fprintln(w, D[K])
}
func scanInt() int {
    sc.Scan()
    n, _ := strconv.Atoi(sc.Text())
    return n
}
마무리
여기까지 따라오시느라 고생 많으셨습니다. 만약 이 글이 도움이 되셨다면 글 좌측 하단의 하트❤를 눌러주시면 감사하겠습니다.
혹시라도 글에 이상이 있거나, 이해가 가지 않으시는 부분, 또는 추가적으로 궁금하신 내용이 있다면 주저 마시고 댓글 을 남겨주세요! 빠른 시간 안에 답변을 드리겠습니다

[BOJ/13549/Golang] 백준 13549 - 숨바꼭질 3 - BFS로 풀이

댓글