IT-garden

문제

상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다.

평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타나 있다. 감옥은 무인 감옥으로 죄수 두 명이 감옥에 있는 유일한 사람이다.

문은 중앙 제어실에서만 열 수 있다. 상근이는 특별한 기술을 이용해 제어실을 통하지 않고 문을 열려고 한다. 하지만, 문을 열려면 시간이 매우 많이 걸린다. 두 죄수를 탈옥시키기 위해서 열어야 하는 문의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다.

첫째 줄에는 평면도의 높이 h와 너비 w가 주어진다. (2 ≤ h, w ≤ 100) 다음 h개 줄에는 감옥의 평면도 정보가 주어지며, 빈 공간은 '.', 지나갈 수 없는 벽은 '*', 문은 '#', 죄수의 위치는 '$'이다.

상근이는 감옥 밖을 자유롭게 이동할 수 있고, 평면도에 표시된 죄수의 수는 항상 두 명이다. 각 죄수와 감옥의 바깥을 연결하는 경로가 항상 존재하는 경우만 입력으로 주어진다.

출력

각 테스트 케이스마다 두 죄수를 탈옥시키기 위해서 열어야 하는 문의 최솟값을 출력한다.

예제 입력과 출력

알고리즘 분류

BFS

정답

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

t=int(input())

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

def bfs(s1,s2):
    ch=[[-1]*(w+2) for i in range(h+2)]
    de=deque()
    de.append([s1,s2])
    ch[s1][s2]=0

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

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < h+2 and 0 <= ny < w+2:
                if ch[nx][ny] == -1:
                    if a[nx][ny] == '.' or a[nx][ny] == '$':
                        ch[nx][ny] = ch[x][y]
                        de.appendleft([nx,ny])
                        
                    if a[nx][ny] == '#':
                        ch[nx][ny] = ch[x][y] +1
                        de.append([nx,ny])
    return ch

while t:
    t -= 1
    h,w=map(int,input().split()) 

    a=[list('.'*(w+2))]
    for i in range(h):
        a.append(list('.'+input().strip()+'.'))
    a.append(list('.'*(w+2)))
    
    s=[]
    for i in range(h+2):
        for j in range(w+2):
            if a[i][j] == '$': # 죄수
                s.append([i,j])
    
    one=bfs(s[0][0],s[0][1])
    two=bfs(s[1][0],s[1][1])
    three=bfs(0,0)
    m=sys.maxsize
    
    for i in range(h+2):
        for j in range(w+2):
            r=one[i][j]+two[i][j]+three[i][j]

            if a[i][j] == '*':
                continue
            if a[i][j] == '#':
                r -= 2
            m=min(m,r)

    print(m)

이 문제에서 중요한 것은 문제에서 주어진 평면도에서 가로, 세로의 가장자리를 확대해서 답을 구한다는 것입니다.
가로, 세로를 확대해도 괜찮은 이유는 확대한 곳에는 문이 없기 때문에 따로 열어야 하는 문의 개수가 올라가지 않기 때문입니다.

one : 첫 번째 죄수가 출발해서 문을 여는 경우
two : 두 번째 죄수가 출발해서 문을 여는 경우
three : 밖에서 출발해서 문을 여는 경우

3가지 경우에 bfs를 통해 ch에 열어야 하는 문의 개수를 저장하고 리턴합니다.
bfs 과정에서 통과하려는 곳이 '.'인 경우 먼저 방문할 수 있게 appendleft를 이용합니다.

평면도의 각 위치에 대한 열어야 하는 문의 개수를 비교합니다.
위치가 '#'인 경우는 3명이 모두 문을 열었기 때문에 한명만 열면 모두 통과할 수 있기 때문에 -2를 합니다.
그 후 최소값을 구하여 출력합니다.

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

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 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()

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

    while de:
        x=de.popleft()
        
        for i in (x+1,x-1,x*2):
            if 0 <= i < 100001:
                if ch[i][0] == -1: # 처음 들르는 경우
                    ch[i][0]=ch[x][0]+1
                    ch[i][1]=ch[x][1]
                    de.append(i)
                    
                elif ch[i][0] == ch[x][0]+1: # 한번 이상 들르는 경우 
                    ch[i][1] += ch[x][1] # 방법 더하기
            
n,k=map(int,input().split())
ch=[[-1,0] for i in range(100001)]

bfs(n)
print(ch[k][0])
print(ch[k][1])

ch[i][0]은 가장 빠른 시간을 나타내고 ch[i][1]은 방법의 수를 나타냅니다.

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

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

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

위 세문제는 관련문제입니다.

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

문제

각각 부피가 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

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다.

• 1+1+1+1
• 2+1+1 (1+1+2, 1+2+1)
• 2+2
• 1+3 (3+1)

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 10,000보다 작거나 같다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

예제 입력과 출력

정답

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

t=int(input())
dp=[[0,0,0,0] for i in range(10001)]

dp[1][1]=1

dp[2][1]=1
dp[2][2]=1

dp[3][1]=1
dp[3][2]=1
dp[3][3]=1

for i in range(4,10001):
    dp[i][1] = dp[i-1][1]
    dp[i][2] = dp[i-2][1] + dp[i-2][2]
    dp[i][3] = dp[i-3][1] + dp[i-3][2] + dp[i-3][3]

while t:
    t -= 1
    print(sum(dp[int(input())]))

dp[i][1] : 끝의 자리가 1인 경우의 수
dp[i][2] : 끝의 자리가 2인 경우의 수
dp[i][3] : 끝의 자리가 3인 경우의 수

dp[i][1]은 dp[i-1][1] 뒤에 1을 추가합니다.
dp[i][2]은 dp[i-2][1], dp[i-2][2] 뒤에 2을 추가합니다.
dp[i][3]은 dp[i-3][1], dp[i-3][2], dp[i-3][3] 뒤에 3을 추가합니다.

백준알고리즘 - 9095번 1, 2, 3 더하기 - 파이썬(Python)

백준알고리즘 - 15988번 1, 2, 3 더하기 3 - 파이썬(Python)

백준알고리즘 - 15990번 1, 2, 3 더하기 5 - 파이썬(Python)

위 세문제와 관련 있는 문제입니다.

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

문제

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

입력

첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.

출력

첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.

예제 입력과 출력

알고리즘 분류

다이나믹 프로그래밍 

정답

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

n,k=map(int,input().split())

dp=[[0]*201 for i in range(201)]

for i in range(201):
    dp[1][i]=1
    dp[2][i]=i+1

for i in range(2,201):
    dp[i][1]=i
    for j in range(2,201):
        dp[i][j]=(dp[i][j-1]+dp[i-1][j] )% 1000000000

print(dp[k][n])

n과 k의 관계에 대해 생각해보았습니다.

k에 상관없이 n이 1인 경우에 합이 n이 되는 경우의 수는 k개입니다.

ex) k = 2 이고 n = 1 이면 (0, 1) (1, 0) 2개

ex) k = 4 이고 n = 1 이면 (0, 0, 0, 1) (0, 0, 1, 0) (0, 1, 0, 0) (1, 0, 0, 0) 4개

k = 1 이면 n에 상관없이 합이 n이 되는 경우의 수는 1개입니다. (n 자신 1개)

k = 2 이면

위의 예제에서처럼 n = 20 이면 21개입니다.

(10,10) 1개와

(0, 20) (1, 19) (2, 18) (3, 17) (4, 16) (5, 15) (6, 14) (7, 13) (8, 12) (9, 11) 10가지를 순서 바뀐 경우로 20가지

20 + 1 = 21

n = 3 이면 (3, 0) (1, 2) 2가지를 순서 바뀐 경우로 4가지, 총 4가지입니다.

이를 통해 k = 2 이면 합이 n이 되는 경우의 수는 n+1개입니다.

k = 3 이면

n = 2 일 때 (0, 1, 1) (1, 1, 0) (1, 0, 1) (0, 0, 2) (0, 2, 0) (2, 0, 0) 6개입니다.

n = 3 일 때 (0, 0, 3) (0, 3, 0) (3, 0, 0) (0, 1, 2) (0, 2, 1) (1, 0, 2) (1, 2, 0) (2, 0, 1) (2, 1, 0) (1, 1, 1) 10개입니다.

이를 표로 표현하면 다음과 같습니다.

이를 통해 점화식 dp[i][j] = dp[i][j-1]+dp[i-1][j] (i, j가 2 이상인 경우) 를 도출할 수 있습니다. 

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