본문 바로가기

Programming/BOJ

BOJ 11965 · Bessie's Dream 알고리즘 분류 : 다익스트라빨간색(0), 분홍색(1), 주황색(2), 파란색(3), 보라색(4) 등 총 5가지 색의 타일이 있는 미로를 이동하면서 탈출해야 한다. 이미 방문했던 타일을 다시 방문할 수 있으므로, 일반적인 BFS로 최단 거리를 구하기는 까다롭다. 구현할 때, 보라색(4) 타일을 유의해야 한다.빨간색(0) 타일로는 이동할 수 없다. 다음 이동에서 0번 타일을 보면 무시한다.분홍색(1) 타일로는 이동할 수 있다. 평범한 이동을 하..
BOJ 5558 · チーズ 알고리즘 분류 : BFS쥐가 먹을 수 있는 치즈를 순서대로 먹으면서 이동하는 최단 거리를 구하는 문제다.  다음 치즈를 먹으러 이동할 때, 방문했던 곳을 다시 방문할 수 있다.치즈를 낮은 숫자부터 순서대로 먹어야 하고, 현재 먹을 수 없는 높은 숫자의 치즈는 무시하고 이동할 수 있다.위 두 가지를 잘 고려하여, BFS 탐색을 해야 한다. 우선 BFS를 통해 먹을 수 있는 치즈를 찾고, 먹은 위치와 이동 거리를&nb..
BOJ 16769 · Mixing Milk 알고리즘 분류 : 시뮬레이션1 → 2, 2 → 3, 3 → 1 (X → Y)을 순서대로 100번 해서 각 양동이에 우유가 얼마나 남았는지 확인하는 문제다. 순서대로 100번만 반복하면 된다.우선 옮기기 전에, X번 양동이에 남아있는 우유의 양과 Y번 양동이에 남아있는 우유의 양을 더해서 temp에 저장해둔다.Y번 양동이의 최대치(C)와 temp와 비교한다.temp가 C보다 크거나 같을 경우 (temp - C)를 X번 양동이..
BOJ 5719 · 거의 최단 경로 알고리즘 분류 : 다익스트라, BFS최단 경로가 아닌, 2번째로 빠른 최단 경로를 구하는 문제다. 다익스트라와 BFS를 둘 다 혼용해서 구현해야 해서 까다롭다.2가지 배열을 사용해야 한다. 첫 번째는 최단 경로를 저장할 dist 배열, 두 번째는 최단 경로를 추적하고 방문 확인용으로 사용할 check 배열이다.입력받을 때 원래 방향 벡터 a를 저장하고, 그 반대 방향 벡터 b를 저장한다.우선 다익스트라 알고리즘을 통해 최단 경로를 ..
BOJ 6593 · 상범 빌딩 알고리즘 분류 : BFSBFS를 통해 최단 탈출 시간을 구하는 문제다. 상범 빌딩에 갇힌 사람을 빌딩 밖으로 탈출시켜야 한다. 시작점은 'S'로 주어지고, 탈출구는 'E'로 주어진다. 3차원 배열을 선언하여 빌딩의 정보를 입력받고, 이동 거리를 저장할 dist 배열을 3차원으로 선언하고 방문 체크 용도로 사용한다.입력받을 때 시작점의 위치와 도착점의 위치를 저장해두어야 한다.이동은 인접한 '동서남북상하'로 한 칸씩만 이동할 수 있다.이동할 ..
BOJ 4485 · 녹색 옷 입은 애가 젤다지? 알고리즘 분류 : 다익스트라링크가 검은 루피를 먹으면서 루피를 잃으면서 이동할 때, 가장 적게 잃는 경로를 구하는 문제다. 각 칸마다 잃을 수 있는 루피는 0~9 이므로, 다익스트라 알고리즘을 통해 구현하면 된다.N X N 의 맵을 입력받고, 이를 dist 배열을 업데이트할 때 이용한다.정답은 dist[n-1][n-1]에 있으며, 이 값에 처음부터 잃는 루피인 a[0][0]을 더해주어야 한다.테스트케이스가 여러 개 주어지므로, 테스트케이스마..
BOJ 1504 · 특정한 최단 경로 알고리즘 분류 : 다익스트라1부터 출발해서 정점 X와 Y를 모두 거쳐서 N에 도착하는 최단 거리를 구하는 문제다. 이동 거리가 1 이상의 값을 가지므로, 다익스트라를 이용해야 한다. 정점 두 군데를 모두 거쳐야 하므로, 다익스트라를 여러 번 호출해야 한다. 다익스트라를 여러 번 호출해야 하므로, dist 배열을 매번 INF로 초기화해야 하는 것에 유의한다.방향성이 없는 그래프이므로, 입력받을 때 양방향으로 저장한다.X, Y를 모두 거쳐서 도착하는&n..
BOJ 1238 · 파티 알고리즘 분류 : 다익스트라각 학생이 각자 자신의 마을에서 출발하고, X 마을에서 파티를 하고, 다시 자신의 마을로 돌아오는 시간을 맞추는 문제다. 마을 간의 이동은 1 이상의 소요 시간이 걸리므로, 다익스트라 알고리즘을 이용해야 한다.이 문제는 다익스트라 알고리즘을 두 번만 호출해서 해결할 수 있다.출발의 기준을 i (1<=i<=N)로 두는 것이 아니라, 출발을 X로 둬서, X → i 와 X ← i 라..
BOJ 1916 · 최소비용 구하기 알고리즘 분류 : 다익스트라A 도시에서 B 도시까지 가는 최단 경로를 구하는 문제다. 도시 간에 비용이 0 이상의 양수 값을 지니므로, 다익스트라 알고리즘을 이용해야 한다.BOJ 1753번 '최단경로'와 유사한 문제다. 다음 글을 참조.C++ 소스코드#include <iostream> #include <queue> #include <vector> #include <algorithm> using namespa..
BOJ 1753 · 최단경로 알고리즘 분류 : 다익스트라한 개의 정점에서 다른 모든 정점으로 가는 최단 경로를 구해야 한다. 이 문제는 다익스트라 알고리즘을 이용하는 대표적인 문제다. 다익스트라 알고리즘을 활용하기 위해서 최소 힙(Min-heap)을 이용하면 편하다.C++은 STL에 있는 우선순위 큐(Priority Queue)를 이용하여 최소 힙을 사용하면 된다. 단, Priority Queue가 기본적으로 최대 힙(Max-heap)이므로, 비용(cost)에 -1을 ..
BOJ 15658 · 연산자 끼워넣기 (2) 알고리즘 분류 : 브루트 포스BOJ 14888번 '연산자 끼워넣기'와 거의 동일한 문제이다. 바뀐 점은 연산자의 사용 가능 횟수가 증가했다는 점이다. 구현 방법은 이전 문제를 참조.이전 문제는 연산자의 개수가 최대 N-1개였지만, 이번 문제는 연산자의 개수가 최소 N-1개, 최대 4N개이다.연산자가 최대로 있는 경우, 연산자를 사용할 때 4개의 연산자 중에서 하나를 선택할 수 있다.따라서 N-1개의 연산자 자리에 연산자 4개 중 하나를 사용하는 경우..
BOJ 14888 · 연산자 끼워넣기 알고리즘 분류 : 브루트 포스재귀 함수를 이용하여 수식 연산의 최댓값과 최솟값을 구하는 문제다.주어진 연산자를 모두 사용해서 수식을 만들고, 그 수식의 연산 결과를 출력하면 된다. 재귀 함수 종료 조건 : 인덱스가 범위를 넘어선 경우 (index >= N)연산은 각 연산자의 잔여횟수가 1 이상인 경우에 수행한다. 0이면 연산을 수행하지 않는다.연산을 수행한 후, 사용한 연산자의 잔여횟수를 1회 감소시킨다.C++ 소스코..