다익스트라 응용 문제 다익스트라 알고리즘만 정확히 이해하고 있으면 조금만 응용해서 풀 수 있다. 핵심은 다음과 같다. 1. 경로중 가장 긴 거리를 pq로 관리한다. 기존의 다익스트라는 경로의 합의 최소를 찾지만, 이 문제에서는 경로중 가장 긴 거리의 최소를 찾는다. 즉 기존에 다음과 같이 경로의 합을 pq에 넣는 방식을 addedD=toD+d if addedD

문제풀이 스벅까지의 거리와 맥날까지의 거리의 합이 최소가 되는 곳을 구하면 된다. 스벅, 맥날은 하나 이상이 있다. 따라서 각각의 집에서 그 집과 가장 가까운 스벅, 맥날까지의 거리를 구하고 그 합이 최소가 되는 집을 찾으면 된다. 도로는 양방향이고 노드사이의 서로 다른 양의 가중치가 존재하므로 다익스트라를 이용하면 된다. 이때 각각의 집에서 가장 가까운 스벅, 맥날까지의 거리만 구하면 된다. 따라서 아래와 같은 순서로 진행한다. 0. 예제 1. 모든 맥날과 가중치 0으로 이은 맥날NODE, 모든 스벅과 가중치 0으로 이은 스벅NODE를 만든다. 2. 맥날NODE에서 각 집까지의 거리, 스벅NODE에서 각 집까지의 거리를 구한다. 주의할점 모든 맥날점과 모든 스벅점을 0의 가중치로 이어서 만든 맥날NOD..

1. 풀이 최대유량을 구해주기 위해선, 시점부터 종점까지 (1)가능한 경로와 경로상의 최소 유량 찾기, (2)현재상태를 업데이트 하는 과정을 더이상 가능한 경로가 없을 때 까지 해주면 된다. 각각의 과정에 대한 구체적인 설명은 다음과 같다. (1) 가능한 경로와 그때의 유량 찾기 - bfs 경로를 찾을 때는 bfs로 탐색을 한다. 이때 한번 탐색한 노드는 다시 탐색하지 않기 위해 (흔히 bfs문제를 풀 때 하는) visited노드로 관리를 해줘야 한다. 이때 단순히 방문하면 1, 그렇지 않으면 0으로 하는게 아니라 해당 노드의 경로상의 직전의 노드를 저장해놓는다 (그래서 이름도 visited가 아니라 prev로 한다). 왜냐하면 (2)현재상태를 업데이트 에서 경로를 따라가며 상태를 업데이트 해야 하기 때..

1. 풀이 아래와 같은 2번조건이 네트워크를 복구해서 통신이 가능하도록 만드는 것도 중요하지만, 해커에게 공격을 받았을 때 보안 패킷을 전송하는 데 걸리는 시간도 중요한 문제가 된다. 따라서 슈퍼컴퓨터가 다른 컴퓨터들과 통신하는데 걸리는 최소 시간이, 원래의 네트워크에서 통신하는데 걸리는 최소 시간보다 커져서는 안 된다. 위와같이 충족되어야 하기 때문에, 다익스트라를 이용하여 그래프를 만들어 나간다. 다익스트라에서 노드들의 거리를 업데이트 할 때, 특정노드의 이전노드도 같이 업데이트 해주며 edge들을 파악해 준다. 다익스트라를 이용해서 mst를 만드는건 어렵지 않은데, 위의 알고리즘을 적용하기 위해선, "다익스트라를 이용해 이은 간선들이 항상 MST를 만든다" 라는 전제조건이 있어야 한다. (1) 이는..

1. 풀이 A열에 있는 기계들을 왼쪽부터 차례대로 B와 매칭시킨다. 이때 매칭된 B의 오른쪽에 있는 기계중에 매칭된 기계의 수가 겹치는 선의 수가 된다. 그 이유는, A의 왼쪽기계부터 차례대로 매칭을 시키기 때문에, B의 왼쪽 기계는 매칭이 되었어도 선이 겹칠일이 없기 때문이다. 이를 그림으로 표현하면 아래와 같다. 따라서 예시를 순서대로 진행하면 아래와 같다. 따라서 답(겹치는 선의 수)은 3이다. 이때 수행해야 할 작업은 아래와 같이 두가지이고 각각을 다음과 같이 해결한다. (1) 현재 매칭중인 기계의 B에서의 위치 => dictionary 자료형 이용 (2) B의 오른쪽에서 이미 매칭이 된 기계의 개수 => 세그먼트트리(구간합) 이용 2. 소스코드 import math import sys N=int..

1. 풀이 (1) 숫자를 넣는 방법 숫자를 1부터 차례대로 적절한 위치에 집어넣는다. 숫자를 1부터 집어넣기 때문에 집어넣을 위치 앞에 아직 차지 않은 부분은 무조건 현재넣을 숫자보다 크고, 이미 차있는 숫자는 현재숫자보다 작다. (2) 세그먼트 트리 따라서 숫자가 들어갈 위치를 세그먼트트리를 이용해서 찾는다. 세그먼트트리를 이용해서 구간합을 구해주는데, 이를 이용하여 현재 위치앞에 몇개의 숫자가 있는지를 빠르게 확인해준다. * 처음에 update함수 따로, 위치를 찾는 함수를 따로 구현해서 시간 초과가 떳다(소스코드1). 위치를 찾으면서 바로 수정을 해야 통과한다. 2. 소스코드 (1) 소스코드1 (update함수, 쿼리함수 따로구현, 시간초과) import sys import math def init..

1. 풀이 이 문제에선 "붙어있는 수열에서 최솟값을 찾는 행위" 를 엄청 많이 해야 한다. (= 이를 쿼리라고 한다) 이때 "붙어있는 수열에서 최솟값을 찾는 행위"를 빠르게 하기 위해 세그먼트트리를 사용한다. 이 문제는 너비는 모든 직사각형이 같지만, 높이만 다르기 때문에 연속된 높이들 중 가장 작은 높이가 만들수있는 직사각형의 높이가 된다. 따라서 높이의 최솟값을 세그먼트 트리에 저장한다. 이때 주의할점은 분할 정복을 할 때 최소 높이를 기준으로 좌 우로 계속해서 탐색을 해야 하기 때문에, 최소높이의 인덱스를 알아야 한다는 것이다. 따라서 세그먼트 트리에는 최소높이와 함께 최소 높이의 인덱스도 저장해야 한다. 2. 소스코드 import math import sys sys.setrecursionlimit..

수열이 있을 때 중에서 연속된 특정구간을 주고, 특정구간의 1. 최댓값([백준]2357 최솟값과 최댓값) 2. 최솟값([백준]10868 최솟값) 3. 합([백준]2042 구간합, [백준]1275 커피숍2) 4. 곱([백준]11505 구간곱 구하기) 을 여러번 구하는 문제는 세그먼트트리를 쓰면 된다. 세그먼트 트리를 사용하기 위해선 보통 아래와 같은 3가지 함수가 필요하다. 1. 주어진 수열을 이용하여 처음으로 세그먼트 트리를 만드는 함수 2. 세그먼트트리의 노드하나를 수정하는 함수 3. 세그먼트트리를 이용하여 구간합(or 구간곱 or 최댓값,최솟값)을 구하는 함수. 각 함수코드는 다음과 같다. 1. 세그먼트트리 초기화 함수. def init(node,start,end): if start==end: tre..

1. 풀이 더보기 시작점, 열쇠가 있는 모든 지점에서 로봇이 복제되고, 모든 열쇠를 얻어야 하며, 이때 모든 로봇의 이동거리를 구한다. 위의 문제가 MST문제임을 알면 구현은 매우쉽게 일반적인 MST를 푸는것과 같이 하면 된다. 하지만 위의 문제 MST문제인지를 알기가 어렵다. 따라서 조건을 어느정도 외워두고 비슷한 상황에서 MST를 떠올릴 줄 아는것이 중요해 보인다! 2. 소스코드 from collections import deque import sys dR=[0,0,-1,1] dC=[1,-1,0,0] N,M=map(int,input().split()) L=[] for i in range(N): L.append(list(input())) def dist(sR,sC,fR,fC): q=deque([[sR,..

1.풀이 재귀로 풀었을때 시간초과가 발생했다 (소스코드1). O(NM)이고 제한시간 5초(C++기준) 이므로 살짝 애매한데 최적화가 잘 안된것 같다. stack으로 풀었고 pypy로 제출하여 정답. (소스코드2) ​ 2.소스코드 (1) 소스코드1 (시간초과) import sys from collections import deque N,M=map(int,input().split()) graph={} for i in range(1,N+1): graph[i]=[] for i in range(M): A,B=map(int,sys.stdin.readline().rstrip().split()) graph[B].append(A) hackCom=0 ans=[] for start in range(1,N+1): visite..

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. 풀이 어떤 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..