프로그래밍
BOJ 6593 · 상범 빌딩
알고리즘 분류 : BFS BFS를 통해 최단 탈출 시간을 구하는 문제다. 상범 빌딩에 갇힌 사람을 빌딩 밖으로 탈출시켜야 한다. 시작점은 'S'로 주어지고, 탈출구는 'E'로 주어진다. 3차원 배열을 선언하여 빌딩의 정보를 입력받고, 이동 거리를 저장할 dist 배열을 3차원으로 선언하고 방문 체크 용도로 사용한다. 입력받을 때 시작점의 위치와 도착점의 위치를 저장해두어야 한다.이동은 인접한 '동서남북상하'로 한 칸씩만 이동할 수 있다.이동할 때 빌딩의 범위를 벗어나는지 확인해야 한다.벽(#)으로 이동할 수 없다.탈출구에 도착하면 "Escaped in x minute(s)."를 출력한다. 탈출구에 도달하지 못하면 "Trapped!"를 출력한다.여러 개의 테스트케이스가 주어지므로, 변수 초기화에 유의한다...
BOJ 4485 · 녹색 옷 입은 애가 젤다지?
알고리즘 분류 : 다익스트라 링크가 검은 루피를 먹으면서 루피를 잃으면서 이동할 때, 가장 적게 잃는 경로를 구하는 문제다. 각 칸마다 잃을 수 있는 루피는 0~9 이므로, 다익스트라 알고리즘을 통해 구현하면 된다. N X N 의 맵을 입력받고, 이를 dist 배열을 업데이트할 때 이용한다.정답은 dist[n-1][n-1]에 있으며, 이 값에 처음부터 잃는 루피인 a[0][0]을 더해주어야 한다.테스트케이스가 여러 개 주어지므로, 테스트케이스마다 dist 배열을 초기화해주어야 한다. C++ 소스코드 #include #include #include using namespace std; struct zelda { // The person wearing green clothes is Zelda, right? ..
BOJ 1504 · 특정한 최단 경로
알고리즘 분류 : 다익스트라 1부터 출발해서 정점 X와 Y를 모두 거쳐서 N에 도착하는 최단 거리를 구하는 문제다. 이동 거리가 1 이상의 값을 가지므로, 다익스트라를 이용해야 한다. 정점 두 군데를 모두 거쳐야 하므로, 다익스트라를 여러 번 호출해야 한다. 다익스트라를 여러 번 호출해야 하므로, dist 배열을 매번 INF로 초기화해야 하는 것에 유의한다. 방향성이 없는 그래프이므로, 입력받을 때 양방향으로 저장한다.X, Y를 모두 거쳐서 도착하는 방법은 2가지가 존재한다. 1 → X → Y → N 와 1 → Y → X → N 이다.1 → X, X → Y, Y → N으로 가는 방법을 경로 1이라 하고, 그 이동 거리를 저장한다.1 → Y, Y → X, X → N으로 가는 방법을 경로 2라 하고, 그 이..
BOJ 1238 · 파티
알고리즘 분류 : 다익스트라 각 학생이 각자 자신의 마을에서 출발하고, X 마을에서 파티를 하고, 다시 자신의 마을로 돌아오는 시간을 맞추는 문제다. 마을 간의 이동은 1 이상의 소요 시간이 걸리므로, 다익스트라 알고리즘을 이용해야 한다. 이 문제는 다익스트라 알고리즘을 두 번만 호출해서 해결할 수 있다.출발의 기준을 i (1 n >> m >> x; vector a[n], b[n]; int dist[n][2]; while (m--) { int u, v, w; cin >> u >> v >> w; a[u-1].push_back({v-1, w}); b[v-1].push_back({u-1, w}); } fill(&dist[0][0], &dist[n][0], INF); dijkstra(a, dist, 0); di..
BOJ 1916 · 최소비용 구하기
알고리즘 분류 : 다익스트라 A 도시에서 B 도시까지 가는 최단 경로를 구하는 문제다. 도시 간에 비용이 0 이상의 양수 값을 지니므로, 다익스트라 알고리즘을 이용해야 한다.BOJ 1753번 '최단경로'와 유사한 문제다. 다음 글을 참조. C++ 소스코드 #include #include #include #include using namespace std; struct bus { int city, cost; bool operator t.cost; } }; int n, m; int depart, arrive; const int INF = 1e9; void dijkstra(vector a[], int dist[]) { priority_queue pq; pq.push({depart, 0}); dist[depar..
BOJ 1753 · 최단경로
알고리즘 분류 : 다익스트라 한 개의 정점에서 다른 모든 정점으로 가는 최단 경로를 구해야 한다. 이 문제는 다익스트라 알고리즘을 이용하는 대표적인 문제다. 다익스트라 알고리즘을 활용하기 위해서 최소 힙(Min-heap)을 이용하면 편하다. C++은 STL에 있는 우선순위 큐(Priority Queue)를 이용하여 최소 힙을 사용하면 된다. 단, Priority Queue가 기본적으로 최대 힙(Max-heap)이므로, 비용(cost)에 -1을 곱해서 사용하거나, 연산자 오버로딩을 통해 순서를 바꿔서 사용하면 된다.Python은 Heapq를 이용하면 된다.정점은 1~N이고, 인덱스는 0~N-1이다. 따라서, 입력받을 때 정점에 -1을 해주거나, 리스트를 N+1 길이로 선언하여 이용해야 한다. C++ 소스코..
BOJ 15658 · 연산자 끼워넣기 (2)
알고리즘 분류 : 브루트 포스 BOJ 14888번 '연산자 끼워넣기'와 거의 동일한 문제이다. 바뀐 점은 연산자의 사용 가능 횟수가 증가했다는 점이다. 구현 방법은 이전 문제를 참조. 이전 문제는 연산자의 개수가 최대 N-1개였지만, 이번 문제는 연산자의 개수가 최소 N-1개, 최대 4N개이다.연산자가 최대로 있는 경우, 연산자를 사용할 때 4개의 연산자 중에서 하나를 선택할 수 있다.따라서 N-1개의 연산자 자리에 연산자 4개 중 하나를 사용하는 경우이므로, 경우의 수는 4^(N-1) 개이다.N의 최댓값은 11이므로, 최대 경우의 수는 4^10 (약 100만)이다.따라서 이 문제는 이전 문제와 동일한 코드로 해결할 수 있다. C++ 소스코드 #include int n; int a[11], op[4]; ..
BOJ 14888 · 연산자 끼워넣기
알고리즘 분류 : 브루트 포스 재귀 함수를 이용하여 수식 연산의 최댓값과 최솟값을 구하는 문제다.주어진 연산자를 모두 사용해서 수식을 만들고, 그 수식의 연산 결과를 출력하면 된다. 재귀 함수 종료 조건 : 인덱스가 범위를 넘어선 경우 (index >= N)연산은 각 연산자의 잔여횟수가 1 이상인 경우에 수행한다. 0이면 연산을 수행하지 않는다.연산을 수행한 후, 사용한 연산자의 잔여횟수를 1회 감소시킨다. C++ 소스코드 #include int n; int a[11], op[4]; int mx = -1e9, mn = 1e9; void solve(int index, int ans, int add, int sub, int mul, int div) { if (index == n) { if (ans > mx)..