[BOJ / Swift & Python] 2251 - 물통

* 개인 블로그에 작성한 내용을 복사해왔습니다. 

[Algorithm] BOJ 2251

BOJ 2251번 물통

2251번: 물통

Intro

BFS를 사용하여 풀이하였습니다. 다른 탐색 문제들에 비해 어떻게 풀이해야 할지 직관적으로 떠오르지 않아, 풀이를 하는 데 조금 시간이 걸렸습니다.

처음에는 방문_여부[물통 A의 물의 양][물통 B의 물의 양][물통 C의 물의 양]으로 표시하여 3차원 배열을 통해 구현하였습니다. 사실 물통 C의 물의 양 = 물통 C의 용량 - 물통 A의 물의 양 - 물통 B의 물의 양이므로 방문_여부[물통 A의 물의 양][물통 B의 물의 양]인 2차원 배열을 통해서도 구현이 가능합니다.

당연히 2차원 배열을 사용한 풀이가 더 효율적이므로, 2차원 배열을 사용한 코드도 구현해 보았습니다.

Solution

*풀이는 더 효율적인 2차원 배열을 기준으로 작성하였습니다.

1. 큐에 (초기 물통 A의 물의 양, 초기 물통 B의 물의 양) 즉 (0, 0)를 넣고 BFS로 탐색한다.
2. 큐의 첫 번째 요소를 꺼낸다.
3. 해당 노드에 방문한 적이 없으면, 해당 노드를 방문했다고 표시하고 해당 노드에서 방문 가능한 노드들을 큐에 추가한다.
   • 물통 N의 물을 물통 M에 붓는 경우
     1. 다 부으면 넘치거나 딱 맞다.
        • 즉, 물통 N의 물의 양 >= 물통 M의 용량 - 물통 M의 물의 양인 경우
        • 큐에 (물통 N의 물의 양 - (물통 M의 용량 - 물통 M의 물의 양), 물통 M의 용량)을 추가한다.
     2. 다 부어도 남는다.
        • 즉, 물통 N의 물의 양 <= 물통 M의 용량 - 물통 M의 물의 양인 경우
        • 큐에 (0, 물통 M의 물의 양 + 물통 N의 물의 양)을 추가한다.
   • 확인해야 할 경우의 수
     1. 물통 A의 물을 물통 B, C에 붓는 경우
     2. 물통 B의 물을 물통 A, C에 붓는 경우
     3. 물통 C의 물을 물통 B, A에 붓는 경우
   위 세 경우를 고려하여 큐에 추가한다.
4. 큐가 빌 때까지 2~3번을 반복한다.
5. 완료되면 0부터 물통 B의 용량까지 for문을 돌며, 표시한 방문 여부 2차원 배열을 통해 A의 물의 양이 0일 때 물통 C에 들어갈 수 있는 값들을 구한다.

Code

Swift

2차원 배열

import Foundation

let input = readLine()!.split(separator: " ").map(){Int(String($0))!}

func bfs(_ A: Int, _ B: Int, _ C: Int) -> [Int] {
    var visit = Array<[Bool]>(repeating: Array<Bool>(repeating: false, count: B+1), count: A+1)
    var queue = [(0, 0)]
    while !queue.isEmpty {
        let node = queue.removeFirst()
        let a = node.0; let b = node.1; let c = C-node.0-node.1
        if visit[a][b] { continue }
        visit[a][b] = true
        if a > 0 {
            if a >= B-b { queue.append((a-B+b, B)) }
            else { queue.append((0, b+a))}
            if a >= C-c { queue.append((a-C+c, b)) }
            else { queue.append((0, b))}
        }
        if b > 0 {
            if b >= A-a { queue.append((A, b-A+a)) }
            else { queue.append((a+b, 0))}
            if b >= C-c { queue.append((a, b-C+c)) }
            else { queue.append((a, 0))}
        }
        if c > 0 {
            if c >= B-b { queue.append((a, B)) }
            else { queue.append((a, b+c))}
            if c >= A-a { queue.append((A, b)) }
            else { queue.append((a+c, b))}
        }
    }
    var result = Set<Int>()
    for b in 0..<B+1 where visit[0][b] { result.insert(C-b) }
    return Array(result).sorted()
}

bfs(input[0], input[1], input[2]).forEach() {print($0, terminator: " ")}

3차원 배열

import Foundation

let input = readLine()!.split(separator: " ").map(){Int(String($0))!}

func bfs(_ A: Int, _ B: Int, _ C: Int) -> [Int] {
    var visit = Array<[[Bool]]>(repeating: Array<[Bool]>(repeating: Array<Bool>(repeating: false, count: C+1), count: B+1),count: A+1)
    var queue = [(0, 0, C)]
    while !queue.isEmpty {
        let node = queue.removeFirst()
        let a = node.0; let b = node.1; let c = node.2
        if visit[a][b][c] { continue }
        visit[a][b][c] = true
        if a > 0 {
            if a >= B-b { queue.append((a-B+b, B, c)) }
            else { queue.append((0, b+a, c))}
            if a >= C-c { queue.append((a-C+c, b, C)) }
            else { queue.append((0, b, c+a))}
        }
        if b > 0 {
            if b >= A-a { queue.append((A, b-A+a, c)) }
            else { queue.append((a+b, 0, c))}
            if b >= C-c { queue.append((a, b-C+c, C)) }
            else { queue.append((a, 0, c+b))}
        }
        if c > 0 {
            if c >= B-b { queue.append((a, B, c-B+b)) }
            else { queue.append((a, b+c, 0))}
            if c >= A-a { queue.append((A, b, c-A+a)) }
            else { queue.append((a+c, b, 0))}
        }
    }
    var result = Set<Int>()
    for b in 0..<B+1 {
        for c in 0..<C+1 where visit[0][b][c] {
            result.insert(c)
        }
    }
    return Array(result).sorted()
}

bfs(input[0], input[1], input[2]).forEach() {print($0, terminator: " ")}

Python

2차원 배열

from collections import deque
import sys
input = sys.stdin.readline

a, b, c = map(int, input().strip().split())
def bfs(a, b, c) :
    v = [[False] * (b+1) for _ in range(a+1)]
    q = deque([(0, 0)])
    while q :
        a1, b1 = q.popleft()
        if v[a1][b1]: continue
        v[a1][b1]= True
        if a1 > 0 :
            if a1 >= b-b1 : q.append((a1-b+b1, b))
            else : q.append((0, b1+a1))
            if a1 >= a1+b1 : q.append((b1, b1))
            else : q.append((0, b1))
        if b1 > 0 :
            if b1 >= a-a1 : q.append((a, b1-a+a1))
            else : q.append((a1+b1, 0))
            if b1 >= a1+b1 : q.append((a1, a1))
            else : q.append((a1, 0))
        if c-a1-b1 > 0 :
            if c-b1 >= a : q.append((a, b1))
            else : q.append((c-b1, b1))
            if c-a1 >= b : q.append((a1, b))
            else : q.append((a1, c-a1))

    result = set()
    for b1 in range(b+1) :
        if v[0][b1] : result.add(c-b1)
    return sorted(list(result))
[print(r, end=' ') for r in bfs(a,b,c)]

3차원 배열

from collections import deque
import sys
input = sys.stdin.readline

a, b, c = map(int, input().strip().split())
def bfs(a, b, c) :
    v = [[[False] * (c+1) for _ in range(b+1)] for _ in range(a+1)]
    q = deque([(0, 0, c)])
    while q :
        a1, b1, c1 = q.popleft()
        if v[a1][b1][c1]: continue
        v[a1][b1][c1]= True
        if a1 > 0 :
            if a1 >= b-b1 : q.append((a1-b+b1, b, c1))
            else : q.append((0, b1+a1, c1))
            if a1 >= c-c1 : q.append((a1-c+c1, b1, c))
            else : q.append((0, b1, c1+a1))
        if b1 > 0 :
            if b1 >= a-a1 : q.append((a, b1-a+a1, c1))
            else : q.append((a1+b1, 0, c1))
            if b1 >= c-c1 : q.append((a1, b1-c+c1, c))
            else : q.append((a1, 0, c1+b1))
        if c-a1-b1 > 0 :
            if c1 >= a-a1 : q.append((a, b1, c1-a+a1))
            else : q.append((a1+c1, b1, 0))
            if c1 >= b-b1 : q.append((a1, b, c1-b+b1))
            else : q.append((a1, b1+c1, 0))

    result = set()
    for b1 in range(b+1) :
        for c1 in range(c+1) :
            if v[0][b1][c1] : result.add(c1)
    return sorted(list(result))
[print(r, end=' ') for r in bfs(a,b,c)]