[bfs/백준] 14867번 : 물통

- 문제 : https://www.acmicpc.net/problem/14867

 

문제 이해

- 물통 a, b 가 있는데 몇 가지 방식에 의해 물을 채우고 비울 수 있다.

- 물통에 있는 물을 옮기는 규칙은 다음과 같다.

  1. 한 번에 가득 채우거나, 비울 수 있다.

  2. a -> b, b -> a로 물을 옮길 수 있다.

    a -> b인 상황을 예시로, b에 남은 공간에 따라 a가 줄 수 있는 물의 양은 달라진다.

    b의 남은 공간 > a 물의 양 일 때는 a에 있는 모든 물을 b에 옮길 수 있다.

    b의 남은 공간 < a 물의 양 일 때는 b의 남은 공간만큼만 a에서 옮길 수 있다. 

- 위의 움직임을 모두 bfs로 진행하면 된다. 1차 분기문으로 단순하게 나눠서 진행하면 될거라고 생각했지만, 케이스가 세세하게 생각이 안나서 좀 헤맸다. 

- 물통 비우기, 물통 가득 채우기, 물 옮기기 를 물통 a와 물통 b의 관점에서 생각하고 케이스를 짜면 쉽게 짤 수 있다.

 

풀이 로직

- 물통 a, b의 용량과 목표 용량을 입력 받고 중복 방문하지 않기 위해서 visit를 set으로 설정한다. 

  visit는 일차원 배열로 그 안에 원소가 있는 경우 방문한 것으로 생각한다. 

- while문으로 bfs를 진행하는데, 방문한 노드가 target이라면 answer를 갱신한 뒤 break 한다.

- 아직 target에 도착하지 못했다면 A 물통을 비웠을 때, 가득 채웠을 때, B 물통으로 물을 옮길 때를 분기문으로 작성하고, queue와 visit    처리를 해준다. 마찬가지로 B 물통을 비웠을 때, 가득 채웠을 때, A 물통으로 물을 옮길 때를 분기문으로 작성하고, queue와 visit 처리를    해준다. 

 

정답 풀이 

a, b, target_a, target_b = map(int, input().split())

queue = [[0, 0, 0]] # a에 있는 물의 양, b에 있는 물의 양, 연산횟수
visit = set()
visit.add((0, 0))

answer = -1
while queue:
    x, y, times = queue.pop(0)
    
    if x == target_a and y == target_b:
        answer = times
        break
    
    if (a, y) not in visit:
        visit.add((a, y))
        queue.append([a, y, times + 1])
    if (x, b) not in visit:
        visit.add((x, b))
        queue.append([x, b, times + 1])
    if (0, y) not in visit:
        queue.append([0, y, times + 1])
        visit.add((0, y))
    if (x, 0) not in visit:
        queue.append([x, 0, times + 1])
        visit.add((x, 0))
    
    if x + y >= b:
        if (x - b + y, b) not in visit:
            visit.add((x + y - b, b))
            queue.append([x + y - b, b, times + 1])
    else:
        if (0, x + y) not in visit:
            visit.add((0, x + y))
            queue.append([0, x + y, times + 1])

    if x + y >= a:
        if (a, x + y - a) not in visit:
            queue.append([a, x + y - a, times + 1])
            visit.add((a, x + y - a))
    else:
        if (x + y, 0) not in visit:
            queue.append([x + y, 0, times + 1])
            visit.add((x + y, 0))
            
print(answer)

 

 

참고한 블로그 : https://kingsol.tistory.com/10