개발하는 고라니

1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net [BFS or Dijkstra] 백준 문제 시리즈 중 '벽 뚫고 이동하기'와 비슷한 유형의 문제이다. 최대 k번의 나이트(Knight) 이동을 이용해 (1, 1)에서 (r, c)로 최소한의 이동으로 가는 이동 횟수를 구하는데, 다익스트라나 BFS 둘 다 가능하지만, 다익스트라를 이용한 장점이 없으므로 BFS를 이용한 것이 400ms정도 더 빨랐다. (사실 동일한 코드이고, Queue를 쓰면 BFS, 우선순위 큐를 쓰면 다익스트라로 변신한다.) 현..

9376번: 탈옥 상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다. 평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타 www.acmicpc.net [Dijkstra * 3] 발상의 전환이 필요한 문제라고 생각된다. 문제에서 죄수 2명이 등장하여 이 2명이 여는 문의 개수를 세려고 하니, 잡아야 할 문제점이 잡히지 않았다. 그래서 여러 사람들이 사용한 제 3의 인물을 등장시켜 3명이 문을 여는 것으로 문제를 풀었다. 죄수 2명은 감옥 안에 주어지고, 제 3의 인물 상근이는 (0, 0)에서 시작한다. 이 3명은 모두 다익스트라 (BFS로 해도 무관하다고 생각됨)를 이용해 모든 문을 열고, 각 지점마다 몇 개의 문을 열고 ..

5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net [다익스트라 알고리즘 + DFS 또는 BFS] 이 문제를 풀기 위해선 다음과 같은 작업을 해야한다. 1. start -> end의 최단 경로 구하기 2. 최단 경로 제거하기 3. 다시 최단경로 구하기 1, 3번 같은 경우는 그냥 다익스트라를 이용하면 되나, 2번이 조금 까다로울 수 있다. 방법은 DFS나 BFS를 이용해 최단 경로를 제거하는 방법인데, 우선 최단 경로를 추가적인 인접 리스트 같은 곳에 저장해두도록 한다. //다익스트..

13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net # 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장..

1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net # 문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다. 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다...

최단 경로 최단 경로 문제에서 입력 그래프의 유형은 크게 두 가지이다. 모든 간선 가중치가 음이 아닌 경우 음의 가중치가 존재하는 경우 음의 가중치를 허용하지 않는 경우 다익스트라(Dijkstra) 알고리즘으로 이 유형의 문제를 푼다. 음의 가중치를 허용하는 경우 벨만-포드 알고리즘으로 이 유형의 문제를 푼다. 음의 가중치는 허용하지만 가중치 합이 음수인 사이클은 절대 허용하지 않는다. 음의 사이클이 있으면 해당 사이클을 몇번이고 돌아 경로의 가중치 합을 무한정 낮출 수 있기 때문에 최단 경로 문제 자체가 성립하지 않는다. Dijkstra 알고리즘 다익스트라 알고리즘은 하나의 시작 정점에서 다른 모든 정점까지 최단 경로를 구한다. 다만 이 때 음의 가중치를 갖는 간선은 허용하지 않는다. 임의의 두 정점 ..