1. 풀이 일반적인 mst문제이고, N개의 노드를 모두 연결하는 edge를 만들어서(nC2개) 크루스칼을 적용하면 정답은 맞지만 시간초과가 발생한다. (소스코드1)​ 시간초과를 줄일 수 있는 방법은 아래의 조건을 이용해서 사용하는 edge의 개수를 줄이는것. (소스코드2) 더보기 행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다. 그리고 위조건을 이용하는 방법은 아래와 같다. (1) 1차원 좌표에서 N개의 점이 있고, 이때 N개의 점으로 mst를 만드는 방법은 왼쪽부터 i번째 점을 i+1번째 점과 연결해나가는 방법이다. (n-1개) (2) 3차원에서도 똑..

1.풀이 (1) 주어진 선후관계만으로 q와 graph를 구성한다 (2) q에 있는 요소 중 가장 작은(가장 쉬운)것을 pop하면서 진행한다 => heap을 쓴다. ​ * 두가지풀이 - 소스코드1(시간초과) : toNode와 fromNode를 사용. fromNode를 하나씩 삭제하고 fromNode가 비어있을때 pq에 넣음 - 소스코드2 (통과) : toNode와 들어오는 노드의 개수(cntParent)를 사용. cntParent 0이 될때 pq에 넣음 ​ 2. 소스코드 (1) 소스코드1 (python3 시간초과) import heapq N,M=map(int,input().split()) fromNode={} toNode={} for i in range(1,N+1): fromNode[i]=[] toNode..

1. 풀이 (1) 늦게 끝낼 수 있는 일부터 탐색하여 최대한 늦게 시작한다. (2) (1)에서 탐색한 일이 이전의 일의 데드라인에 영향을 주면, 이전의 일을 영향받는만큼 늦게 시작한다. 2. 소스코드 N=int(input()) L=[] for i in range(N): L.append(list(map(int,input().split()))) def returnSecond(L): return L[1] L.sort(key=returnSecond) preStart=L[N-1][1]-L[N-1][0] for i in range(N-2,-1,-1): if preStart

1. 풀이 모든 문제는 푸는데 1시간이 걸리기 때문에, 컵라면을 가장 많이주는걸 그리디하게 고르면 된다. 이때 문제마다 데드라인이 다르기 때문에 시간을 뒤에서부터 1시간 단위로 탐색하면서 먼저 끝나는 일 중에 컵라면을 많이 주는 것부터 차례대로 수행하면 된다. 2. 소스코드 from collections import deque import heapq N=int(input()) L=[] for i in range(N): L.append(list(map(int,input().split()))) # t시간까지 해야되는거 pq에추가 def addPQ(t): while(L): dead,cup=L.pop() if dead==t: heapq.heappush(cupPQ,-1*cup) else: L.append([dea..

1. 풀이 (1) 주유소의 위치를 기준으로 가까운 순으로 정렬을 한다. (2) 현재위치에서 최대로 갈 수 있는 위치를 확인한다 - 갈 수 있는 위치가 도착지점을 넘으면 -> 종료 - 넘지 않으면 -> 갈 수 있는 위치까지의 주유소 중 가장 주유를 많이 할 수 있는 곳에서 주유 (3) 주유한 만큼 위치이동 (4) (2),(3)을 반복 2. 소스코드 import heapq import sys from collections import deque N=int(input()) point=[] for i in range(N): a,b=map(int,sys.stdin.readline().rstrip().split()) point.append([a,b]) L,P=map(int,input().split()) point...

1. 풀이 어떤 node의 k번째 최단경로는 아래의 다익스트라구조에서 [구역1]에 해당하는부분에 k번째로 방문됐을때에 해당된다. while(dij): nowDist,nowNode,isCon=heapq.heappop(dij) if nodeDist[nowNode]

1. 풀이 플로이드와샬을 이용해서 사이클을 구한다. 처음에 i->i로 가는 가중치를 INF로 주고, 플로이드와샬을 한번 수행한 뒤, i->i 값이 변해있으면 i->i로 가는 사이클이 존재한다는 뜻. 이때 가중치가 사이클 도로의 합이므로 그중 최소를 찾는것이 정답이 된다. ​ 2. 소스코드 import sys INF = 9876543210 V, E = map(int, input().split()) L=[[0 for j in range(V)] for i in range(V)] for i in range(V): for j in range(V): L[i][j]=INF for i in range(E): a, b, c = map(int, sys.stdin.readline().rstrip().split()) L[a-..

1. 풀이 * 오일러 경로 : 모든 edge를 정확히 1번만 방문하는 연속된 경로 차수가 홀수인 정점이 2개(출발점과 도착점은 각각 차수가 홀수개) ​ * 오일러 회로 : 오일러 경로 중 시작점과 끝점이 같은것 차수가 홀수인 정점이 0개(나갔으면 들어오는 점(or 들어왔으면 나가는점)이 있어야 함) ​ 오일러 회로를 구하는 문제이므로 (1) 모든 정점에서 차수가 짝수임을 확인하고 ​(2)짝수임이 확인되었으면 반드시 오일러 회로가 (어느 정점에서 시작하든) 가능하므로 아무정점이나 시작점으로 잡고 dfs돌림. ​ (2) dfs를 돌릴 때 - 어느방향으로 돌리든 답은 나온다. 따라서 L[nowNode][conNode]-=1을 해주고 다시 +=1을 해줄 필요가 없다. 즉 탐색은 무조건 edge의 개수만큼 한다...

1. 풀이 (1) 입력값 아래의 두 리스트로 그래프를 관리한다 parent[i] : i 노드로 들어오는 노드들을 저장한 리스트 garph[i]: i노드에서 향하는 노드들을 저장한 리스트 이후 정석대로 간선을 삭제한 후, parent[i]가 비어있는 노드들을 차례대로 q에 넣어서 탐색한다. ​ (2) 위상정렬 이때 각 노드의 최소완료시간을 구해야 하기 때문에 ans[toNode]=max(ans[nowNode]+time[toNode],ans[toNode])를 수행해 주어야 한다. ans[i] : i건물까지 만드는데 드는 최소시간 time[i] : i건물을 만드는데 드는 시간 q에서 뽑힌 노드 i의 ans[i]는 최소시간으로 보장된상태이다. 그리고 ans[nowNode]+time[toNode]가 ans[toN..

1.풀이 (1) 플로이드와샬을 이용하여 연결되어있는지를 확인한다. (2) bfs를 통해 연결되어있는 컴포넌트에서 경찰서 건설비용이 가장 작은곳에 경찰서를 짓는다. ​ 위의 방법으로 어거지로 풀었지만 아래와 같이 최적화하여 푸는 방법을 찾아본다. *최적화 풀이 (1) dfs(강연결요소)를 통한 풀이 (2) 유니온-파인드를 이용. ​ 2. 소스코드 (플로이드와샬, bfs) INF=9876543210 N=int(input()) cost=list(map(int,input().split())) L=[] for i in range(N): L.append(list(map(int,list(input())))) def floid(): #초기값 설정 for i in range(N): for j in range(N): if..

1.풀이 모든쌍의 최단거리가 나타나 있고, 간선의 개수를 최소로 해야 한다. 따라서 모든 도시간의 최단거리를 가진 간선이 존재한다고 생각을 하고, L[i][j]=L[i][k]+L[k][j]를 만족하는 간선 i - j 는 k를 거쳐가면 되기 때문에 없애주는 방식으로 진행. 불가능한 경우는 도시i와 도시j의 최단거리 L[i][j] 보다 k를 거쳐가는 L[i][k]+L[k][j] 가 더 작은 경우가 존재하는 경우 ​ 2. 소스코드 import sys N=int(input()) L=[] for i in range(N): L.append(list(map(int,input().split()))) edge=[[1 for j in range(N)] for i in range(N)] for k in range(N): f..

1.풀이 거쳐가는 노드수의 최솟값을 계산해야한다. 하이퍼튜브는 k가지 노드를 모두 연결해주는, 즉 1의 가중치를 가지게 해주는 장치이다. 따라서 아래와 같이 가중치를 주면 하이퍼튜브를 통해서 노드를 연결해주는 그래프를 만들 수 있다. 노드 -> 하이프튜브 : 가중치 1 하이퍼튜브 -> 노드 : 가중치 0​ 이렇게 하면 (노드a->하이퍼튜브->노드b) 의 cost가 1이 되어서 다익스트라 처럼 풀 수 있다. ​ 2.소스코드 import heapq maxNum=9876543210 N,K,M=map(int,input().split()) graph={} for i in range(1,N+M+1): graph[i]=[] for i in range(M): temp=list(map(int,input().split()..

1.풀이 (1) 2개의 연결된 그래프를 만들기 위해선 크루스칼 알고리즘을 적용한 뒤 가장 큰 간선을 하나 빼면된다. 이때 가장 큰 간선은 N-1번째에 들어오는 간선이므로, 2개의 mst를 만들기 위해선 간선을 N-2번째까지 추가해 주면 된다. (2) 최소간선부터 하나씩 넣어볼 때, pq를 쓰는방법과 sort를 하고 앞에서부터 뽑는 방법이 있다. 결과는 아래와 같다. 소스코드1 : edge.pop(0)을 해줌 ->시간초과 소스코드2 : edge[i]로 참조해줌 -> 통과 (5696ms) 소스코드3 : heapq.heappop() -> 통과 (6992ms) *pq는 매번 pop하고 정렬해주어야 하기 때문에 한번 정렬 후 앞에서 부터 참조하면 되는 소트보다 느림 단, 소트후 앞에서..

1. 풀이 플로이드와샬의 정석 k 포문이 돌아갈때 L[i][j]의 의미 : k정점까지 사용이 가능할 때 i에서 j까지의 최단거리 * 초기화시 주의할점 L[i][j]가 (1) if i==j 이면 => 0 (2) if i!=j 이면 => inf 으로 초기화할것! 2. 소스코드 N,M=map(int,input().split()) maxNum=9876543210 L=[[maxNum for j in range(N+1)] for i in range(N+1)] for i in range(1,M+1): a,b=map(int,input().split()) L[a][b]=1 L[b][a]=1 for i in range(1,N+1): L[i][i]=0 for k in range(1,N+1): for i in range(1,..

1. 풀이 (1) 벨만포드를 적용할 때 경로를 저장한다. * 처음엔 특정 노드에서 어디로 가는지를 저장했다. 하지만 이렇게 하면 우리가 원하는 목적지로 가는 경로가 나오는것이 아니라 입력 순서에 영향을 받아 해당 노드에서 어떠한 다른 노드로의 최단경로의 일부가 저장될 수 있다. ex) 1-2, 1,3이 있고 3이 목적지일때 1노드의 방향이 2노드를 향할 수 있다. 따라서 특정 노드가 어느 노드에서 오는지를 저장해야한다. (즉 이전 노드가 무엇인지를) ​ (2) 벨만 포드를 적용한 후 싸이클을 확인해야한다. 이때 경우의 수는 다음과 같다 1. (출발지에 붙은)사이클이 있다 (​isUpdate==True) (1) 도착지와 붙어있다. (q를 통해서 확인, connectCycle==True) => -1 (2) ..

1. 풀이 가중치 있는 그래프이므로 일반적인 다익스트라 알고리즘을 사용하면 되는데, 특정 경로를 지났는지를 확인해주어야 한다. 다익스트라는 아래와 같이 구성된다. while(dij): nowDist,nowNode,isCon=heapq.heappop(dij) if nodeDist[nowNode]

1. 풀이 이분그래프를 확인하는 방법은 다음과 같다. (1) 2개의 색깔을 가지고 dfs를 통해 인접한 노드에 다른 색깔을 칠하며 전체를 다 칠하기. (2) 2중 포문을 통해 인접한 노드에 다른색이 칠해져 있는지 확인. -> 다른색이 칠해져 있으면 이분그래프 될 수 없음. (3) 이분그래프 2. 소스코드 import sys sys.setrecursionlimit(10 ** 7) k = int(input()) turn = [1, 0] def cheak(): for v in range(1, V + 1): nowColor = colorV[v] for conNode in graph[v]: if colorV[conNode] == nowColor: print("NO") return print("YES") def d..

1. 최단거리 2. 최소스패닝 트리(MST)