https://www.acmicpc.net/problem/15961 15961번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net 🏗️ 설계 슬라이딩 윈도우 기법을 활용하여 접시들을 탐색하며 Map에 저장하고, 매 탐색마다 Map의 Size를 갱신하는 방식으로 문제를 풀이하였습니다. 📋 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.ut..
알고리즘 문제풀이/백준
https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 🏗️ 설계 각 칸에 물이 도달하는 시간을 저장하는 시간 배열을 BFS를 통해서 작성합니다 이후 고슴도치는 이동할 수 있는 칸을 탐색하여, 최소 시간에 비버의 소굴로 이동할 수 있는 방법을 BFS를 통해 탐색하도록 하였습니다. 📋 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import..
https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 🏗️ 설계 기본적인 탐색 방법은 BFS를 사용하였습니다. 하지만 Queue만 사용하는 기본적인 BFS와 달리 door들을 저장하는 다른 2차원 리스트를 하나 만들어, 탐색 중 만나는 door들은 이 리스트에 저장해 두고, door를 열 수 있는 key를 보유하고 있을 경우에 door들을 Queue에 넣어주는 방식으로 설계하였습니다. 📋 코드 import java.io.BufferedReader; import ..
https://www.acmicpc.net/problem/5972 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net 🏗️ 설계 입력받은 헛간 사이의 정보를 이용해 다익스트라 알고리즘을 통해서 헛간 사이에 위치한 소들을 최소한으로 만날 수 있는 경로를 탐색하도록 하였습니다. 📋 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class BOJ_5972 ..
https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 🏗️ 설계 입력 받은 board에서 각 행/열 별로 탐색하며 정의된 로직에 의해 지나갈 수 있는 길인지의 여부를 판별하도록 하였습니다. 📋 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BOJ_14890 { pub..
https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 🏗️ 설계 입력 받을 때 섬인 부분은 -1로 설정해 두고, 이후 BFS를 이용해 섬의 인덱스를 채워주는 방식으로 섬에 번호를 매겨줍니다. 섬 이후 바다가 나오는 지점부터 바다가 2개 이상 연결되어 있고, 이후 다시 섬이 나오는 경우들을 탐색하며, 인접 행렬로 섬과 섬 사이의 다리의 길이를 저장하였습니다. 다리의 길이를 저장해 둔 인접 행렬을 이용하여 Prim 알고리즘을 이용해..
https://www.acmicpc.net/problem/2157 2157번: 여행 첫째 줄에 N(1 ≤ N ≤ 300), M(2 ≤ M ≤ N), K(1 ≤ K ≤ 100,000)가 주어진다. K는 개설된 항공로의 개수이다. 다음 K개의 줄에는 각 항공로에 대한 정보를 나타내는 세 정수 a, b, c(1 ≤ a, b ≤ N, 1 ≤ c ≤ 1 www.acmicpc.net 🏗️ 설계 도시의 인덱스가 작아지는 경우는 존재하지 않기 때문에 DP를 이용해서 현재 위치하고 있는 도시에서 다른 도시로 이동할 수 있는 경우를 방문한 도시의 수, 이동할 도시의 번호의 정보를 인덱스로 사용하는 DP에 기내식 점수를 담아가며 문제를 풀이하였습니다. 📋 코드 import java.io.BufferedReader; impo..
https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 🏗️ 설계 이분 탐색을 통해서 cost를 선택하고, cost가 선택되었을 때 이 cost로 공장 A에서 공장 B까지 움직일 수 있는 경로가 있는지 판단하였습니다. (BFS를 이용) 움직일 수 있는 경로가 있다면 left값을 mid + 1로, 없다면 right를 mid - 1로 범위를 절반 씩 줄여가며, 최대 cost를 구하는 방법으로 풀이..
