[BOJ/12886/Golang] 백준 12886 - 돌 그룹

문제로 이동하기

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

여담

Gold 5 문제입니다. BFS에는 나름 자신감이 붙게 만들어준 문제입니다. 이제는 Gold도 두렵지 않다..! 뭐 이런거죠 ㅋㅋㅋ.. 사실 흔한 BFS 문제들과 비슷한 패턴으로 풀리는 문제라서.. 크게 어렵진 않습니다.

접근 방식

우선 상황에 대한 정리가 필요합니다. 현재 주어진 정점은 무엇이고, 가고자 하는 정점은 무엇인지 알아야 합니다. 그리고 현재 주어진 정점에서 이동할 수 있는 방법의 수, 다시 말해 간선의 종류는 어떻게 되는지 정리해볼 필요가 있습니다.

현재 주어진 정점

현재 주어진 정점은 당연하게도 (A, B, C) 입니다.

가고자 하는 정점

모든 그룹에 있는 돌의 개수를 같게 만드는 상황이 목표입니다. 따라서 돌의 개수를 조작해서 모든 그룹의 돌의 개수가 같아지면 됩니다. 정점을 정리해보면 (A+B+C/3, A+B+C/3, A+B+C/3) (단, (A+B+C)%3 == 0) 로 정리할 수 있겠습니다.

갈 수 있는 방법의 종류

문제에서 주어진대로, 크기가 같지 않은 두 그룹을 골라 조작할 수 있습니다. 3개 중에 순서에 관계 없이 2개를 고르는 방법은 3가지가 있습니다. (A, B), (A, C), (B, C)

이 때, 각 그룹의 개수에 따라서 상황이 각각 두 개씩 만들어집니다. 따라서 한 정점에서 이동할 수 있는 방법의 수는 3개이고, 방향까지 고려하면 총 6개가 됩니다.

A, B를 고른 경우

A와 B를 골랐을 때를 가정해보겠습니다. A > B 라면, 다음 정점은 (A-B, B+B, C) 입니다.

만약 반대의 경우라면, (A+A, B-A, C) 가 되겠죠?

A, C를 고른 경우

위와 같은 방식으로 정리해보면 다음과 같습니다.

• A < C → (A+A, B, C-A)
• A > C → (A-C, B, C+C)

B, C를 고른 경우

• B < C → (A, B+B, C-B)
• B > C → (A, B-C, C+C)

고려해볼만한 점

처음에 문제를 풀 때는 정점을 3개의 좌표로 표현했습니다. 하지만 이내 그렇게 할 필요가 없다는 생각이 들더라구요. A와 B만 알고 있다면 C의 개수는 자동으로 구해지기 때문입니다. 이유는 A+B+C가 항상 일정하기 때문입니다. 따라서 공간 복잡도를 낮추기 위해 C를 제외하고 코드를 구현했습니다. 나머지는 코드를 참조해주세요!

아참! 그리고 만약에 A+B+C가 3으로 나누어 떨어지지 않는다면, 구해볼 필요도 없이 답은 0입니다. 세 개의 그룹으로 쪼개야 하는데, 3으로 나눠지지 않는다면 당연하게도 같은 개수로 만들 수 없기 때문입니다.

코드

package main

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

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

type pair struct {
    x, y int
}

var (
    A, B, C, M, S int
    D             [][]bool
)

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

func main() {
    defer w.Flush()
    A, B, C = scanInt(), scanInt(), scanInt()
    S = A + B + C
    if S%3 != 0 {
        fmt.Fprintln(w, 0)
        return
    }
    M = S / 3
    D = make([][]bool, S+1)
    for i := range D {
        D[i] = make([]bool, S+1)
    }
    q := make([]pair, 0)
    D[A][B] = true
    q = append(q, pair{A, B})
    for len(q) != 0 {
        nx, ny := q[0].x, q[0].y
        q = q[1:]
        // nx, ny
        if nx < ny {
            // nx+nx, ny-nx, nz
            if !D[nx+nx][ny-nx] {
                D[nx+nx][ny-nx] = true
                q = append(q, pair{nx + nx, ny - nx})
            }
        } else {
            // nx-ny, ny+ny, nz
            if !D[nx-ny][ny+ny] {
                D[nx-ny][ny+ny] = true
                q = append(q, pair{nx - ny, ny + ny})
            }
        }
        // nx, nz
        if nx < S-(nx+ny) {
            // nx+nx, ny, nz-nx
            if !D[nx+nx][ny] {
                D[nx+nx][ny] = true
                q = append(q, pair{nx + nx, ny})
            }
        } else {
            // nx-nz, ny, nz+nz
            if !D[nx-S+(nx+ny)][ny] {
                D[nx-S+(nx+ny)][ny] = true
                q = append(q, pair{nx - S + (nx + ny), ny})
            }
        }
        // ny, nz
        if ny < S-(nx+ny) {
            // nx, ny+ny, nz-ny
            if !D[nx][ny+ny] {
                D[nx][ny+ny] = true
                q = append(q, pair{nx, ny + ny})
            }
        } else {
            // nx, ny-nz, nz+nz
            if !D[nx][ny-S+(nx+ny)] {
                D[nx][ny-S+(nx+ny)] = true
                q = append(q, pair{nx, ny - S + (nx + ny)})
            }
        }
        if D[M][M] {
            break
        }
    }
    if D[M][M] {
        fmt.Fprintln(w, 1)
    } else {
        fmt.Fprintln(w, 0)
    }
}

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

마무리

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

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