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

1. 함수의 구성 유니온 파인드는 find와 union 두가지 함수로 구성이 된다. (1) find는 그래프에서 루트노드를 찾아주는 함수이다. int find(int x) { if (parent[x] == x) { return x; } else { return parent[x] = find(parent[x]); } } (2) union은 서로 연결되어 있지 않은 그래프를 연결시키는 함수이다. void Union(int x, int y){ x = find(x); y = find(y); if(x!=y){ parent[y] = x; } } 2. 함수의 사용 유니온 파인드는 아래의 두가지 경우에 사용할 수 있다. (1) 그래프가 연결되어 있는지 확인할 때 (ex [boj]1717_집합의 표현) 어떤 두 노드의 ..

0. 풀이 원칙 ※ dfs,dp류의 문제는 아래와 같은 원칙을 기본적으로 따른다. (1) dp 리스트를 -1로 초기화 한다. (2) 처음방문했을 때 0으로 바꿔준다 (3) 끝까지 간 다음 리턴값을 적절히 조정한다. 이때 리턴은 현재 depth에서 r,c의 상태를 판단하는 방식으로 아래와 같이 구성한다. (bfs를 수행할 때 queue에 넣기위해 미리 tempR,tempC를 검사하는것과 다르다. 일딴 재귀를 돌돌리고 검사한다.) if not (0 -1출력 - 이전경로에서 방문 -> dp 리턴 - 방문한적없음 -> 4방향조사 ​ 2. 소스코드 (1) 방문했을때 0으로 바뀌는걸 이용하여 사이클판단, 틀림 처음에 방문했을 때 dp가 -1에서 0으로 바뀌는것을 이용하여 사이클이 있는지 확인하려고 했다. dp는 끝..