문제 링크 https://www.acmicpc.net/problem/13911 13911번: 집 구하기 첫줄에는 정점의 개수 V(3 ≤ V ≤ 10,000)와 도로의 개수 E(0 ≤ E ≤ 300,000)가 주어진다. 그 다음 E줄에 걸쳐 각 도로를 나타내는 세 개의 정수 (u,v,w)가 순서대로 주어진다. 이는 u와 v(1 ≤ u,v ≤ V)사 www.acmicpc.net 문제 풀이 - 다익스트라 알고리즘 - 맥세권과 스세권을 만족하는 최소 최단 거리 합 구하는 문제 (없는 경우 -1 출력) - 맥도날드와 스타벅스 각각 시작점으로 최단 경로 구할 경우 시간 초과 발생 가능 - MultiSource BFS 아이디어 응용해서 총 2번 다익스트라 실행 ① 모든 맥도날드를 시작점으로 집까지의 최단 거리 ② 모..

문제 링크 https://www.acmicpc.net/problem/2211 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다 www.acmicpc.net 문제 풀이 - 다익스트라 + 백트래킹 - 양방향 그래프 - N(노드) 최대 1,000, C (비용) 최대 10 이므로 최대치는 10,000이므로 int로 처리가능 - 루트 노드가 1번일 때, 다른 노드를 모두 연결하기 위해서는 N - 1개의 간선이 필요하다 (트리 생각하기!) - 최단 경로를 갱신하면서 parent 배열에 이전 노드에 대한 정보 기록 (pare..

문제 링크 https://www.acmicpc.net/problem/21278 21278번: 호석이 두 마리 치킨 위의 그림과 같이 1번과 2번 건물에 치킨집을 짓게 되면 1번부터 5번 건물에 대해 치킨집까지의 왕복 시간이 0, 0, 2, 2, 2 로 최소가 된다. 2번과 3번 건물에 지어도 동일한 왕복 시간이 나오지만 더 www.acmicpc.net 문제 풀이 다익스트라 풀이 건물 중 두 개를 뽑는 조합을 구하고 다익스트라 알고리즘으로 최단 거리를 구한다. - N : 건물의 개수, 노드 수, 최대 100 - M : 도로의 개수, 간선 수, 최대 N * (N-1)/2 = 4950 - 100개의 건물 중 2개를 뽑는 조합 : 100C2 = 100 * 99 / 2! = 4950 - 다익스트라 알고리즘 시간 ..

문제 링크 https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 문제 풀이 - 다익스트라 알고리즘 - 시간복잡도 : O(ElogV) - s에서 출발하여 주어진 경로 g-h, h-g를 거쳐 최단 거리로 의심되는 노드에 도착하는지 파악하고, 경로를 거쳐 도착했을 경우 형식에 맞춰 출력하는 문제 처음 2차원 배열(int[][] dist = new int[노드][2]) 로 하여 풀이 하였는데 틀렸다 - 0번 인덱스에는 경로(g - h, h-g)를 거치..

문제 링크 https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 문제 풀이 - 다익스트라 알고리즘, bfs 수행하면서 방향 전환시 같은 방향이 아닌 경우 거울을 하나씩 추가한다 - 두 점을 이으면서 거울의 최소값을 구하면 되는 아주 Simple한 문제인 줄 알았으나 .. 중복 방문 처리에 대한 예외 케이스가 있었다 아래 예외 케이스를 참고하도록 하자 https://www.acmicpc.net/board/view/109356 글 읽기 - 데이..