두부의 코딩일기

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 ✅ 골드 Ⅲ 🔶 풀이 각 각의 마을에서 파티가 열린 마을 X를 방문했다가 다시 돌아왔을 때 가장 많이 시간을 소비한 학생을 구하라. 모든 가중치가 양수이고, 한 정점에서 다른 모든 정점까지의 최단 거리를 구해야하므로 다익스트라. 다익스트라를 두 번 나누어서 해결했다. 1. X에서 각 마을까지의 최단 거리 2. 각 마을에서 X까지의 최단 거리 (역방향) 위 두가지를 구..

https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 🔶 풀이 오랜만에 나온 다익스트라 문제. 완전 탐색으로 풀려고 했지만 시간 초과가 발생할 것 같아서 다른 방향을 생각해 봄. bfs와 다익스트라 알고리즘을 헷갈려하시는 분들이 있는 것 같은데 큰 차이점은 그래프의 가중치 유무와 dp 활용이다. 두 가지 알고리즘 모두 최단 거리를 찾는 알고리즘이지만 그래프의 가중치가 생기면 다익스트라 알고리즘을 사용하는 것이 좋다. 또한, 그래프의..

https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 🔶 풀이 유니온-파인드 문제. 1 → 3 으로 가려고할 때, 바로 연결되어있지 않아도 1 → 2 → 3 이 연결되어있다면 갈 수 있다. 즉, 가고자하는 경로가 쭉 이어져있으면 여행이 가능하다는 뜻이다. 유니온-파인드에 대해서 처음 접하신 분들은 아래 링크를 보고 오는 것을 추천한다. 유니온-파인드를 이용한 대표적인 알고리즘을 설명하고있다. 최소 비용 신장 트리(MST), 크루스칼 알고리즘(Krus..

https://www.acmicpc.net/problem/20926 20926번: 얼음 미로 탐험가 테라는 얼음 미로에 갇혔다. 얼음 미로의 바닥은 빙판으로 되어 있어 발을 내디디면 바위에 부딪힐 때까지 미끄러진다. 예를 들어, 위 그림에서 테라가 왼쪽 방향으로 이동한다면 중간에 www.acmicpc.net 풀이 포켓몬 얼음동굴이 생각나는 다익스트라 문제. 테라, 바위, 구멍, 출구가 char형이라서 int형으로 임의의 값을 줘서 int형 배열로 선언했다. static int Rock = 100, Hole = -1, Escape = 200, W, H; for (int i=0; i= W) break; if (map[nx][ny] == Hole) break; if (map[nx][ny] == Rock) { ..

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 풀이 전형적인 다익스트라 알고리즘 문제. 최단경로 응용 문제로 진행 과정을 자세하게 적어뒀다. 다익스트라에 대해서 처음 접하시는 분은 아래 링크를 먼저 읽어보는 걸 추천한다. https://sookr5416.tistory.com/160 자바 다익스트라(Dijkstra) 알고리즘 정의 및 작동 원리 다익스트라 알고리즘 (Dijkstra) 정의 음의 가중치..

https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 풀이 위 문제는 최소 스패닝 트리 문제로 해결 방법은 프림, 크루스칼 두 가지가 존재한다. 필자는 두 가지 방법에 대해서 잘 모르는 상태였고, 해당 알고리즘 해결법을 먼저 숙지한 다음에 다시 문제에 접근했다. 우선, 크루스칼을 이용해서 문제를 해결했으며 해당 내용을 모른다면 아래를 참고하는 걸 추천한다. 자바 최소 비용 신장 트리(MST), 크루스칼 ..

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 풀이 전형적인 다익스트라 알고리즘 문제이다. dp와 bfs를 이용해서 한 노드에서 모든 노드로 가는 최단거리를 구할 수 있다. 다익스트라에 대해서 잘 모르면 아래 링크를 먼저 보는 걸 추천한다. 자바 다익스트라(Dijkstra) 알고리즘 정의 및 작동 원리 다익스트라 알고리즘 (Dijkstra) 정의 음의 가중치가 없는 그래프의 한 노드에서 각 모든 노드까지의..

https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 풀이 이번 문제는 최소 비용 신장 트리 (MST) 유형의 문제이다. 해결 방법으로는 크루스칼 알고리즘과 프림 알고리즘이 있다. 필자는 사실 크루스칼 알고리즘을 처음 들어본다. 그래서 한 번 정리해봤다. 자바 최소 비용 신장 트리(MST), 크루스칼 알고리즘(Kruskal Algorithm) 정의 크루스칼 알고리즘 (Kruskal Algorithm) 정의 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘으로 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘 중 하나이다...