나그네

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 풀이 한 정점에서 다른 모든 정점까지 가는 최단 경로, 즉 최소 비용을 구하면 되는 문제다. 최소 비용을 구하는 알고리즘은 다익스트라 알고리즘과 벨만포드 알고리즘이 있는데 이 문제에선 음의 가중치가 없기 때문에 다익스트라 알고리즘을 사용해 풀 수 있다. 다익스트라 알고리즘에 대한 설명은 아래 링크를 참고하길 바란다. [다익스트라 알고..

1260번: DFS와 BFS 문제 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 풀이 dfs와 bfs의 기본 사용 방법을 연습할 수 있는 문제다. 간선이 양방향이므로 x, y를 입력받아 graph[x][y] = 1, graph[y][x] = 1로 해준다. 시작 정점부터 dfs를 돌리면 방문처리를 한 후 정점에서 연결된 위치가 아직 방문하지 않았다면 해당 정점으로 dfs를 다시 진행한다. 이를 반복하여 계속..

1012번: 유기농 배추 문제 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 풀이 잘 알려진 bfs 문제. M×N 배열을 모두 돌면서 값이 1인 동시에 아직 방문하지 않은 점들에 대해 bfs를 시행한다. bfs에선 해당 좌표를 방문처리한 후 상하좌우를 하나씩 체크하며 값이 1인 동시에 아직 방문하지 않았다면 큐에 추가해 준다. 위 방법을 큐가 빌 때까지 반복한다. bfs를 한 번 진행하면 인접해있는 모든 배추는 방문하게 되므로, bfs를 진행한 횟수가 정..