다리 놓기


오랜만에 첫 시도에 맞았다. DP를 사용한 조합 문제였는데 제출하기 전 시간초과가 걱정되긴 했었다. 그런데 생각보다 무난하게 통과할 수 있었다.


CODE

import sys
read=sys.stdin.readline

N=int(read())
f=[]
t=[]
for _ in range(N):
    a,b=map(int,read().split())
    f.append(a)
    t.append(b)

n=max(f)
m=max(t)

dp=list(list(0 for _ in range(m)) for _ in range(n))

for i in range(n):
    dp[i][i]=1
for i in range(m):
    dp[0][i]=i+1
for i in range(1,n):
    for j in range(i+1,m):
        dp[i][j]=dp[i][j-1]+dp[i-1][j-1]

for a,b in zip(f,t):
    print(dp[a-1][b-1])



탈출

BFS문제다. 앞에서 풀지 못했던 스타트택시, 아기상어 때문에 자신감이 많이 떨어져있었지만, 다행히 이 문제는 한번에 풀 수 있었다. 이 문제가 비교적 쉬웠던건지 아니면 최근에 BFS연습 문제들을 푼 효과인진 모르겠지만, 자신감을 얻어갈 수 있었다.

CODE

import sys
read=sys.stdin.readline
from collections import deque

r,c=map(int,read().split())
#r - 세로, c - 가로
map=list(list(read().strip()) for _ in range(r))
#비버 - D, 고슴도치 - S

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

#water와 kaktus가 번갈아가며 BFS를 수행해야 하기 때문에
#아래와 같이 각각 두개의 리스트를 생성해 운영했다.
water_s=deque([])
water_tmp=deque([])
kak_s=deque([])
kak_tmp=deque([])
D=[0,0]

for i in range(r):
    for j in range(c):
        if map[i][j]=='*':
            water_s.append([i,j])
        elif map[i][j]=='S':
            kak_s.append([i,j])
            map[i][j]=0
        elif map[i][j]=='D':
            D=[i,j]


def kak():
    while kak_s:
        a,b=kak_s.popleft()
        #print(a,b,map[a][b])
        for x,y in zip(dx,dy):
            ax=a+x
            by=b+y
            if 0<=ax<r and 0<=by<c and map[ax][by]==".":
                if map[a][b]=='*':
                    continue
                kak_tmp.append([ax,by])
                map[ax][by]=map[a][b]+1
            elif ax==D[0] and by==D[1]:
                if map[a][b]=='*':
                    print('KAKTUS')
                else: print(map[a][b]+1)
                sys.exit()
    for i in range(len(kak_tmp)):
        kak_s.append(kak_tmp.pop())


def water():
    while water_s:
        a,b=water_s.popleft()
        for x,y in zip(dx,dy):
            ax=a+x
            by=b+y
            if 0<=ax<r and 0<=by<c and (map[ax][by]!="X" and map[ax][by]!="D" and map[ax][by]!="*"):
                water_tmp.append([ax,by])
                map[ax][by]='*'
    for i in range(len(water_tmp)):
        water_s.append(water_tmp.pop())

while kak_s or water_s:
    kak()
    water()
print('KAKTUS')