www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 � www.acmicpc.net 1. 아직 완전히 이해하지는 못했는데 cnt는 방법의 수이고 check는 현재위치에서 걸린 시간이다 y는 x에서 이동할 수 있는 곳을 나타내는데 y의 시간이 x에서 한 번 이동하게 되는 시간이랑 같거나 처음 방문한다면 경우의 수를 더해주기 위해 큐에 넣어주면 된다. from collections import deque N, K = map(int, input().split..
www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 최소 경로를 bfs로 찾는 법 from collections import deque def bfs(): dq=deque() dq.append((0,0)) vis[0][0]=1 cnt=1 while dq: x,y=dq.popleft() if x==n-1 and y==m-1: return vis[x][y] for k in range(4): xx,yy=x+dx[k],y+dy[k] if xx=n or yy=m: continue if vis[xx][y..
from collections import defaultdict import heapq hour=defaultdict(int) order=defaultdict(list) cnt=defaultdict(int) n=int(input()) for i in range(1,n+1): m=list(map(int,input().split())) hour[i]=m[0] if m[1]==-1: continue for j in m[1:-1]: order[j].append(i) # i이전에 j가 성행한다 cnt[i]+=1 q=[] ans=[0]*(n+1) for i in range(1,n+1): if cnt[i]==0: q.append(i) ans[i]=hour[i] while q: x=q.pop() for y in ord..
height: 현재 번호 작업을 하기 위한 우선순위 작업들을 담고 있다 cost: 현재 작업의 비용(시간) 모든 작업을 돌면서 현재 번호를 작업하기 위해 먼저 해야할 작업들의 비용의 최대값(여러 작업을 동시에 할 수 있다는 조건이 있다)에 현재 작업의 시간을 더한 것이 현재 번호를 작업하는 걸리는 시간이다 from collections import defaultdict import heapq height=defaultdict(list) cost=defaultdict(int) n=int(input()) for i in range(1,n+1): c=list(map(int,input().split())) cost[i]=c[0] if c[1]==0: continue for j in c[2:]: height[i]..
위상정렬 + 우선순위큐 문제번호가 작은 것 부터 풀어야된다 from collections import defaultdict import heapq height=defaultdict(list) cnt=defaultdict(int) q=[] n,m=map(int,input().split()) for i in range(m): a,b=map(int,input().split()) height[a].append(b) cnt[b]+=1 # b이전에 a가 선행된다 for i in range(1,n+1): if cnt[i]==0: q.append(i) result=[] while q: x=heapq.heappop(q) result.append(x) for j in height[x]: cnt[j]-=1 if cnt[j]..
from collections import defaultdict from collections import deque height=defaultdict(list) cnt=defaultdict(int) dq=deque() n,m=map(int,input().split()) for i in range(m): a,b=map(int,input().split()) height[a].append(b) cnt[b]+=1 # b이전에 a가 선행된다 for i in range(1,n+1): if cnt[i]==0: dq.append(i) result=[] while dq: x=dq.popleft() result.append(x) for j in height[x]: cnt[j]-=1 if cnt[j]==0: dq.appe..
www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 �� www.acmicpc.net 다익스트라 유형 import sys import collections import heapq t=int(sys.stdin.readline()) for kk in range(t): n,d,c=map(int,sys.stdin.readline().split()) graph=collections.defaultdict(list) for i in range(d): a,b,s=map(int,sys.stdin.readlin..
import sys import collections import heapq V,E=map(int,sys.stdin.readline().split()) K=int(sys.stdin.readline()) graph=collections.defaultdict(list) for i in range(E): u,v,w=map(int,sys.stdin.readline().split()) graph[u].append((v,w)) dist=collections.defaultdict(int) q=[(0,K)] while q: time,node=heapq.heappop(q) if node not in dist: dist[node]=time for v,w in graph[node]: alt=time+w heapq.heapp..
1. python import collections import sys sys.setrecursionlimit(2000) def dfs(x): visited[x]=True print(x,end=' ') for y in sorted(dict[x]): if not visited[y]: dfs(y) def bfs(x): visited[x]=True dq=collections.deque() dq.append(x) while dq: cur=dq.popleft() print(cur,end=' ') for y in sorted(dict[cur]): if not visited[y]: visited[y]=True dq.append(y) n,m,v=map(int,sys.stdin.readline().split()) dic..
문제 어떤 수열을 읽고, 홀수번째 수를 읽을 때 마다, 지금까지 입력받은 값의 중앙값을 출력하는 프로그램을 작성하시오. 예를 들어, 수열이 1,5,4,3,2 이면, 홀수번째 수는 1번째 수, 3번째 수, 5번째 수이고, 1번째 수를 읽었을 때 중앙값은 1, 3번째 수를 읽었을 때는 4, 5번째 수를 읽었을 때는 3이다. 입력 첫째 줄에 테스트 케이스의 개수 T(1