본문 바로가기

분류 전체보기

(402)
[백준 17267번] 상남자 (Python3) import sys input = sys.stdin.readline from collections import * dy = [0,0,-1,1]; dx = [-1,1,0,0] def BFS(n,d): visited = [[0]*M for i in range(N)] dq = deque([(sy,sx,0)]) while dq: y,x,cnt = dq.popleft() if visited[y][x]: continue visited[y][x] = 1 for i in range(4): y1,x1 = y+dy[i],x+dx[i] if N>y1>=0 and M>x1>=0 and not visited[y1][x1]|board[y1][x1]: if i==d: if cnt < n: dq.append((y1,x1,cnt+1)..
[백준 6543번] 그래프의 싱크 (Python3) import sys input = sys.stdin.readline sys.setrecursionlimit(10**4) def DFS(now): global id nowid = visited[now] = id stack.append(now) for next in graph[now]: if sccnum[next]: continue if not visited[next]: id += 1 DFS(next) visited[now] = min(visited[now],visited[next]) if visited[now]==nowid: n = len(scc); scc.append([]) while 1: x = stack.pop() sccnum[x] = n; scc[-1].append(x) if x==now: brea..
[백준 10803번] 정사각형 만들기 (Python3) def DFS(n,m): if n==m: DP[n][m] = 1 return DP[n][m] = n*m for n1 in range(1,n//2+1): n2 = n-n1 n1,m1,n2,m2 = max(n1,m),min(n1,m),max(n2,m),min(n2,m) if not DP[n1][m1]: DFS(n1,m1) if not DP[n2][m2]: DFS(n2,m2) DP[n][m] = min(DP[n][m],DP[n1][m1]+DP[n2][m2]) for m1 in range(1,m//2+1): m2 = m-m1 n1,m1,n2,m2 = max(n,m1),min(n,m1),max(n,m2),min(n,m2) if not DP[n1][m1]: DFS(n1,m1) if not DP[n2][m2]: DF..
[백준 1109번] 섬 (Python3) import sys input = sys.stdin.readline from collections import * dy = [1,-1,0,0,1,1,-1,-1]; dx = [0,0,1,-1,1,-1,1,-1] def DFS(ocean): island = set(); h = 0 for y,x in ocean: if not visited[y][x]: island |= BFS(y,x,4,0) for y,x in island: if not visited[y][x]: h = max(h,DFS(BFS(y,x,8,1))+1) if len(result)==h: result.append(0) result[h] += 1 return h def BFS(y,x,d,n): dq = deque([(y,x)]); S = set()..
[백준 5446번] 용량 부족 (Python3) import sys input = sys.stdin.readline def update(word,n): now = Dict for w in word+"#": now[n] = 1 if not now.get(w): now[w] = {} now = now[w] now[n] = 1 def DFS(now): global result if not now.get(1): return if not now.get(0) or len(now)==2: result += 1 return for w in now: if w==0 or w==1: continue DFS(now[w]) for _ in range(int(input())): Dict = {} for _ in range(int(input())): update(input()...
[백준 14908번] 구두 수선공 (Python3) import sys input = sys.stdin.readline def bubble(): swap = 0 for i in range(N-1): if data[i][0]*data[i+1][1] > data[i+1][0]*data[i][1]: data[i],data[i+1],swap = data[i+1],data[i],1 return swap N = int(input()) data = [[*map(int,input().split()),i+1] for i in range(N)] while bubble(): pass print(*map(lambda x:x[2],data)) 버블소트로 해결하였다. 재미있는 문제였다. 아이디어를 떠올리기 약간 까다로울 수 있다. 풀이를 설명하면, 1. 모든 입력값을 번호와 함께..
[백준 3977번] 축구 전술 (Python3) import sys input = sys.stdin.readline sys.setrecursionlimit(10**6) def DFS(now): global id visited[now] = nowid = id stack.append(now) for next in graph[now]: if not visited[next]: id += 1 DFS(next) visited[now] = min(visited[now],visited[next]) if visited[now] == nowid: n = len(scc); scc.append([]) while 1: x = stack.pop() visited[x] = 1e7 scc[-1].append(x); sccnum[x] = n if x==now: break for _..
[백준 9015번] 정사각형 (Python3) import sys input = sys.stdin.readline for _ in range(int(input())): N = int(input()) co = [tuple(map(int,input().split())) for i in range(N)] check = {*co} result = 0 for i in range(N): x1,y1 = co[i] for j in range(i+1,N): x2,y2 = co[j] dx,dy = x1-x2,y1-y2 if (x1+dy,y1-dx) in check and (x2+dy,y2-dx) in check or (x1-dy,y1+dx) in check and (x2-dy,y2+dx) in check: result = max(result,dx**2+dy**2) p..