백준 - 물통 (2251)

let sender = [0, 0, 1, 1, 2, 2]
let receiver = [1, 2, 0, 2, 0, 1]

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

var visited = Array(repeating: Array(repeating: false, count: 201), count: 201)
var queue = Queue<[Int]>()
var answer = [size[2]]
var answerString = ""

bfs(0, 0)
answer.sorted().forEach { answerString += "\($0) " }
print(answerString)

func bfs(_ a: Int, _ b: Int) {
    visited[a][b] = true
    queue.enqueue([a, b])
    
    while !queue.isEmpty {
        let now = queue.delete()
        let A = now[0]
        let B = now[1]
        let C = size[2] - (now[0] + now[1])
        
        for i in 0..<6 {
            var next = [A, B, C]
            next[receiver[i]] += next[sender[i]]
            next[sender[i]] = 0
            if next[receiver[i]] > size[receiver[i]] { // 물이 넘치는 경우
                next[sender[i]] += next[receiver[i]] - size[receiver[i]]
                next[receiver[i]] = size[receiver[i]]
            }
            if !visited[next[0]][next[1]] {
                visited[next[0]][next[1]] = true
                queue.enqueue([next[0], next[1]])
                if next[0] == 0 {
                    answer.append(next[2])
                }
            }
        }
    }
}

• BFS 알고리즘을 사용해서 현재 물통의 상태에서 물통의 물을 옮겨 담는 모든 경우(A→B, A→C, B→A, B→C, C→A, C→B)를 확인한다.
• 주의할 점
  • 물의 총량이 항상 똑같기 때문에 물통 A, B의 용량만 저장해도 C의 용량을 쉽게 구할 수 있다.
  • A, B가 비어 있는 상태에서 BFS 알고리즘을 실행한다.
  • 방문하지 않은 노드만 큐에 추가한다.
    • = 이전에 보았던 물통 상태는 더이상 확인하지 않는다.