IT-garden

문제

각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다.

이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. 첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 모두 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 세 정수 A, B, C가 주어진다.

출력

첫째 줄에 공백으로 구분하여 답을 출력한다. 각 용량은 오름차순으로 정렬한다.

예제 입력과 출력

알고리즘 분류

BFS

정답

from collections import deque
import sys
input= lambda : sys.stdin.readline().strip()

def cou(s1,s2):
    if ch[s1][s2] != 1:
        ch[s1][s2] = 1
        de.append([s1,s2])

def bfs():
    de.append([0,0])
    ch[0][0]=1

    while de:
        a1,b1=de.popleft()
        c1 =c-a1-b1
        
        if a1 == 0:
            r.append(c1)

        if b1+a1 < b: # a를 b로
            cou(0, b1+a1)
        else:
            cou(a1-(b-b1), b)

        if c1+a1 < c: # a를 c로
            cou(0, b1)
        else:
            cou(a1-(c-c1), b1)

        if a1+b1 < a: # b를 a로
            cou(a1+b1, 0)
        else:
            cou(a, b1-(a-a1))

        if c1+b1 < c: # b를 c로
            cou(a1, 0)
        else:
            cou(a1, b1-(c-c1))

        if a1+c1 < a: # c를 a로
            cou(a1+c1,b1)
        else:
            cou(a, b1)

        if b1+c1 < b: # c를 b로
            cou(a1, c1+b1)
        else:
            cou(a1, b)

a,b,c=map(int,input().split())
ch=[[0]*201 for i in range(201)]
r=[]
de=deque()

bfs()
r.sort()

print(' '.join(map(str,r)))

처음 c에만 물이 있고 a와 b에는 물이 없기 때문에 (0, 0)에서 bfs를 시작합니다.
큐에 넣거나 체크를 할 때 a와 b의 값으로 비교를 합니다.
c의 값은 c에서 a와 b에 있는 물의 값을 빼는 것을 통해 구할 수 있기 때문에 따로 배열에 넣지 않았습니다.

물을 옮길 수 있는 방법은 6가지입니다.
a→b, a→c, b→a, b→c, c→a, c→b

각각의 경우에 물을 옮길 수 있다면 중복체크를 하고 옮기고 첫 번째 물통 a가 비어있으면 리스트 r에 c에 있는 물의 양을 저장합니다.

bfs 완료 후 리스트 r에 있는 값들을 오름차순으로 정렬해서 출력합니다.

백준 알고리즘 2251번 : https://www.acmicpc.net/problem/2251

문제

3×3 표에 다음과 같이 수가 채워져 있다. 오른쪽 아래 가장 끝 칸은 비어 있는 칸이다.

어떤 수와 인접해 있는 네 개의 칸 중에 하나가 비어 있으면, 수를 그 칸으로 이동시킬 수가 있다. 물론 표 바깥으로 나가는 경우는 불가능하다. 우리의 목표는 초기 상태가 주어졌을 때, 최소의 이동으로 위와 같은 정리된 상태를 만드는 것이다. 다음의 예를 보자.

가장 윗 상태에서 세 번의 이동을 통해 정리된 상태를 만들 수 있다. 이와 같이 최소 이동 횟수를 구하는 프로그램을 작성하시오.

입력

세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다.

출력

첫째 줄에 최소의 이동 횟수를 출력한다. 이동이 불가능한 경우 -1을 출력한다.

예제 입력과 출력

정답

from collections import deque
import sys
input= lambda : sys.stdin.readline().strip()

def bfs():
    de=deque()
    de.append(aa)
    dist[aa] = 0
    
    while de:
        d = de.popleft()
        if d == 123456789:
            return dist[d]
        
        s = str(d)
        k = s.find('9')
        x, y = k//3, k%3 # 3X3표일 때 x,y 좌표
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0 <= nx < 3 and 0 <= ny < 3:
                nk = nx*3 + ny # 3x3 표에서 x,y 좌표를 리스트로 바꿨을때의 위치
                ns = list(s)
                ns[k], ns[nk] = ns[nk], ns[k]
                nd = int(''.join(ns))
                
                if not dist.get(nd): 
                    dist[nd] = dist[d]+1
                    de.append(nd)
                    
    return -1

dx=[1,-1,0,0]
dy=[0,0,1,-1]

dist = dict()
aa=''

for i in range(3):
    a=input()
    a=a.replace(' ','')
    aa += a

aa=int(aa.replace('0','9'))

print(bfs())

1. 3x3 표를 하나의 문자열로 생각합니다. 이때 0은 9로 바꿉니다.
2. 딕셔너리를 통해 키는 퍼즐 형태, 값은 퍼즐 이동 수로 표현합니다.

3. bfs를 통해 문자열에서 9의 위치를 기준으로 위, 아래, 왼쪽, 오른쪽으로 옮깁니다.
4. 옮기면서 이동 수를 하나씩 늘리고 문자열이 123456789가 나오면 이동 수를 출력하고 큐에 남은 값이 없을 때까지 123456789가 나오지 않으면 -1을 출력합니다.

백준 알고리즘 1525번 : https://www.acmicpc.net/problem/1525

문제

네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다. n의 네 자릿수를 d1, d2, d3, d4라고 하자(즉 n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4라고 하자)

1. D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. 그 결과 값(2n mod 10000)을 레지스터에 저장한다.
2. S: S 는 n에서 1 을 뺀 결과 n-1을 레지스터에 저장한다. n이 0 이라면 9999 가 대신 레지스터에 저장된다.
3. L: L 은 n의 각 자릿수를 왼편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d2, d3, d4, d1이 된다.
4. R: R 은 n의 각 자릿수를 오른편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d4, d1, d2, d3이 된다.

위에서 언급한 것처럼, L 과 R 명령어는 십진 자릿수를 가정하고 연산을 수행한다. 예를 들어서 n = 1234 라면 여기에 L 을 적용하면 2341 이 되고 R 을 적용하면 4123 이 된다.

여러분이 작성할 프로그램은 주어진 서로 다른 두 정수 A와 B(A ≠ B)에 대하여 A를 B로 바꾸는 최소한의 명령어를 생성하는 프로그램이다. 예를 들어서 A = 1234, B = 3412 라면 다음과 같이 두 개의 명령어를 적용하면 A를 B로 변환할 수 있다.

1234 →L 2341 →L 3412
1234 →R 4123 →R 3412

따라서 여러분의 프로그램은 이 경우에 LL 이나 RR 을 출력해야 한다.

n의 자릿수로 0 이 포함된 경우에 주의해야 한다. 예를 들어서 1000 에 L 을 적용하면 0001 이 되므로 결과는 1 이 된다. 그러나 R 을 적용하면 0100 이 되므로 결과는 100 이 된다.

입력

프로그램 입력은 T 개의 테스트 케이스로 구성된다. 테스트 케이스 개수 T 는 입력의 첫 줄에 주어진다. 각 테스트 케이스로는 두 개의 정수 A와 B(A ≠ B)가 공백으로 분리되어 차례로 주어지는데 A는 레지스터의 초기 값을 나타내고 B는 최종 값을 나타낸다. A 와 B는 모두 0 이상 10,000 미만이다.

출력

A에서 B로 변환하기 위해 필요한 최소한의 명령어 나열을 출력한다.

예제 입력과 출력

알고리즘 분류

BFS

정답

from collections import deque
import sys
input= lambda : sys.stdin.readline().strip()

t=int(input())

def bfs(n):
    de=deque()
    de.append(n)
    ch=[-1]*10000
    ch[n]=''
    
    while de:
        x=de.popleft()

        if x == b:
            return ch[b]
    
        no,nx=divmod(2*x, 10000) #D
        if ch[nx] == -1:
            ch[nx]=ch[x]+'D'
            de.append(nx)
        
        if x == 0: #S
            nx = 9999
        else:
            nx=x-1
        
        if ch[nx] == -1:
            ch[nx]=ch[x]+'S'
            de.append(nx)
        
        nx=(x%1000)*10 + x//1000 #L
        if ch[nx] == -1:
            ch[nx]=ch[x]+'L'
            de.append(nx)
        
        nx=(x%10)*1000 + x//10 #R
        if ch[nx] == -1:
            ch[nx]=ch[x]+'R'
            de.append(nx)

while t:
    t -= 1
    a,b=map(int,input().split())
    print(bfs(a))

파이썬 시간초과로 PyPy3로 제출했습니다.

문제가 많이 어렵진 않았지만 L과 R에 해당하는 계산식을 생각하느라 시간을 많이 사용했습니다.
수학적 계산을 많이 사용해봐야겠다고 생각했습니다.

배열 ch에 이전 이동 방향을 넣고 각각 해당하는 D, S, L, R을 넣어주고 b가 되는 순간 출력했습니다.

백준 알고리즘 9019번 : https://www.acmicpc.net/problem/9019

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력한다.

예제 입력과 출력

정답

from collections import deque
import sys
input= lambda : sys.stdin.readline().strip()

n,k=map(int,input().split())
ch=[[-1,-1] for i in range(100002)]

def bfs(s):
    de=deque()
    de.append(s)
    ch[s][0]=0

    while de:
        x=de.popleft()
        
        if x == k:
            return ch[k][0]

        for i in (x*2,x+1,x-1):
            if 0 <= i < 100001:
                if ch[i][0] == -1:
                    ch[i][0]=ch[x][0]+1
                    ch[i][1]=x # 이전에 방문했던 곳
                    de.append(i)

print(bfs(n)) # 가장 빠른 시간

li=deque()
li.append(k)

while True: # 어떻게 이동했는지 추적
    if ch[k][1] != -1:
        li.appendleft(ch[k][1])
        k=ch[k][1]
    else:
        break

print(' '.join(map(str,li)))

ch배열을 2차로 잡습니다.
ch[i][0]은 해당 지점에 가는데 걸린 시간이고 ch[i][1]은 이전에 방문했던 지점을 표시합니다.

ch[i][1]을 통해 끝에서부터 추적해서 어떻게 이동했는지 출력합니다.

백준알고리즘 - 1697번 숨바꼭질 - 파이썬(Python)

백준알고리즘 - 13549번 숨바꼭질 3 - 파이썬(Python)

위 두문제의 응용문제입니다.

백준 알고리즘 13913번 : https://www.acmicpc.net/problem/13913

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

예제 입력과 출력

정답

from collections import deque
import sys
input = lambda :sys.stdin.readline().strip()

n,k=map(int,input().split())
ch=[-1]*100001

def bfs():
    de=deque()
    de.append(n)
    ch[n] = 0

    while de:
        x=de.popleft()

        if x == k:
            return ch[k]

        if 0 <= x*2 < 100001 and ch[x*2] == -1:
            ch[x*2] = ch[x]
            de.append(x*2)
        
        for i in (x-1,x+1):
            if 0 <= i < 100001 and ch[i] == -1:
                ch[i] = ch[x]+1
                de.append(i)

print(bfs())

1697 숨바꼭질 문제에서 조금 변형된 문제입니다.

백준 알고리즘 13549번 : https://www.acmicpc.net/problem/13549

문제

영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다.

영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만들어 보려고 한다.

1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
3. 화면에 있는 이모티콘 중 하나를 삭제한다.

모든 연산은 1초가 걸린다. 또, 클립보드에 이모티콘을 복사하면 이전에 클립보드에 있던 내용은 덮어쓰기가 된다. 클립보드가 비어있는 상태에는 붙여넣기를 할 수 없으며, 일부만 클립보드에 복사할 수는 없다. 또한, 클립보드에 있는 이모티콘 중 일부를 삭제할 수 없다. 화면에 이모티콘을 붙여넣기 하면, 클립보드에 있는 이모티콘의 개수가 화면에 추가된다.

영선이가 S개의 이모티콘을 화면에 만드는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 S (2 ≤ S ≤ 1000) 가 주어진다.

출력

첫째 줄에 이모티콘을 S개 만들기 위해 필요한 시간의 최솟값을 출력한다.

예제 입력과 출력

정답

from collections import deque
import sys
input = lambda :sys.stdin.readline().strip()

s=int(input())
ch=[[-1]*(s+1) for i in range(s+1)]

def bfs():
    de=deque()
    de.append([1,0])
    ch[1][0]=0

    while de:
        x,y=de.popleft()

        if ch[x][x] == -1: # 1번 연산
            ch[x][x] = ch[x][y]+1
            de.append([x,x])
        if x+y <= s and ch[x+y][y] == -1 : # 2번 연산
            ch[x+y][y] = ch[x][y]+1
            de.append([x+y,y])
        if x-1 >=0 and ch[x-1][y] == -1: # 3번 연산
            ch[x-1][y] = ch[x][y]+1
            de.append([x-1,y])
            
bfs()

r=ch[s][1]
for i in range(1,s):
    if ch[s][i] != -1:
        r=min(r,ch[s][i])
print(r)

이모티콘 1개에서 s개까지의 이모티콘을 화면에 만드는데 걸리는 최소 시간을 구하는 문제입니다.
bfs를 이용해 문제를 푸는데 ch를 이차원 배열로 만듭니다.

ch[화면에 나온 이모티콘 개수][클립보드의 이모티콘 개수]

bfs에서 1, 2, 3번 각각 연산의 경우를 실행합니다.
화면에 나온 이모티콘은 s개이고 클립보드의 이모티콘이 1부터 s-1개일때까지의 값을 비교해 가장 작은 값(최소 시간)을 출력합니다.

백준 알고리즘 14226번 : https://www.acmicpc.net/problem/14226