본문 바로가기

분류 전체보기

(402)
[백준 1799번] 비숍 (Python3) 아주 까다로운 문제였다. 처음에는 모든 좌표를 돌면서 비숍을 놓고, 놓은 위치의 대각선 부분을 체크하는 식으로 브루트 포스 알고리즘으로 풀려고 했다. 코드는 다음과 같다. import sys input = sys.stdin.readline N = int(input()) board = [] for i in range(N): board.append(list(map(int,input().split()))) empty = 0 for i in board: empty += sum(i) def check(y,x): cant = set() sum,dif = y+x,y-x for i in range(N): if N>-i+sum>=0: if board[-i+sum][i] == 1: cant.add((-i+sum,i)) i..
[백준 1005번] ACM Craft (Python3) import sys input = sys.stdin.readline from collections import deque T = int(input()) for test in range(T): N,K = map(int,input().split()) time = list(map(int,input().split())) child = [[] for i in range(N+1)] indegree = [0]*(N+1) pretime = [0]*(N+1) for i in range(K): x1,x2 = map(int,input().split()) child[x1].append(x2) indegree[x2] += 1 W = int(input()) dq = deque() for i in range(1,N+1): if i..
[백준 2623번] 음악프로그램 (Python3) import sys input = sys.stdin.readline from collections import deque N,M = map(int,input().split()) indegree = [0]*(N+1) child = [[] for i in range(N+1)] for pd in range(M): order = list(map(int,input().split())) for i in range(1,order[0]): x1,x2 = order[i],order[i+1] child[x1].append(x2) indegree[x2] += 1 dq = deque() for i in range(1,N+1): if indegree[i] == 0: dq.append(i) seq = [] while dq: x ..
[백준 2252번] 줄 세우기 (Python3) import sys input = sys.stdin.readline from collections import deque N,M = map(int,input().split()) indegree = [0]*(N+1) child = [[] for i in range(N+1)] for i in range(M): x1,x2 = map(int,input().split()) child[x1].append(x2) indegree[x2] += 1 dq = deque() for i in range(1,N+1): if indegree[i] == 0: dq.append(i) seq = [] while dq: x = dq.popleft() for i in child[x]: indegree[i] -= 1 if indegree[..
[백준 9328번] 열쇠 (Python3) import sys input = sys.stdin.readline from collections import deque dy = [1,-1,0,0] dx = [0,0,1,-1] def entrance(): #경계 주변을 돌면서 입구 좌표를 찾는 함수 result = set() for i in range(N): if MAP[i][0] != "*": result.add((i,0)) if MAP[i][M-1] != "*": result.add((i,M-1)) for i in range(M): if MAP[0][i] != "*": result.add((0,i)) if MAP[N-1][i] != "*": result.add((N-1,i)) return result #입구 좌표를 모은 set 반환 def BFS(..
[백준 17143번] 낚시왕 (Python3) import sys input = sys.stdin.readline dr = [1,0,-1,0] dc = [0,1,0,-1] R,C,M = map(int,input().split()) ocean = [[0]*C for i in range(R)] speed,direction,size,co,dead = {},{},{},{},{} #속도, 방향, 사이즈, 좌표, 죽었는지 알려주는 dict for num in range(1,M+1): r,c,s,d,z = map(int,input().split()) ocean[r-1][c-1] = num co[num] = (r-1,c-1) speed[num] = s if d == 1: #방향전환 편의를 위해서 direction[num] = 2 if d == 2: directio..
[백준 1509번] 팰린드롬 분할 (Python3) import sys input = sys.stdin.readline INF = 10**9 seq = input().strip() N = len(seq) palin = [[] for i in range(N)] start,end = 0,0 while True: if end == N: break s,e = start,end if seq[s] == seq[e]: while True: palin[e].append(s) s1 = s-1 e1 = e+1 if not (s1>=0 and e1
[백준 20149번] 선분 교차 3 (Python3) import sys input = sys.stdin.readline x1,y1,x2,y2 = map(int,input().split()) x3,y3,x4,y4 = map(int,input().split()) def eq1(x,y): return (x2-x1)*(y-y1)-(y2-y1)*(x-x1) def eq2(x,y): return (x4-x3)*(y-y3)-(y4-y3)*(x-x3) def check(): if eq1(x3,y3)*eq1(x4,y4) min(y1,y2): return 1,0 if max(y1,y2)==min(y3,y4): return 1, (x1,max(y1,y2)) if max(y3,y4)==min(y1,y2): return 1, (x1,min(y1,y2)) elif (y4-y3)*..