ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 2251 물통
    알고리즘/백준 2019. 3. 12. 09:03

    1. 문제



    2. 코드


    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    #include "pch.h"
    #include <stdio.h>
    #include <queue>
    #define _CRT_SECURE_NO_WARNINGS
    using namespace std;
     
    struct water
    {
        int a, b, c;
    };
     
    int A, B, C;
    bool visit[202][202], ans[202];
     
    int main()
    {
        scanf("%d %d %d"&A, &B, &C);
        queue<water> q;
        q.push({ 0,0,C });
        while (!q.empty())
        {
            water cur = q.front();
            q.pop();
     
            if (visit[cur.a][cur.b])
                continue;
     
            visit[cur.a][cur.b] = true;
     
            if (cur.a == 0)
                ans[cur.c] = true;
     
            //a->b
            if (cur.a + cur.b > B)
                q.push({ cur.a + cur.b - B,B,cur.c });
            else
                q.push({ 0,cur.a + cur.b,cur.c });
     
            //a->c
            if (cur.a + cur.c > C )
                q.push({ cur.a + cur.c - C,cur.b,C });
            else
                q.push({ 0, cur.b, cur.a + cur.c });
     
            //b->a
            if (cur.b + cur.a > A )
                q.push({ A,cur.b + cur.a - A,cur.c });
            else
                q.push({ cur.b + cur.a,0,cur.c });
     
            //b->c
            if (cur.b + cur.c > C )
                q.push({ cur.a,cur.b + cur.c - C,C });
            else
                q.push({ cur.a,0,cur.c + cur.b });
     
            //c->a
            if (cur.c + cur.a > A)
                q.push({ A,cur.b,cur.c + cur.a - A });
            else
                q.push({ cur.c + cur.a,cur.b,0 });
     
            //c->b
            if (cur.c + cur.b > B)
                q.push({ cur.a,B,cur.c + cur.b - B });
            else
                q.push({ cur.a,cur.b + cur.c,0 });
        }
     
        for (int i = 0; i < 202; i++) {
            if (ans[i])
                printf("%d ", i);
        }
    }
     
    cs


    3. 후기

    내가 이문제를 풀었을 때는 메모리가 이 코드의 몇십배였다. 방문검사를 일단 넣고나서 하며, q.push()에 한 줄로 원하는 값을 넣을 수 있어서 값을 저장할 필요가 없다. 나는 값을 저장할 임시 배열을 만들어서 하고 방문검사를 할 때 굳이 a,b,c다 검사를 했다. 생각해보면 셋 중에 두개만 검사를 해도 상관이 없다. 

    '알고리즘 > 백준' 카테고리의 다른 글

    9376 탈옥  (0) 2019.03.14
    12851 숨바꼭질 2 -BFS  (0) 2019.03.12
    1525 퍼즐  (0) 2019.03.12
    9019 DSLR  (0) 2019.03.11
    7453 합이 0인 네 정수  (0) 2019.03.10
Designed by Tistory.