알고리즘/백준3

• 

  [백준 Java] 3055 탈출 🔗 문제링크 🔗 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 🌟 생각 흐름 - 개인적 풀이 방법 🌟 물이 이동하는 경로와, 고슴도치가 이동하는 경로를 생각한다. 한 턴을 기준으로 BFS를 이용하여 먼저 물을 이동시키고, 고슴도치가 이동하는 방식으로 알고리즘을 구현하였다. 쉽게 물을 이동시키기 위해 물의 좌표를 입력당시 큐에 넣어두고 고슴도치의 시작 위치 또한 큐에 넣어준다. 이후에 물을 이동시키면서 기존 BFS와 같이 큐에 추가하면서 이동시킨다. ㄴ 차이점은 visit배열을 따로 선언하는것이 아닌 map에서 물이 이동.. 알고리즘/백준 2023. 5. 12.

• 

  [백준 java] 소가 길을 건너간 이유 14466 🔗 문제링크 🔗 14466번: 소가 길을 건너간 이유 6 첫 줄에 N, K, R이 주어진다. 다음 R줄에는 한 줄에 하나씩 길이 주어진다. 길은 상하좌우로 인접한 두 목초지를 잇고, r c r′ c′의 형태 (행, 열, 행, 열)로 주어진다. 각 수는 1 이상 N 이하이다. www.acmicpc.net 🌟 생각 흐름 🌟 먼저 가지 못하는 길을 저장해야 한다고 생각했습니다. 만약 리스트 형태로 저장하게 된다면 탐색에 너무 많은 시간이 걸리고 map의 사이즈가 100*100이므로 배열의 형태로 저장하는 것이 이득이라 생각하였습니다. 문제는 길의 startx, starty, endx, endy 형태로 주어지기 때문에 어느방향으로 길이 있는지 저장해야 합니다. 따라서 direction 방향에 따라 확인해보면서 .. 알고리즘/백준 2023. 5. 5.

• 

  [백준 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 🌟 생각 흐름 🌟 기존의 크루스칼 문제에서는 최단 경로를 계산하기 위해서 최단 경로를 기준으로 정렬을 하였다 하지만 해당 문제에서는 다리를 건널 때 가장 많이 적재할 수 있는 양을 물어보는 것이므로 가장 높은 값을 기준으로 정렬한다(내림차순) 만약 시작 지점과 끝지점이 한사이클안에 있다고 판단되는 순간 현재 적재량을 싫고 나를 수 있다는 소리이므로 멈추고 리턴한다. -- 이진탐색을 이용한.. 알고리즘/백준 2023. 5. 4.