[BOJ] 백준 14867 물통

출처: www.acmicpc.net/problem/14867

Approach

BFS (Breadth-First Search, 너비 우선 탐색) 이용

BFS (Breadth-First Search, 너비 우선 탐색)

DFS와 BFS 비교

DFS와 BFS 비교

 

---

#include <stdio.h>
const int MAX_N = 100005;
int A, B, ta, tb;
int visited[4][MAX_N];
int fr, re;

struct Data {
    int a, b, lev;
}que[MAX_N * 4];

void push(int na, int nb, int nl) {
    int r = 3, c = na;
    if (na == 0) r = 0, c = nb;
    else if (na == A) r = 1, c = nb;
    else if (nb == 0) r = 2, c = na;
    if (visited[r][c]) return;
    visited[r][c] = 1;
    que[re++] = { na, nb, nl };
}

int BFS() {
    push(0, 0, 0);
    Data t;

    while (fr < re) {
        t = que[fr++];
        if (t.a == ta && t.b == tb) return t.lev;
        push(0, t.b, t.lev + 1); // A 물통 비우기
        push(A, t.b, t.lev + 1); // A 물통 가득 채우기
        push(t.a, 0, t.lev + 1); // B 물통 비우기
        push(t.a, B, t.lev + 1); // B 물통 가득 채우기
        
        // B 물통의 물을 A에 붓기
        if (t.a + t.b < A)
            push(t.a + t.b, 0, t.lev + 1);
        else
            push(A, t.a + t.b - A, t.lev + 1);
        
        // A 물통의 물을 B에 붓기
        if (t.a + t.b < B)
            push(0, t.a + t.b, t.lev + 1);
        else
            push(t.a + t.b - B, B, t.lev + 1);
    }
    return -1;
}

int main() {
    // freopen("input.txt", "r", stdin);
    scanf("%d %d %d %d", &A, &B, &ta, &tb);
    printf("%d\n", BFS());
}