백준 알고리즘44 [BOJ]9205번: 맥주 마시면서 걸어가기 www.acmicpc.net/problem/9205 그래프 탐색문제입니다. 상근이네 집 -> 페스티벌 장소까지 중간에 편의점을 경유하든 안하든 도달할 수 있는지 묻습니다. 한 장소에서 맥주를 20개까지 충전가능하기에 정점과 정점사이의 거리가 1000m 이하일 때만 이동 가능합니다. 바꿔말하면, 1. 플로이드 알고리즘을 통해 정점과 정점 사이의 거리를 모두 구하기 2. BFS를 돌면서 상근이네 -> 페스티벌 장소까지 이동가능 여부 판단 위 두 가지 과정을 거치면 됩니다. 다음 노드를 큐에 넣을 수 있는지 판별여부는 현재 노드와 다음 노드의 거리가 1000m 이하인지 체크하면됩니다. 코드: github.com/cottory/algorithm/blob/master/BOJ/BOJ9205.cc 2020. 9. 13. [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]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 2 3 4 5 6 ··· 11 다음
