'ㅅ'
-
[알고리즘] BOJ 3197 백조의 호수 (JAVA)
https://www.acmicpc.net/problem/3197 백준 플레5 난이도의 문제로, 전형적인 bfs문제의 형태를 띄면서도 시간단축이 필요한 문제였다. 한 백조 위치에서 다른 백조 위치에 도달할 수 있는지 bfs 탐색 -> 실패 시 빙판이 녹는 과정 실행 이와 같은 순서로 구현했고, 물 녹는 과정을 실행할 때 전체 물 범위가 아닌 이전에 녹았던 지점들의 좌표값을 저장해두고 해당 좌표들에 한해 인접한 지역의 빙판이 녹는 식으로 시간 단축을 시켰다. import java.io.*;import java.util.*;public class boj3197 { static int R, C, time; static int dir[][] = { { 1, 0 }, { -1, 0 }, { 0..
알고리즘/알문풀(백준, 프로그래머스, 코드트리)
2024. 9. 16.
-
[알고리즘] BOJ 2437 저울 (JAVA)
https://www.acmicpc.net/problem/2437 백준 골드2 난이도의 문제로, 오랜만에 문제 풀면서 머리를 좀 많이 쓴 문제가 아니었나 싶다. 우선 문제를 보면, 배낭 문제와 비슷한 형태를 띄고 있다. 그래서 일단 그리디 문제라는 것은 어느 정도 유추가 가능했다. 문제를 풀기 위해 조건을 좀 찾아봤다. 우선 문제 풀면서 메모장에 적어놨던 첫번째 예시를 가져왔다. an은 무게 추가 정렬되었을 때 n번째 추를 의미하고, SN은 n번째 무게추까지의 누적 무게 합을 의미하고, 그 옆은 부분 집합을 의미한다. 위의 예시에서는 무게추가 순서대로 1,2,4,9인 순서대로 확인한다. 무게 추를 추가할때마다 누적합과 부분 집합에 해당되는 값들을 확인하면, 다음을 알 수 있다. an ..
알고리즘/알문풀(백준, 프로그래머스, 코드트리)
2024. 6. 13.
-
[알고리즘] BOJ 16236 아기 상어 (JAVA)
https://www.acmicpc.net/problem/16236 백준 골드3 난이도인 문제로, 문제를 읽으면 눈치채기 쉽겠지만 bfs 기반 구현 문제이다. 가장 가까운 거리를 기반으로 이동하면서, 해당 위치에 있는 물고기를 먹을 수 있는 경우 먹고, 성장까지 해야하므로 Pos 클래스를 만들어 위치값(x,y)와 출발 지점으로부터의 거리를 저장했고, 해당 Pos값의 거리를 비교하고 같은 경우 x값, x값도 같은 경우 y값을 비교하여 다음에 접근할 위치를 탐색할 수 있도록 클래스를 선언했고, 이를 PriorityQueue를 통해 만족하는 값을 순차적으로 탐색하면서 만약 현재 위치에 먹을 수 있는 물고기가 있는 경우, 새로운 탐색을 시작해야하므로 PriorityQueue의 값과 isVisit..
알고리즘/알문풀(백준, 프로그래머스, 코드트리)
2024. 6. 11.
