4Legs_Archives

[서론] 그래프 최단경로 알고리즘으로, 꽤 자주 보이는 유형이다. 다익스트라 알고리즘은 음수가 아닌 가중치가 있는 그래프에서 한 점으로부터 다른 모든 점까지의 최단 경로를 구하는 알고리즘이다. [동작 원리] 다음과 같은 그래프에서, 1번 노드와 나머지 각 노드 간의 최단거리를 다익스트라 알고리즘을 통해 구해보자. 다익스트라 알고리즘은 위와 같은 상태에서 시작한다. 테이블의 값은 출발 노드로부터 해당 노드까지의 최소 가중치 합을 의미하며, 테이블의 값이 INF(무한대)라면 해당 노드와 연결되어 있지 않다는 의미이다. 아직은 1번 노드만 확인했으므로, 다른 모든 노드에 대해 INF가 기록된 모습이다. 출발 노드로부터 인접한 각 노드에 대해 테이블에 거리를 기록한다. 예시 그래프에서는 출발 노드 1이 2, 3..

문제 링크 : www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 문제를 봤을 때 BFS로 풀어야 하는 문제이구나! 하는 느낌은 바로 받을 수 있지만, 막상 문제를 해결하려고 하면 생각이 복잡해지는 문제이다. 출구를 향해 일단 가다가 잠긴 문을 만나면 목적지를 열쇠로 바꿔가면서 가는 방법을 제일 처음 생각해 볼 수 있다. 이 방법은 각 출구마다의 최단경로 path를 기억해 놓고, 통과해야 하는 문이 어떤 문들인지를 파악한 후에 가장..

문제 링크 : https://www.acmicpc.net/problem/16437 16437번: 양 구출 작전 2, 3, 5번에 사는 모든 양들은 1번 섬으로 갈 수 있지만 7번 섬에 사는 양들은 1번 섬으로 가기 위하여 6번 섬을 거쳐야 하는데 6번 섬에 사는 늑대들의 수가 7번 섬에 사는 양들의 수보다 많으므로 www.acmicpc.net DFS를 재귀 형태로 구현하면 쉽게 풀 수 있는 문제이다. 문제의 그래프를 인접 리스트 형내로 변환한 뒤, 한 노드에 들어올 수 있는 양의 수 = 모든 자식 노드들에 들어올 수 있는 양의 수 합 이라는 점을 이용하여 루트 노드(1번)의 최종 값을 구하면 된다. 양의 수가 음수가 될 수 없다는 것과 각 값 자료형에만 유의하면 쉽게 해결할 수 있다. [코드] 1 2 3..