ZeroIron의 JUST DO "IT"!

문제 - (www.acmicpc.net/problem/19238) 🤔문제 접근 방법 다익스트라를 이용해서 풀었다.조금 다른 것은택시 승객을 찾아야 하는 상태와 태운 승객을 목적지까지 데려다줘야 하는 상태 2개로 나눠서 풀어나갔다 다익스트라를 진행하는 bfs는 총 M * 2 번 수행되어야 한다 (M은 승객의 수). 한 사람을 태우기 위해 최단 거리로 이동해야 하는 경우 M가지와 태운 사람을 최단거리로 목적지까지 데려다줘야 하는 경우 M가지를 합했기 때문이다. 즉, 처음 위치에서 승객을 찾기 위해 다익스트라 진행 -> 승객까지의 최단거리 승객을 목적지로 데려다 주기 위해 다익스트라 진행 -> 목적지까지의 최단거리 1,2를 반복 📌주의할 점 택시가 승객을 찾을 때는 현재 위치에서 가장 가까운 승객을 태워야 한..

문제 - (www.acmicpc.net/problem/19237) 🤔문제 접근 방법 상어마다 상하좌우 우선순위가 있네?->상어 클래스에 dir(현재 상어가 바라보는 방향), dirs(이 상어만의 우선순위)를 저장시켜 놓자 각 상어들 이동은 어떻게 하지? 다른 상어의 냄새가 없는 곳이 발견되면 그 위치로 이동한다 여기서 주의할 점!!! 그냥 이동하면 안 된다. tmp에 원래 map을 복사해놓고, tmp에다가 상어의 위치를 업데이트한다! 그랬을 때, 동시에 동일한 칸으로 이동하는 상어가 생긴다면, 상어의 숫자를 보고 판단하여 숫자가 가장 작은 상어만 이동시키고 나머지 상어는 모두 제거해준다. (반복문을 다 돌고 난 다음 제거작업 진행) 상하좌우 모두에 상어의 냄새가 존재한다면 나의 우선순위 순서로 방문했을 ..

문제 적당한 가지치기를 해야하는 dfs 문제였다 처음엔 완전탐색(부분집합)으로 풀었다 1. 두께별로 하나하나 방문해서 방문하고있는 위치를 전부 0, 1 (A, B)로 바꾼다. 2. 기저에 도달하면 완성된 필름을 검사하여 k만큼 연속되어있는지 확인한다 3. k만큼 연속되지 않은 것이 발견된다면 곧바로 검사를 종료하고, 전부 k만큼 연속되어있다면 주입한 약품의 수를 이용해 min값을 업데이트 한다. 🗝키포인트 dfs진행 시, 현 시점에서 주입한 약품의 수가 min보다 크거나 같다면 더이상 탐색할 필요없이 최소가 될 수 없으므로 탐색을 하지 않도록 한다. min이 뭔데? 지금까지 필름을 완성해왔을 때, 사용했던 약품의 수 중 최솟값 코드 import java.io.BufferedReader; import ja..

문제 - (www.acmicpc.net/problem/4485) 풀이는 코드에 주석으로 적었다! 😅실수 다익스트라를 이용하여 문제를 접근한다 dist 배열에 현재위치까지의 최단경로를 기록해가면서 목표지점까지 bfs dist 배열을 사용하는 것을 생각못했다 ㅜㅜ 다음엔 그래프에서 다익스트라를 활용하는 문제도 풀어봐야 겠다 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.PriorityQueue; import java.util.StringTokenizer; public class Main { public stat..