❓문제https://www.acmicpc.net/problem/1976성능 요약메모리: 32412 KB, 시간: 40 ms분류그래프 이론, 자료 구조, 그래프 탐색, 분리 집합 문제 설명동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 수 있다.도시들의 개수와 도시들 간의 연결 여부가 주어져 있고, 동..

❓문제https://www.acmicpc.net/problem/1717성능 요약메모리: 77876 KB, 시간: 284 ms분류자료 구조, 분리 집합문제 설명초기에 n+1n+1개의 집합 {0},{1},{2},…,{n}{0},{1},{2},…,{n}이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.집합을 표현하는 프로그램을 작성하시오.✍🏻풀이https://yoongrammer.tistory.com/102 서로소 집합(Disjoint Set) & 유니온 파인드(Union find)목차서로소 집합(Disjoint Set) & 유니온 파인드(Union find)서로소 집합(Disjoint Set)Disjoint Set(서로소 집합, 분리 집합)이란 서로..

❓문제https://www.acmicpc.net/problem/1197성능 요약Kruskal, Python3➡️메모리: 57288 KB, 시간: 264 msPrim, PyPy3➡️메모리: 129144 KB, 시간: 380 ms분류최소 스패닝 트리, 그래프 이론문제 설명그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.✍🏻풀이2024.11.29 - [Computer Science/Algorithms] - [Algorithms] 최소 신장 트리 (Minimum Spanning Tree) [Algorithms] 최소 신장 트리 (Minimum Spannin..

❓문제https://www.acmicpc.net/problem/13549성능 요약메모리: 115084 KB, 시간: 232 ms분류그래프 이론, 그래프 탐색, 너비 우선 탐색, 최단 경로, 데이크스트라, 0-1 너비 우선 탐색 문제 설명수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시..

❓문제https://www.acmicpc.net/problem/11657성능 요약메모리: 34456 KB, 시간: 788 ms분류그래프 이론, 최단 경로, 벨만–포드문제 설명N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C 1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.✍🏻풀이벨만 포드 알고리즘을 사용한다. 사이클을 확인은 아래 사이트를 참고하면 된다.https://growth-coder.tistory.com/2..

❓문제https://www.acmicpc.net/problem/1504성능 요약메모리: 126204 KB, 시간: 376 ms분류그래프 이론, 최단 경로, 데이크스트라문제 설명방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.✍🏻풀이우선 주어진..