All(149)
-
[BOJ] 17135번 – 캐슬 디펜스
💬 문제 설명성 바로 아래에 3명의 궁수를 배치하고 모든 적을 제거하는 게임을 시뮬레이션하는 문제로 규칙은 다음과 같다:1. 매 턴 각 궁수는 가장 가까운 적 하나를 공격한다. - 거리는 맨해튼 거리로 계산 - 가장 가까운 적이 여러 명이면 가장 왼쪽(열이 작은) 적을 우선한다.2. 3명의 궁수가 동시에 공격을 수행한다. (같은 적을 겨냥해도 한 번만 제거됨)3. 공격이 끝나면 적이 한 칸 아래로 이동한다.4. 모든 적이 사라질 때까지 반복하며 제거한 적의 최대 수를 출력해야 한다. 📌 주의 사항타깃 선정: “거리 → 왼쪽 우선” 규칙을 반드시 구현해야 함동시 공격 처리: 각 궁수가 고른 적을 한 번에 제거해야 함적 이동: 라운드마다 맵을 한 칸 아래로 이동시키는 과정이 필요궁수 배치: ..
2025.08.17 -
[BOJ] 9505 - 엔터프라이즈호 탈출
💬 문제 설명엔터프라이즈호에서 출발해 가장 빠르게 함선 밖으로 탈출하는 최소 시간을 구하는 문제이다.각 지형(알파벳)에 따라 이동 시간이 다르며 지도 위의 `E` 위치에서 시작하여 지도 경계(바깥)로 나가는 최단 시간을 계산해야 한다. (지도상에서 이동은 상·하·좌·우로만 가능) 📌 주의 사항BFS로 풀면 안 됨BFS는 모든 간선의 가중치가 동일할 때만 최단 경로 보장이 가능하지만 이 문제는 지형마다 이동 시간이 다르기 때문에 BFS로는 최소 시간 보장이 안 됨다익스트라 알고리즘 필수가중치가 있는 최단 경로 문제이므로 우선순위 큐(Priority Queue)를 활용한 다익스트라를 적용해야 함PQ에서 꺼낼 때 방문 처리다익스트라는 PQ에 여러 번 같은 좌표가 들어갈 수 있기 때문에 큐에 넣을 때 `vi..
2025.08.15 -
[BOJ] 13424 - 비밀 모임
💬 문제 설명`N`개의 방과 `M`개의 통로가 있는 건물에서 `K`명의 친구들이 비밀 모임을 하려고 한다. 각 통로는 양방향이며 통과하는 데 시간이 걸린다.친구들은 각각 다른 방에 있고 한 방을 모임 장소로 정했을 때 모든 친구가 이동하는 거리의 합이 최소가 되는 방을 찾아야 한다.n만약 합이 같은 방이 여러 개면 방 번호가 작은 것을 선택한다. 📌 주의 사항그래프는 양방향 + 양의 가중치 → 다익스트라 사용 가능친구들이 위치한 `K`개의 시작점에서 각각 모든 방까지의 최단 거리를 알아야 함테스트 케이스가 여러 개 주어짐 → 매 케이스마다 초기화 필요INF 값은 충분히 크게 두고 거리를 더할 땐 `long` 타입 고려(누적 거리 합이 커질 수 있음)인접 리스트 초기화 시 `Arrays.fill(adj..
2025.08.13 -
[BOJ] 14675 - 단절점과 단절선
💬 문제 설명`N`개의 정점과 `N-1`개의 간선이 주어진다. (즉 그래프는 트리) `Q`개의 쿼리가 주어짐`1 k` → 정점 `k`가 단절점인지 확인`2 k` → 간선 `k`가 단절선인지 확인단절점 혹은 단절선이면 yes, 아니면 no 출력 📌 주의 사항그래프는 트리이므로 사이클이 없음트리의 성질:모든 간선은 제거하면 그래프가 2개로 나뉨 → 모든 간선이 단절선(bridge)단절점은 연결된 간선이 2개 이상(차수 ≥ 2)인 정점 → 잎 노드(차수 1)는 단절점이 아님 👌 문제 풀이차수 계산정점별 연결된 간선 개수(`degrees`) 저장쿼리 처리`t` == 1: `degrees[k]` >= 2면 yes, 아니면 no`t` == 2: 무조건 yes 💻 코드import java.io.Buffere..
2025.08.10 -
[BOJ] 18223 - 민준이와 마산 그리고 건우
💬 문제 설명그래프의 정점 수 `V`, 간선 수 `E` 그리고 친구 건우가 있는 정점 `P`가 주어지고 모든 간선은 양방향이며 가중치가 있다.1번 정점에서 `V`번 정점까지 가는 최단 경로가 존재할 때 그 경로가 정점 `P`를 지나가는지 여부를 판단해야 한다.`P`를 지나는 최단 경로가 있으면 "SAVE HIM" 아니면 "GOOD BYE"를 출력하면 된다. 📌 주의 사항간선 수와 정점 수가 많을 수 있으므로 `O(V²)` 알고리즘은 시간 초과가중치가 양수이므로 다익스트라 알고리즘을 사용하는 것이 적합"경로를 지나는지"를 직접 추적할 필요 없이 최단 거리 비교로 판별 가능경로가 존재하지 않는 경우(INF 값)도 고려해야 함 👌 문제 풀이1) 핵심 아이디어다익스트라를 두 번만 실행하면 문제를 풀 수 있..
2025.08.10 -
[BOJ] 22254 - 공정 컨설턴트 호석
💬 문제 설명`N`개의 작업이 주어지고 각 작업은 소요 시간이 다르다. 이 작업들을 `K`개의 공정 라인(=기계)에 나누어 배치했을 때 모든 작업이 `X` 시간 이내에 끝나도록 하고 싶을 때 가능한 최소 `K`를 구하는 문제이다.1. 작업은 주어진 순서대로 배치한다.2. 각 라인은 동시에 작업할 수 없고 한 번에 하나의 작업만 수행한다.3. 모든 작업을 `X` 이내에 끝내야 한다. 📌 주의 사항단순 정렬 후 매칭은 불가능→ 라인의 상태(남은 시간)가 실시간으로 변하므로 현재 가장 빨리 끝나는 라인을 찾아 작업을 배정해야 함`K`가 커질수록 조건이 쉬워진다는 단조성을 이용하면 이분 탐색(파라메트릭 서치)로 최소 `K`를 찾을 수 있음작업 시간의 합이 커질 수 있으므로 `long` 타입 사용 권장max(..
2025.08.08