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

문제로 이동하기

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

접근 방식

앞서 소개 드렸던 이모티콘 문제와 마찬가지로, 이 문제도 BFS와 DP 모두 사용이 가능합니다. 저는 BFS로 해결했는데, 결과를 보니 DP에 비해 시간과 메모리 모든 면에서 처참했습니다 ㅜㅜ 추후 DP로 해결하는 방법도 포스팅하겠습니다.

이 문제에서 중요한 키워드는 "순간이동을 하는 경우에는 '0초' 후에 이동" 입니다. 즉, 가중치가 0인 간선이 존재한다는 것인데요, 지금까지 BFS로 풀 수 있는 중요한 키워드가 되는 말이 가중치가 모두 1이다. 라는 점이었다는 것을 생각해보면, 이 문제를 BFS로 접근할 수 없는 것이 아닌가 싶을 수 있는데요.

두 가지 방법을 생각해볼 수 있습니다.

1. 큐 두 개를 활용하여, 가중치에 대한 구분을 확실하게 해주는 방법
2. 덱(앞 뒤 모두 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
}

순서

1. 우선 가중치가 0인 간선은 다음처럼 처리합니다.

    if 2*nx <= 100_000 && D[2*nx] == -1 {
        D[2*nx] = D[nx]
        q.pushFront(2 * nx)
    }

   코드를 보시면, 간선 가중치가 0일 때는, 가중치에 1을 더하지 않습니다. 그리고, pushFront() 메서드를 활용하여, 현재 정점이 가중치가 1인 다른 정점보다 먼저 처리될 수 있게 queue의 맨 앞에 넣어줍니다. 이 점이 가장 중요합니다.

2. 가중치가 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
}

마무리

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

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