나그네

10282번: 해킹 문제 https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 풀이 의존성이 있는 컴퓨터에 바이러스가 전염되는 시간과 몇 대의 컴퓨터가 감염되었는지 구하는 문제다. 다익스트라 알고리즘으로 풀 수 있다. 다익스트라 알고리즘에 대해 잘 모른다면 아래 링크를 통해 알아보자. [다익스트라 알고리즘 알아보기] !! 신경 쓸 점이 두 가지 있다. 1. 테스트 케이스가 여러 개이므로 배열과 변수 초기화에 신경 써야 한다. 2. a가 b에 의존하고 있..

5972번: 택배 배송 문제 https://www.acmicpc.net/problem/5972 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net 풀이 양방향 그래프에서의 다익스트라 알고리즘을 사용하면 풀 수 있다. 다익스트라 알고리즘에 대해 잘 모른다면 아래 링크를 통해 알아보자. [다익스트라 알고리즘 알아보기] 코드 #include using namespace std; #define INF 2147483647 int N, M; vector graph[50001]; vector dist(50001, INF), visit..

11779번: 최소비용 구하기 2 문제 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 풀이 최소비용 구하기(1916번) 문제에서 확장된 문제다. 풀이는 아래 링크 참고. https://khyunx.tistory.com/71 [백준 / BOJ] C++ 1916 최소비용 구하기 1916번: 최소비용 구하기 문제 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에..

1916번: 최소비용 구하기 문제 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 풀이 다익스트라 알고리즘으로 쉽게 풀 수 있는 문제다. 다익스트라 설명은 아래 링크를 참고하면 된다. [다익스트라 알고리즘 알아보기] 코드 #include using namespace std; #define INF 2147483647 int main() { ios::sync_with_stdio(false); cin.tie(NULL..

1504번: 특정한 최단 경로 문제 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 풀이 정점 1에서 출발해 특정한 두 정점 v1, v2를 지나 정점 N에 도착하는 최단 거리를 출력하는 문제다. 다익스트라 알고리즘을 사용해 풀 수 있으며 양방향 그래프임을 기억하고 풀어야 하며 경로가 없는 경우 예외 처리 하는 게 힘들었다. 다익스트라 알고리즘에 대해 잘 모른다면 아래 링크를 참고하자. [다익스트라 알..

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 풀이 1부터 N까지 각 마을에 사는 학생이 X번째 마을에 갔다가 돌아오는 최단 거리가 가장 오래 걸리는 학생의 이동 거리를 구하는 문제다. 다익스트라 알고리즘을 이용하면 해결할 수 있다. 다익스트라 알고리즘에 대해 잘 모른다면 아래 링크를 참고하자. [다익스트라 알고리즘 알아보기] 이 문제는 유향인 그래프이고 i 정점부터 출발해 X 정점까지 가..

다익스트라 알고리즘(Dijkstra's Algorithm) 다익스트라 알고리즘은 시작 정점에서 모든 나머지 정점까지의 최단거리(cost)를 구하는 알고리즘 중 하나다. 주로 주어진 두 노드 사이의 최단거리(cost)를 구하는 데 유용하게 사용된다. 다익스트라 알고리즘 특징 정점의 개수가 V, 간선의 개수를 E일 때 O(ElogV)의 시간복잡도를 가진다. 모든 거리(cost)가 음수가 아닐 때만 사용할 수 있다. 우선순위 큐(최소 힙)를 사용한다. 다익스트라 알고리즘 작동 방식 아직 방문하지 않은 정점들 중 거리(cost)가 가장 작은 정점을 하나 선택해 방문한다. 해당 정점에 인접하고 아직 방문하지 않은 정점들의 거리를 갱신한다. 모든 정점을 방문하면 종료한다. 1번 과정을 위해 우선순위 큐(최소 힙)가..

1753번: 최단경로 문제 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 풀이 한 정점에서 다른 모든 정점까지 가는 최단 경로, 즉 최소 비용을 구하면 되는 문제다. 최소 비용을 구하는 알고리즘은 다익스트라 알고리즘과 벨만포드 알고리즘이 있는데 이 문제에선 음의 가중치가 없기 때문에 다익스트라 알고리즘을 사용해 풀 수 있다. 다익스트라 알고리즘에 대한 설명은 아래 링크를 참고하길 바란다. [다익스트라 알고..