Algorithm/BOJ172 [BOJ]1389번: 케빈 베이컨의 6단계 법칙 www.acmicpc.net/problem/1389 BFS, 플로이드-와샬 등 다양한 형태로 해결할 수 있습니다. 저는 플로이드로 해결했습니다. "dist[i][j] = i와 j가 연결되어 있는 거리"로 정의합니다. 초기값은 dist[i][j]= ∞로 두고, 입력이 주어져 있는 경우만 dist[i][j] = 1로 셋팅을 합니다. 그 다음에 플로이드를 돌면서 dist[i][j] > dist[i][mid] + dist[mid][j] 이면 dist[i][j] = dist[i][mid] + dist[mid][j] 로 갱신하면 됩니다. 코드: github.com/cottory/algorithm/blob/master/BOJ/BOJ1389.cc 2020. 9. 12. [BOJ]1613번: 역사 www.acmicpc.net/problem/1613 역사의 우선순위는 그래프 문제로 바라볼 수 있습니다. 그래프 문제 관점에서 모든 정점에서 다른 모든 정점으로의 관계가 궁금한 것이니 플로이드 알고리즘을 써서 해결할 수 있습니다. eventTable[eventA][eventB] == 1 이면, eventA가 B보다 먼저 일어난 것이고, eventTable[eventB][eventA] == 1 이면, eventB가 A보다 먼저 일어난 것이고, eventTable[eventA][eventB] == 0 이면, 둘 사이에는 아무런 관계가 없는 것입니다. 코드: github.com/cottory/algorithm/blob/master/BOJ/BOJ1613.cc 2020. 9. 11. [BOJ]1865번: 웜홀 www.acmicpc.net/problem/1865 라이님 블로그(blog.naver.com/kks227/220796963742)의 풀이를 참고하여 해결했습니다. 임의의 정점에 대해 모두 벨만포드를 돌 수 없으므로 그래프를 BFS 탐색을 통해 컴포넌트로 나눠주고, 각 각의 컴포넌트에 대해서만 한 번씩 벨만포드를 돌면 됩니다. 하나의 컴포넌트라도 컴포넌트내에 음의 싸이클이 있다면 YES, 아니면 NO를 출력하면 됩니다. 코드: github.com/cottory/algorithm/blob/master/BOJ/BOJ1865.cc 2020. 9. 11. [BOJ]16947번: 서울 지하철 2호선 www.acmicpc.net/problem/16947 DFS/BFS 문제입니다. 싸이클 판별만 잘 하게 되면 DFS로 탐색하든 BFS로 탐색하든 상관없습니다. 싸이클 내부에 있는 노드의 성질은 자기 자신에게 들어오는 간선이 최소 1개이상 입니다. 이 점을 활용하여 그래프를 입력받을 때 1. 자기 자신에게 들어오는 노드를 세주기 2. 싸이클의 후보가 아닌 노드를 제거하면서 그 노드과 연결되어 있는 노드의 간선 갯수를 하나씩 빼줍니다. 3. 이렇게 갱신을 하다가 더 이상 갱신되지 않으면 남아있는 노드들은 전부 싸이클에 속합니다. 이 점을 활용해서 순환선 내부에 있는 역을 파악하면 됩니다. 코드: github.com/cottory/algorithm/blob/master/BOJ/BOJ16947.cc 2020. 9. 9. 이전 1 ··· 20 21 22 23 24 25 26 ··· 43 다음
