문제 https://www.acmicpc.net/problem/2151 2151번: 거울 설치 첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 www.acmicpc.net 풀이 3차원 방문체크를 활용한 Dijkstra 풀이 문제이해 문제를 읽고 예제를 보고 이해를 하려는데 개인적으로 상당히 난해했음. 일단 동작과정은 아래와 같음. #이라는 문에 대해서 어느 방향에서든 출발해도 상관없음. 빈칸 ‘.’에 대해 진행방향 그대로 직진만 가능. ‘!’ 칸은 거울 설치 가능한 곳으로써 해당 자리에 거울을 45도 설치 가능. 거울을 설치하게 되면 빛은 직진이 ..

문제 https://www.acmicpc.net/problem/21940 21940번: 가운데에서 만나기 위 조건을 만족하는 도시 $X$의 번호를 출력한다. 만약 가능한 도시 $X$가 여러 개인 경우는 도시의 번호를 오름차순으로 출력한다. www.acmicpc.net 풀이 모든 정점으로부터 다른 모든 정점까지의 거리를 구하는 문제로써 플로이드 워셜 풀이가 가능 하지만 나는 데이크스트라로 풀이함 최초 접근 주어지는 K개의 노드를 출발점으로 하여금 데이크스트라를 수행하면서 전역 dp배열에 최대 비용을 기록 후 갈 수 있는 노드들에 대해 탐색하여 왕복시간을 구하려함. 하지만 이렇게 풀이하게 될 경우 왕복시간을 구할수가 없기 때문에 잘못된 풀이. 접근법 주어지는 K로부터 모든 노드에 대해 왕복시간을 구하고 모두..

Concept 그리디 알고리즘의 한 분류 다이나믹 프로그래밍 메모이제이션 기법 활용 부분 문제 : 한 정점까지의 최단거리는 방문하는 여러개의 정점들의 최단거리로 이루어져있음. 주어지는 그래프에서 시작 정점으로부터 각 정점까지의 최단경로를 찾는 알고리즘 Feature 우선순위 큐와 거리배열(DP)을 활용하여 로직 구성. 한 정점 V까지의 최단거리를 구할 때 V까지로 가는 여러 정점들의 최단 거리 정보를 활용한다는 특징을 가짐. 가중치를 가진 그래프에서 최단거리를 구할 때 쓰이는 알고리즘 음수 가중치를 가진 그래프에서는 사용불가. 우선순위 큐를 활용함으로써 시간복잡도 : O(N * NlogN) Implement 인접 리스트를 통한 구현 우선 데이크스트라 소스코드를 보자. private static int d..