[백준 2718번] 타일 채우기 (Python3)
def DFS(n,now): if n == N-1: if 0 in graph[now]: DP[n][now] = 1 return for next in graph[now]: if not DP[n+1][next]: DFS(n+1,next) DP[n][now] += DP[n+1][next] for _ in range(int(input())): N = int(input()) DP = [[0]*16 for i in range(N)] graph = {0:{0,3,9,12,15},3:{0,12},6:{9},9:{0,6},12:{0,3},15:{0}} DFS(0,0) print(DP[0][0]) 비트마스킹을 이용한 DP로 구현하였다. 타일의 상태를 비트로 두고, 직접 손으로 그려서 해결하였다... 쉽게 말하면 현재 줄을..
[백준 1035번] 조각 움직이기 (Python3)
import collections,itertools,copy dy = [1,-1,0,0] dx = [0,0,1,-1] def BFS(n,board): y,x = piece[n] board[y][x] = 0 dq = collections.deque([(y,x,0)]) visited = [[0]*5 for i in range(5)] arr = [] distance = 25 while dq: y,x,d = dq.popleft() if visited[y][x] or d>distance: continue visited[y][x] = 1 for i in range(4): y1,x1 = y+dy[i],x+dx[i] if 5>y1>=0 and 5>x1>=0: if board[y1][x1]==P[0] and not bo..
[백준 2536번] 버스 갈아타기 (Python3)
import sys,collections input = sys.stdin.readline def cross(i,j): x1,y1,x2,y2,x3,y3,x4,y4 = *line[i],*line[j] return max(x1,x2)>=min(x3,x4) and max(x3,x4)>=min(x1,x2) and max(y1,y2)>=min(y3,y4) and max(y3,y4)>=min(y1,y2) M,N = map(int,input().split()) K = int(input()) line = [[*map(int,input().split())][1:] for i in range(K)] sx,sy,dx,dy = map(int,input().split()) line += [[sx,sy,sx,sy],[dx,dy,d..
