땅지원
땅지원's Personal blog
땅지원
전체 방문자
오늘
어제
  • 전체 (353)
    • Frontend (2)
      • React (2)
    • Backend (90)
      • Java (16)
      • Python (19)
      • Spring (23)
      • Database (21)
      • Troubleshooting (8)
    • DevOps (27)
      • ELK (13)
    • CS (40)
    • OS (2)
      • Linux (2)
    • Algorithm (95)
      • concept (18)
      • Algorithm Problem (77)
    • 인공지능 (25)
      • 인공지능 (12)
      • 연구노트 (13)
    • 수업정리 (35)
      • 임베디드 시스템 (10)
      • 데이터통신 (17)
      • Linux (8)
    • 한국정보통신학회 (5)
      • 학술대회 (4)
      • 논문지 (1)
    • 수상기록 (8)
      • 수상기록 (6)
      • 특허 (2)
    • 삼성 청년 SW 아카데미 (6)
    • 42seoul (12)
    • Toy project (3)
    • 땅's 낙서장 (2)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

  • 20.11.6 BB21플러스 온라인 학술대회
  • 20.10.30 한국정보통신학회 온라인 학술대회

인기 글

태그

  • D
  • ㅗ
  • E
  • 이것이 리눅스다 with Rocky Linux9
  • I

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
땅지원

땅지원's Personal blog

백준 2251 물통(BFS)
Algorithm/Algorithm Problem

백준 2251 물통(BFS)

2022. 7. 3. 18:56

https://www.acmicpc.net/problem/2251

 

2251번: 물통

각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부

www.acmicpc.net

물을 옮길 수 있는 방법은 총 6가지이다.

x -> y, x -> z, y -> x, y -> z, z -> x, z -> y : 6가지

 

https://cijbest.tistory.com/14 그림참고

x -> y 라고 한다면 2가지의 경우가 있을 수 있는데

1. x의 담긴 물을 모두 y로 옮긴다

2. x의 담긴 물을 모두 y로 옮기려고 했지만 y의 용량(b)때문에 b-y만 옮기는 경우

 

1,2 case의 min()값을 옮겨주는 물이라고 생각하고 방문처리를 진행해준다.

why?

max값이라고 하면 애초에 말이 안됨. x-water해줘야되는데 음수가 될 수도 있음

water = min(x, b-y)
pour(x - water, y + water)

 

visited[x][y]에 저장을 하면서 중복을 방지해준다.

ex) x->y에 대해서 x,y 물통에 현재 있는 값을 기억해준다.

visited[x][y] => x에 3L, y에 5L 저장되어있다면

visited[3][5] = 1을 해줌으로써 x=3,y=5일 때의 경우를 고려했다라는 것을 체크한다.

 

import sys
from collections import deque

def pour(x, y):
    if not visited[x][y]:
        visited[x][y] = True
        q.append((x, y))

def bfs():

    while q:
        x, y = q.popleft()
        z = c - x - y

        if x == 0:
            answer.append(z)

        water = min(x, b-y)
        pour(x - water, y + water)

        water = min(x, c-z)
        pour(x - water, y)

        water = min(y, a-x)
        pour(x + water, y - water)

        water = min(y, c-z)
        pour(x, y - water)

        water = min(z, a-x)
        pour(x + water, y)

        water = min(z, b-y)
        pour(x, y + water)


a, b, c = map(int, sys.stdin.readline().split())

q = deque()
q.append((0, 0))

visited = [[False] * (b+1) for _ in range(a+1)]
visited[0][0] = True

answer = []

bfs()
answer.sort()
for i in answer:
    print(i, end=" ")

 

'Algorithm > Algorithm Problem' 카테고리의 다른 글

백준 1068 트리(DFS)  (0) 2022.07.10
백준 3079 입국심사(이분탐색)  (0) 2022.07.10
백준 6236 용돈 관리(이분 탐색)  (0) 2022.07.03
백준 10451 순열 사이클(DFS, Union-Find)  (2) 2022.06.27
백준 1326 폴짝폴짝(BFS)  (0) 2022.06.26
    'Algorithm/Algorithm Problem' 카테고리의 다른 글
    • 백준 1068 트리(DFS)
    • 백준 3079 입국심사(이분탐색)
    • 백준 6236 용돈 관리(이분 탐색)
    • 백준 10451 순열 사이클(DFS, Union-Find)
    땅지원
    땅지원
    신입 개발자의 우당탕탕 기술 블로그

    티스토리툴바