[BOJ/14226/Golang] 백준 14226 - 이모티콘 - BFS로 풀이

접근 방식

이 문제는 BFS로도 접근이 가능하고, DP로도 가능합니다. DP가 더 빠른 성능을 보여주기 때문에 수행 시간에 민감하다면 DP로 접근하는 것이 바람직합니다.

여기서는 BFS를 연습하기 위해 BFS로 접근해보겠습니다.

이 문제에서 주의해야 하는 점은, 같은 정점에 있다고 해서, 실제 같은 정점이 아니라는 점입니다. 예를 들어, 횟수 등의 조건이 들어가게 되면, 해당 조건으로 인해 이용할 수 있는 간선이 달라지기 때문에 조건이 다른 상황에서의 정점은 같은 정점이라고 할 수 없습니다.

정리하자면, 같은 정점이기 위해서는, 해당 정점에서 이동할 수 있는 간선이 같아야 한다는 것입니다. 그러나 이 문제에서는 클립보드에 들어있는 이모티콘의 개수에 의해 정점마다의 상태가 달라집니다. 따라서 이 문제의 기준은 클립보드에 들어있는 이모티콘의 개수로 정의할 수 있겠습니다.

순서

우선 이 문제에서 정점을 나타내는 요소는 두 가지 입니다. 하나는 정점의 번호, 다른 하나는 현재 클립보드에 들어있는 이모티콘의 개수입니다.

현재 x라는 정점(화면의 이모티콘 개수)에서 클립보드에 c 개의 이모티콘이 있을 때 이동할 수 있는 경우의 수는 총 3가지 입니다.

1. 클립보드에 현재 화면의 이모티콘을 복사하는 경우
   현재 화면에 출력된 개수는 변함이 없으나 클립보드에는 현재 화면에 출력된 이모티콘이 복사됩니다. (D[x][x])
2. 클립보드에서 현재 화면에 이모티콘을 붙여넣는 경우
   현재 화면에 출력된 개수에 추가로 클립보드의 개수만큼이 더해집니다. 클립보드의 개수는 변함이 없습니다. (D[x+c][c])
3. 현재 화면에서 이모티콘을 1개 삭제하는 경우
   말 그대로 현재 화면에 출력된 개수에만 변화가 있습니다. (D[x-1][c])

이 내용을 코드로 나타내면 다음과 같습니다.

코드

package main

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

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

var (
    D [1004][1004]int
)

type pair struct {
    x, c int
}

func main() {
    defer w.Flush()
    S := scanInt()
    for i := range D {
        for j := range D[i] {
            D[i][j] = -1
        }
    }
    D[1][0] = 0
    q := make([]pair, 0)
    q = append(q, pair{1, 0})
    for len(q) != 0 {
        nx, nc := q[0].x, q[0].c
        q = q[1:]
        // clipboard copy
        if D[nx][nx] == -1 {
            D[nx][nx] = D[nx][nc] + 1
            q = append(q, pair{nx, nx})
        }
        // clipboard paste
        if nx+nc < 1004 && D[nx+nc][nc] == -1 {
            D[nx+nc][nc] = D[nx][nc] + 1
            if nx+nc == S {
                fmt.Fprintln(w, D[nx+nc][nc])
                break
            }
            q = append(q, pair{nx + nc, nc})
        }
        // delete
        if 0 <= nx-1 && D[nx-1][nc] == -1 {
            D[nx-1][nc] = D[nx][nc] + 1
            if nx-1 == S {
                fmt.Fprintln(w, D[nx-1][nc])
                break
            }
            q = append(q, pair{nx - 1, nc})
        }
    }
}

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

마무리

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

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