문제 - 택배 화물이 각 집하장들 사이를 오갈 때, 어떤 경로를 거쳐야 하는지 정해야 함 - 이를 경로표로 정리해야 함 - 경로표에는 한 집하장에서 다른 집하장으로 최단 경로로 화물을 이동시키기 위해 가장 먼저 거쳐야 하는 집하장을 나타냄 해결방법 다익스트라 알고리즘을 활용하여 문제를 해결하였다. 다익스트라 알고리즘에 대한 설명을 아래 포스팅을 확인하면 좋을 것 같다. [알고리즘] 다익스트라 알고리즘 (Dijkstra Algorithm) 다익스트라 알고리즘 (Dijkstra Algorithm) 개념 - 특정한 한 정점(=노드)에서 출발하여 다른 모든 정점으로 가는 최단 경로를 구하는 알고리즘 - BFS와 DP를 활용한 최단경로 탐색 알고리즘 - DP를 활용 sa11k.tistory.com 다익스트라 기본..
문제 - n개의 도시, m개의 버스 - 버스는 한 도시에서 출발하여 다른 도시에 도착 - A번째 도시에서 B번째 도시까지 가는데 드는 최소 비용과 경로 출력 해결방법 다익스트라 알고리즘을 활용하여 문제를 해결하였다. 다익스트라 알고리즘에 대한 설명은 아래 포스팅을 확인하면 좋을 것 같다. [알고리즘] 다익스트라 알고리즘 (Dijkstra Algorithm) 다익스트라 알고리즘 (Dijkstra Algorithm) 개념 - 특정한 한 정점(=노드)에서 출발하여 다른 모든 정점으로 가는 최단 경로를 구하는 알고리즘 - BFS와 DP를 활용한 최단경로 탐색 알고리즘 - DP를 활용 sa11k.tistory.com 다익스트라 기본 코드를 활용하여 기본적인 문제 해결 틀을 잡았는데 이 문제에서는 경로도 함께 출력..
문제 - 방향 그래프가 주어짐 - 시작점에서 다른 모든 정점으로의 최단 경로 구하기 - 다익스트라 기본 유형 해결방법 다익스트라 알고리즘을 사용하는 기본적인 유형으로 가중치가 있는 그래프에서 최단경로를 찾는 문제였다. 주어진 간선 정보를 저장하기 위해 각 정점에서 출발하는 간선에 대한 정보를 list에 저장하였고, 각 정점에 도착할 수 있는 최단 경로의 값을 result 배열에 저장하였다. 큐에 출발점부터 이어지는 정점들 중 최단거리로 이동할 수 있도록 넣어가면서 비교하여 최단거리를 구할 수 있도록 코드를 구성하였다. 다익스트라에 대한 자세한 설명은 아래 포스팅에서 확인할 수 있다. [알고리즘] 다익스트라 알고리즘 (Dijkstra Algorithm) 다익스트라 알고리즘 (Dijkstra Algorith..
문제 - 사무실에 총 K개의 CCTV가 설치되어 있음 - CCTV는 5가지 종류 - CCTV는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있음 - 사무실에 벽이 있는데 CCTV는 벽을 통과할 수 없음 - CCTV가 감시할 수 없는 영역은 사각지대 - CCTV는 회전할 수 있는데, 항상 90도 방향으로 해야 하며, 감시하려고 하는 방향이 가로 또는 세로 방향이어야 함 - 0은 빈칸, 6은 벽, 1~5는 CCTV를 나타냄 - CCTV의 방향을 적절히 정해서, 사각 지대의 최소 크기를 구하기 해결방법 처음에는 그리디 방식으로 각 CCTV에서 감시할 수 있는 최대의 칸을 감시할 수 있도록 코드를 작성하였다. 하지만, 더 나은 방법으로 감시할 수 있는 방향이 있었다. 예를 들어 (0, 0)부터 CCTV에서..
문제 - 상근이네 집에서 맥주 한 박스 들고 출발 - 맥주 한 박스에는 맥주가 20개 들어있음 - 50미터에 한 병씩 마실 것임 (50미터 가기 직전에 맥주 한 병을 마셔야 함) - 가는 길에 맥주를 더 구매해야 할 수도 있음 - 편의점에 들렀을 때, 빈 병은 버리고 새 맥주 병을 살 수 있음 - 박스에 들어있는 맥주는 20병을 넘을 순 없음 - 편의점을 나선 직후에도 50미터를 가기 전에 맥주 한 병을 마셔야 함 - 상근이가 행복하게 목적지까지 도착할 수 있으면 "happy", 중간에 맥주가 바닥나서 더 이동할 수 없으면 "sad"를 출력 해결방법 맥주가 20병 있는데 1병 당 50미터를 이동할 수 있기 때문에 현재 좌표부터 다음 좌표(편의점 or 목적지)까지 1000미터 이내여야 이동이 가능하다. 따..
문제 - 상근이는 빈 공간과 벽으로 이루어진 건물에 갇힘 - 건물의 일부에 불이 났고, 상근이는 출구를 향해 뛰는 중 - 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나감 - 벽에는 불이 붙지 않음 - 상근이는 동서남북 인접한 칸으로 이동 가능. 1초 걸림 - 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 / 이제 불이 붙으려는 칸으로 이동할 수 없음 - 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있음 - 빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하기 - '.' : 빈공간 / '#' : 벽 / '@' : 상근이의 시작 위치 / '*' : 불 - 탈출할 수 없는 경우에는 "IMPOSSIBLE" 출력 해결방법 탈출을 위한 escape 함수와 불..
문제 - 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와 그 그림 중 넓이가 가장 넓은 것의 넓이 출력 - 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의 - 가로나 세로로 연결된 것은 연결이 된 것 - 대각선으로 연결이 된 것은 떨어진 그림 - 그림의 넓이란 그림에 포함된 1의 개수 해결방법 BFS를 활용하여 도화지를 탐색할 수 있도록 하였다. 상, 우, 하, 좌 순서로 각 위치에서 더 뻗어나갈 수 있는 위치를 탐색하였다. 뻗어나가면서 그림의 크기를 구해주었고, 최대 그림의 크기를 비교하면서 update 할 수 있도록 하였다. BFS 코드가 호출될 때는 그림 하나가 그려지는 것이기 때문에 BFS 함수 하단 부분에서 그림의 개수를 update 할 수 있도록 하였다. 코드 import java..
문제 - 이중 우선순위 큐는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있음 - 차이점은 데이터를 삭제할 때 연산 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 것 - 각 줄에 연산을 나타내는 문자('D' 또는 'I')와 정수 n이 주어짐 - 'I n'은 정수 n을 큐에 삽입하는 연산 (동일한 정수가 삽입될 수 있음) - 'D 1'는 큐에서 최댓값 삭제 / 'D -1'는 큐에서 최솟값 삭제 (최댓값, 최솟값이 둘 이상인 경우 하나만 삭제 됨) - 큐가 비어있는데 적용할 연산이 'D'라면 무시 가능 - 모든 연산을 처리하고 최종적으로 큐에 저장된 데이터 중 최댓값과 최솟값 출력 해결방법 TreeMap 자료 구조를 활용하여 문제를 해결하였다. 숫자와 해당 숫자가..