graph2 [Programmers] 순위 문제 : https://programmers.co.kr/learn/courses/30/lessons/49191 A가 B를 이겼는데 B가 C를 이겼다면 A가 C를 이긴것과 같다. 어디선가 많이 본 것 같은.. A에서 B로 가는 최단거리가 x1이고, B에서 C로 가는 최단거리가 x2라면 A에서 C로 가는 거리의 최단거리 중 하나가 x1 + x2 일 수 있다. 플로이드 워셜 알고리즘의 기본 이론이다. 알고리즘이론 글을 안쓴지 오래되었는데 다익스트라랑 벨만포드는 포스팅했는데 플로이드는 없네. 그렇지만 최단거리 알고리즘 중에 제일 좋아하는 알고리즘이다. (구현이 간단해서 ㅎㅎ) 플로이드 워셜을 돌려서 승부결과를 nxn 크기의 matches 배열에 채운다. matches[A][B] = A가 B를 이겼으면 true... 2021. 6. 11. [Programmers] 가장 먼 노드 문제 : https://programmers.co.kr/learn/courses/30/lessons/49189 bfs로 풀 수 있다. bfs를 돌면서 현재 노드, 1번 노드와의 거리를 저장한다. 만약 노드와의 거리가 갱신되면 정답 변수를 0으로 갱신한다. 노드를 탐색할때 정답변수에 1을 더한다. 시간복잡도는 O(V + E). V = 정점개수, E = 간선개수 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/programmers/Graph/%EA%B0%80%EC%9E%A5%20%EB%A8%BC%20%EB%85%B8%EB%93%9C.cpp 2021. 6. 9. 이전 1 다음