BFS

문제설명입력 & 출력나의 풀이문제 접근 방법이번 "백준 - 토마토"문제는 "백준7576번 문제"와 거의 같은 문제입니다. 7576번 문제와 다른 점은 하나의 위 아래로 박스가 추가되었다는 점입니다. 위 아래로 박스가 추가되었기 때문에 방향도 마찬가지로 앞, 뒤가 추가되었습니다. 접근 방법도 마찬가지로 동일합니다. M x N 크기의 상자가 주어지고, 해당 상자의 토마토가 있을 때 다음 조건을 만족하는 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 합니다.보관 후 하루가 지나면 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다.저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력 왼쪽 그림과 같이 ..

문제설명입력 & 출력나의 풀이문제 접근 방법"백준 - 숨바꼭질" 문제는 수빈(N)이와 동생(K)의 위치가 주어질 때 동생을 찾을 수 있는 가장 빠른 시간을 출력하는 문제입니다.수빈이는 걷거나 순간이동을 할 수 있다.수빈이의 위치가 x라면걷기 : x + 1, X -1 순간이동 : x * 2즉, 수빈이가 동생을 찾을 수 있는 최단 시간을 구하는 것이기 때문에 BFS 문제의 대표적인 형태입니다.위와 같이 시작 노드에서 시작해서 수빈이가 이동할 수 있는 위치를 탐색하고, 최단시간이니깐 BFS를 사용하여 해결합니다. 각 위치에서 수빈이는 1초 후에 X-1, X+1, X*2로 이동할 수 있으며, Time이 증가할 때마다 모든 가능한 위치를 큐에 넣어 순서대로 탐색합니다. 이렇게 BFS로 탐색하면 처음 목표 위치(동..

개요본 글에서는 그래프 탐색 알고리즘의 종류인 너비 우선 탐색:BFS(Breadth-First Search) 알고리즘에 대해서 정리해보고자 합니다. BFS의 대한 내용은 아래의 포스팅에서 확인 가능합니다.  [Algorithm] 효율적인 그래프 탐색: 자바로 구현한 DFS 알아보기 (1/2)이번 포스팅에서는 Java 알고리즘에서 필수적이라고도 말할 수 있는 DFS와 BFS에 대해서 알아보겠습니다.  자바를 활용하다 보면 그래프나 트리 구조를 탐색해야 할 때가 있습니다.  예를 들어,pixx.tistory.com BFS (너비 우선 탐색) 이란❓BFS(Breadth-First Search)는 그래프 탐색 알고리즘의 하나로, 시작 노드에서 출발해 시작 노드를 기준으로 가장 가까운 노드를 먼저 방문하면서 탐색..

문제설명입력 & 출력나의 풀이문제 접근 방법"백준 - 토마토" 문제는 BFS (너비 우선 탐색) 를 활용하여 풀이하는 전형적인 그래프 탐색 문제입니다. M x N 크기의 상자가 주어지고, 해당 상자의 토마토가 있을 때 다음 조건을 만족하는 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 합니다.보관 후 하루가 지나면 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다.저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력문제 접근 방법익은 토마토(1)들을 모두 큐에 넣고 동시에 BFS를 시작합니다.익지 않은 토마토(0)는 방문하지 않은 노드로 처리하며, 토마토가 없는 칸(-1)은 아예 탐색하지 않습니..