본문 바로가기

분류 전체보기

(402)
[백준 2261번] 가장 가까운 두 점 (Python3) import sys input = sys.stdin.readline from math import sqrt,ceil dx = [0,0,0,1,1,1,-1,-1,-1] dy = [0,1,-1,0,1,-1,0,1,-1] N = int(input()) xlist = [] ylist = [] for i in range(N): x,y = map(int,input().split()) xlist.append((x,y)) ylist.append((y,x)) xlist.sort() ylist.sort() result = 10**9 for i in range(N-1): x1,y1 = xlist[i] x2,y2 = xlist[i+1] result = min(result,(x1-x2)**2+(y1-y2)**2) x1,y1 =..
[백준 2098번] 외판원 순회 (Python3) import sys input = sys.stdin.readline INF = 10**9 N = int(input()) graph = [] for i in range(N): graph.append([*map(int,input().split())]) DP = [[-1]*N for i in range(1
[백준 2481번] 해밍 경로 (Python3) import sys input = sys.stdin.readline from collections import deque sys.setrecursionlimit(10**6) def printpath(x): if x == 1: print(1,end=" ") return printpath(path[x]) print(x,end=" ") N,K = map(int,input().split()) num = {} code = {} for i in range(1,N+1): c = input().strip() num[c] = i code[i] = c path = {i:-1 for i in range(1,N+1)} path[1] = 1 dq = deque([1]) while dq: now = dq.popleft() cli..
[백준 5676번] 음주 코딩 (Python3) import sys input = sys.stdin.readline def makeseg(start,end,x): if start == end: segtree[x] = data[start] else: mid = (start+end)//2 segtree[x] = makeseg(start,mid,x*2) * makeseg(mid+1,end,x*2+1) return segtree[x] def updateseg(i,v,start,end,x): if start == end: segtree[x] = v else: mid = (start+end)//2 if i
[백준 2213번] 트리의 독립집합 (Python3) import sys input = sys.stdin.readline N = int(input()) weight = [*map(int,input().split())] graph = [set() for i in range(N)] for i in range(N-1): x,y = map(lambda x:x-1,map(int,input().split())) graph[x].add(y) graph[y].add(x) DP = [[0,0] for i in range(N)] path = [[set(),set([i])] for i in range(N)] def DFS(now): for next in graph[now]: graph[next].remove(now) DFS(next) if DP[next][0] >= DP[ne..
[백준 15653번] 구슬 탈출 4 (Python3) import sys input = sys.stdin.readline from collections import deque dy = [1,0,-1,0] dx = [0,1,0,-1] N,M = map(int,input().split()) board = [] for i in range(N): board.append(list(input().strip())) def go(y,x,direction,opcolor): while True: y1 = y+dy[direction] x1 = x+dx[direction] if (y1,x1) == opcolor: break if board[y1][x1] == "O": return 0,0 if board[y1][x1] == ".": y,x = y1,x1 else: break re..
[백준 15644번] 구슬 탈출 3 (Python3) import sys input = sys.stdin.readline from collections import deque dy = [1,0,-1,0] dx = [0,1,0,-1] D = "DRUL" N,M = map(int,input().split()) board = [] for i in range(N): board.append(list(input().strip())) def go(y,x,direction,opcolor): while True: y1 = y+dy[direction] x1 = x+dx[direction] if (y1,x1) == opcolor: break if board[y1][x1] == "O": return 0,0 if board[y1][x1] == ".": y,x = y1,x1 els..
[백준 16933번] 벽 부수고 이동하기 3 (Python3) import sys input = sys.stdin.readline from collections import deque dy = [1,-1,0,0] dx = [0,0,1,-1] N,M,K = map(int,input().split()) def BFS(): dq = deque() dq.append((0,0,0,1)) visited = [[[0]*M for i in range(N)] for i in range(K+1)] while dq: y,x,k,cnt = dq.popleft() if visited[k][y][x]: continue if y == N-1 and x == M-1: return cnt if board[y][x] == 1 and cnt%2 == 1:#현재 벽인데 밤일 경우 dq.append((..