본문 바로가기

BFS3

[백준] 2573번 - 빙산 풀이 및 코드 분석 (Java) 문제 링크1. 문제 분석📌 문제 개요이 문제는 지구 온난화로 인해 빙산이 해마다 녹는 현상을 시뮬레이션하고, 빙산이 두 덩어리 이상으로 분리되는 최초 시점(년수) 을 구하는 문제입니다.🎯 요구사항빙산은 2차원 배열로 주어지며, 0은 바다, 1~10은 빙산의 높이를 의미합니다.매년, 각 빙산 칸은 상하좌우에 접한 바다(0)의 수만큼 높이가 감소합니다.빙산의 높이는 0 이하로 내려갈 수 없습니다.매년 시뮬레이션을 진행하면서 빙산 덩어리의 개수를 세고, 2개 이상으로 나뉘는 첫 해를 출력해야 합니다.만약 빙산이 전부 다 녹을 때까지 분리되지 않으면 0을 출력합니다.📈 입력 크기 및 제약3 ≤ N, M ≤ 300빙산 칸 수 ≤ 10,000시간 복잡도는 연산이 해마다 반복되므로, 연산당 O(NM) 이내여야 .. 2025. 5. 9.
[백준] 7576번 - 토마토 문제 풀이 및 코드 해석 (Java) 문제 링크1. 문제 분석📌 문제 개요M x N 크기의 상자에 익은 토마토(1), 익지 않은 토마토(0), 빈 칸(-1)이 있다.익은 토마토는 인접한 네 방향(상, 하, 좌, 우)으로 익지 않은 토마토를 하루에 한 번 익게 만든다.모든 토마토가 익을 때까지 걸리는 최소 일수를 구해야 한다.익지 않은 토마토가 존재하지만 익을 수 없는 경우에는 -1을 출력한다.모든 토마토가 이미 익어 있다면 0을 출력한다.🎯 요구사항BFS(너비 우선 탐색) 을 활용하여 최소 일수를 구해야 한다.익은 토마토에서 BFS를 시작하여 인접한 익지 않은 토마토를 익게 만든다.익지 않은 토마토가 남아 있다면 -1을 출력해야 한다.2. 해결 방법🔹 핵심 개념BFS(너비 우선 탐색) 을 이용하여 최소 거리를 구하는 전형적인 문제여러 .. 2025. 2. 28.
[백준] 7562번 - 나이트의 이동 풀이 및 코드 분석 (Java) 문제 링크1. 문제 분석🏰 문제 개요체스판 위에서 나이트(knight)가 주어진 위치에서 목표 위치까지 이동하는 최소 횟수를 구하는 문제이다.나이트는 다음과 같은 8가지 방향으로 이동할 수 있다.(-1, -2), (-2, -1), (-2, 1), (-1, 2), (1, -2), (2, -1), (2, 1), (1, 2)🎯 요구사항나이트가 l x l 크기의 체스판에서 이동해야 한다.출발 위치 (sr, sc)에서 도착 위치 (er, ec)까지 가는 최소 이동 횟수를 구해야 한다.여러 개의 테스트 케이스가 주어지므로, 각각의 결과를 출력해야 한다.2. 해결 방법🔹 핵심 개념이 문제는 그래프 탐색(BFS)를 이용하면 최적의 해결책을 찾을 수 있다.BFS는 최단 경로를 찾을 때 가장 적합한 알고리즘이다.🔑.. 2025. 2. 27.

티스토리툴바