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)

1. 풀이 그래프에서 음의 사이클이 단 하나라도 있으면 벨만포드의 V번째 반복에서 최솟값(nodeDist)의 갱신이 일어난다. 따라서 웜홀의 유무는 벨만포드 알고리즘을 이용하여 풀 수 있다 ​ 2. 주의사항 1. 도로는 양방향임 2. 도로와 웜홀은 모두 연결되어있다고 가정.(여러개의 컴포넌트 tc가 현재까진 없음) 현재 알고리즘은 임의의 점(1번노드) 하나를 잡아서 연결된 모든 노드들까지의 최단거리를 구한다. 따라서 임의의 시작점과 연결되어있는 그 음의 사이클만 확인할 수 있다. 아래가 반례이다. TRUE가 나와야 하지만 음의사이클이 시작점과 연결되어있지않아 음의사이클을 검출하지못하고 FALSE가나옴 1 5 1 3 1 2 3 3 4 1 4 5 1 5 3 1 따라서 위의 경우(연결되어있진 않지만 음의 사이..

1.풀이 (1) 목적지에서 벌수있는 돈을 음(-)으로, 이동비용을 (+)로 두고 간선의 가중치를 부여한다 (2) 벨만포드로 최단 거리를 구하기 위해 N-1번 edge relaxation 수행한다. (3) N번째에서 아래의 사항을 확인 - 음의 사이클이 있는지(nodeCost[n1]+cost"gg" - (시작부분과 연결된)음의사이클이 존재하고, 해당 음의 사이클에서 목적지로 이동이가능할때(bfs로확인)->"gee" - 그렇지않은경우(목적지까지 도달할수있고, 음의사이클이 존재하지만 목적지로 도달할수 없는경우 or 음의사이클 존재안하는경우) -> 값출력 (-1곱할것) ​ *많이틀림 처음에 출발지에서 임의의 음의 싸이클까지 연결이 되있는지를 확인해주는 N번째반복의 조건문(nodeCost[n1]!=maxNum)를..

파티에 진실을 아는사람이 있으면 진실만을 말해야 한다. 새롭게 진실을 알게 된 사람을 고려해야한다(그사람이 참석하는 다른 파티에서도 진실을 말해야한다) ​ 1. 풀이 (1) 그래프 연결 1) 파티를 하나의 노드로 본다. 2) 파티를 두개씩 짝지어서 비교하면서, 한사람 이상을 공유하면 연결한다. (파티1과 파티2를 비교하여 둘다 참여하는사람이 있으면 연결한다.) 3) 연결이 완료되면 탐색을 시작한다. (2) 탐색 1) 연결된 노드(파티)들을 탐색한다 2) 연결된 파티들 중 하나의 파티에서라도 진실을 아는사람이 있다면, 연결된 모든 파티에는 진실을 말해야한다 3) 한명도 진실을 아는사람이 없다면 연결된 모든 파티에는 과장을 해도된다. ​ 2. 소스코드 from collections import deque N..

1. 풀이 (1) 설치횟수의 최솟값을 구한다. 설치할때만 이동거리를 +1해주고, 그렇지 않은 노드간의 연결은 +0 (2) 즉 간선간의 가중치가 다르므로(1 or 0) bfs가 아닌 다익스트라를 이용한다. (bfs로 탐색하면, 처음으로 다른문(#)을 찾은 경우가 거울의 최소설치가 아닌, 거울설치에 제약이 없을 때 최소이동 경로가 된다. 따라서 모든경우를 다 탐색한 후 그 중 최소설치횟수를 찾아야함.) (3) 이 문제는 특히 이동방향 상의 제약(빛은 직진만함)이 있기 때문에 한 노드(r,c)에 총 4번까지 방문이 가능하다. 따라서 한 노드 nodeDist[r][c]에 4방향의 저장소를 만든다 즉 nodeDist[r][c][k] : r,c에 k방향일때의 최소 설치횟수 ​ 2. 소스코드 import heapq ..

1. 풀이 최소스패닝트리(MST)문제. 크루스칼 알고리즘을 사용한다. 사이클을 확인하기 위해 유니온파인드를 이용해아햐며, 이때 dfs(or bfs)를 사용하면 시간초과가 난다. ​ 2. 소스코드 (1) dfs,시간초과 import heapq from collections import deque def isCycle(L): visited=[-1 for i in range(V+1)] stack=deque([L[0][0]]) while(stack): temp=stack.pop() # 스택에 있으면 싸이클 if temp in stack: return True visited[temp]=1 for n1,n2 in L: if n1==temp and visited[n2]==-1: stack.append(n2) elif..

어떤노드에 처음으로 방문한 순간이 최단거리임이 보장된다(bfs와 비슷). 따라서 주어진 끝노드에 도달하면 해당 비용을 출력한 후 종료한다. import heapq N=int(input()) M=int(input()) graph={} for i in range(N): graph[i+1]=[] for i in range(M): a,b,c=map(int,input().split()) graph[a].append([b,c]) start,end=map(int,input().split()) maxNum=9876543210 nodeDist=[maxNum for i in range(N+1)] dij=[[0,start]] heapq.heapify(dij) while(dij): temp=heapq.heappop(dij) ..

1. 풀이 1) 다음의 두가지 거리가 필요하다. (파티장 x에서 a까지의 최단거리) + (a에서 파티장x까지 최단거리) 2) (파티장 x에서 a까지의 최단거리) : X를 시작점으로 다익스트라를 이용해서 구한다 3) (a에서 파티장x까지 최단거리) : edge를 모두 반대방향으로 바꾼 후(cost는 그대로) 다익스트라. 위가 성립하는 이유는 (graph에서 a->b 까지의 최단거리) == (edge의 방향을 바꾼 graph에서 b->a까지의 최단거리) 이기 때문에 자명하다. 2. 소스코드 import heapq #input N,M,X=map(int,input().split()) graph={} graphR={} for i in range(1,N+1): graph[i]=[] graphR[i]=[] for i..

모든 노드들을 최소한의 비용으로 연결한 트리를 최소신장트리(mst)라고 한다. 최소신장 트리를 만드는 방법은 여러가지가 있다. ​ 1. 크루스칼 알고리즘 1) 모든 간선들을 오름차순으로 정렬한다. 2) 가중치가 작은 간선부터 하나씩 연결한다. 3) 간선을 연결했을 때 사이클이 생기면 해당 간선은 제거하고 다음 간선을 붙인다. 4) 간선의 개수가 (node개수 - 1)이 될때까지 간선을 이어붙인다. ​ https://m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221230994142&proxyReferer=https%3A%2F%2Fwww.google.com%2F 18. 크루스칼 알고리즘(Kruskal Algorithm) 이번 시간에 다루어 볼 내용은 바로 크루스..

1. 위상정렬? 2. 방법 어떠한 노드의 관점에서 그 노드로 들어오는 간선의 수를 진입차수라고 한다. 그리고 이러한 진입 차수가 0인 노드가 항상 시작 노드가 된다. 기본적인 알고리즘은 이러한 시작노드들을 큐에 넣고, 시작노드들과 연결되어 있는 다음 순서의 노드들 사이에 간선들을 없애며, 그 과정에서 새롭게 진입차수가 0이된 노드들을 다시 큐에 넣는 방식으로 진행된다. 3. 소스코드 #include #include #include #include using namespace std; // 부무노드 개수 저장 int parent[32001]; // togo[i]에는 i가 향하는 정점들을 저장 vector togo[32001]; queue q; int main() { int N, M; cin >> N >> ..