Intro
BFS를 사용하여 풀이하였습니다. 다른 탐색 문제들에 비해 어떻게 풀이해야 할지 직관적으로 떠오르지 않아, 풀이를 하는 데 조금 시간이 걸렸습니다.
처음에는 방문_여부[물통 A의 물의 양][물통 B의 물의 양][물통 C의 물의 양]으로 표시하여 3차원 배열을 통해 구현하였습니다. 사실 물통 C의 물의 양 = 물통 C의 용량 - 물통 A의 물의 양 - 물통 B의 물의 양이므로 방문_여부[물통 A의 물의 양][물통 B의 물의 양]인 2차원 배열을 통해서도 구현이 가능합니다.
당연히 2차원 배열을 사용한 풀이가 더 효율적이므로, 2차원 배열을 사용한 코드도 구현해 보았습니다.
Solution
*풀이는 더 효율적인 2차원 배열을 기준으로 작성하였습니다.
-
큐에
(초기 물통 A의 물의 양, 초기 물통 B의 물의 양)즉(0, 0)를 넣고 BFS로 탐색한다. -
큐의 첫 번째 요소를 꺼낸다.
-
해당 노드에 방문한 적이 없으면, 해당 노드를 방문했다고 표시하고 해당 노드에서 방문 가능한 노드들을 큐에 추가한다.
- 물통 N의 물을 물통 M에 붓는 경우
- 다 부으면 넘치거나 딱 맞다.
- 즉,
물통 N의 물의 양 >= 물통 M의 용량 - 물통 M의 물의 양인 경우 - 큐에
(물통 N의 물의 양 - (물통 M의 용량 - 물통 M의 물의 양), 물통 M의 용량)을 추가한다.
- 즉,
- 다 부어도 남는다.
- 즉,
물통 N의 물의 양 <= 물통 M의 용량 - 물통 M의 물의 양인 경우 - 큐에
(0, 물통 M의 물의 양 + 물통 N의 물의 양)을 추가한다.
- 즉,
- 다 부으면 넘치거나 딱 맞다.
- 확인해야 할 경우의 수
- 물통 A의 물을 물통 B, C에 붓는 경우
- 물통 B의 물을 물통 A, C에 붓는 경우
- 물통 C의 물을 물통 B, A에 붓는 경우
위 세 경우를 고려하여 큐에 추가한다.
- 물통 N의 물을 물통 M에 붓는 경우
-
큐가 빌 때까지 2~3번을 반복한다.
-
완료되면 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)]
iOS / 🌊