그래프 이론10 [Python] 백준 18223번 : 민준이와 마산 그리고 건우 https://www.acmicpc.net/problem/18223 18223번: 민준이와 마산 그리고 건우 입력의 첫 번째 줄에 정점의 개수 V와 간선의 개수 E, 그리고 건우가 위치한 정점 P가 주어진다. (2 ≤ V ≤ 5,000, 1 ≤ E ≤ 10,000, 1 ≤ P ≤ V) 두 번째 줄부터 E개의 줄에 걸쳐 각 간선의 정보 www.acmicpc.net 💡 문제 풀이 다익스트라 알고리즘 문제이다. 문제를 처음 읽으면 최단 경로에 건우가 있는지 따져야 할 것만 같지만 이 문제는 단순히 최소 비용만 따지면 된다. 마산까지의 최소 비용과 (시작 지점부터 건우가 있는 곳까지의 비용 + 건우가 있는 곳부터 마산까지의 비용)이 같다면 최단 경로의 길이보다 길어지지 않는 것이므로 건우를 구해서 마산으로 가도.. 2022. 8. 29. TIL : 플로이드-워샬(Floyd-Warshall) 알고리즘 (8) 💻 알고리즘 📌 플로이드-워샬 알고리즘이란? 그래프 이론 중 하나로 다익스트라 알고리즘과 비슷하게 노드와 노드 사이의 최단거리를 구하는 알고리즘이다. 이 알고리즘의 특징과 동작 원리는 다음과 같다. ✔️ 특징 모든 노드 간의 최단거리를 구한다. 따라서 2차원의 공간이 필요하다. 음의 비용을 가지는 그래프에서도 사용할 수 있다. O(n^3)의 시간복잡도를 가진다. (3중 반복문) 다이나믹 프로그래밍의 성질을 가진다. ✔️ 동작 원리 거쳐 가는 노드를 기준으로 알고리즘이 수행한다. a → b의 비용과 a → k → b의 비용을 비교해서 더 작은 비용으로 최신화한다. INF = int(1e9) # 정점과 간선 개수 입력 vertex, edge = map(int, input().split()) # 그래프 초기화.. 2022. 8. 17. [Python] 백준 1976번 : 여행 가자 https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 💡 문제 풀이 그래프 이론 중 Union-Find 문제이다. union 함수와 find 함수를 구현할 수 있다면 쉽게 풀 수 있다. 입력받은 값들에 대해서 각 node별로 연결해주고 여행 계획에 맞춰 find 함수를 사용해 1개의 값으로 귀결된다면 YES를, 아니라면 NO를 출력해주면 된다. ✔️ 느낀 점 union-find 알고리즘에 대해서 제대로 이해를 못 해서 낯설었던 문제였다. 새로운 알고.. 2022. 8. 7. [Python] 백준 1516번 : 게임 개발 https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 💡 문제 풀이 위상 정렬 문제이다. 다른 위상 정렬과 다르게 DP와 같이 들어가 있는 문제이다. 주의해야 할 점은 어떤 건물을 건설할 때 요구하는 건물들이 다 완공되어야 한다. 즉, (가장 마지막에 건설한 건물의 시간) + (어떤 건물 건설 시간)이 더해진 값이 총 건설 시간이다. ✔️ 느낀 점 위상 정렬에 익숙해지고 있는데 이런 복합적인 문제가 나와서 너무 좋았다. 그리고 역시 DP는.. 2022. 8. 5. [Python] 백준 2252번 : 줄 세우기 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 💡 문제 풀이 위상 정렬 문제이다! 위상 정렬을 구현해주면 된다 ㅎㅎ ✔️ 느낀 점 💻 코드 import sys input = sys.stdin.readline N, M = map(int, input().split()) graph = [[] for _ in range(N+1)] indegree = [0] * (N + 1) for _ in range(M):.. 2022. 8. 4. [Python] 백준 1238번 : 파티 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 💡 문제 풀이 그래프 이론 중 다익스트라 알고리즘 문제이다. 기본적인 다익스트라 알고리즘과 형태가 비슷하지만 주의할 점이 있다. 바로, 원하는 값이 특정 노드에서 목적지로의 거리 + 목적지부터로의 거리라는 점이다. 구현한 다익스트라 알고리즘은 출발지로부터 모든 정점에 대해서 최단 거리를 구해준다. 따라서 최단 거리를 저장하는 배열을 2개를 구현해서 최대 거리를 찾아준.. 2022. 8. 2. 이전 1 2 다음
