BFS

Bredth-First-Search (너비 우선 탐색)란? BFS의 원리는 간단하게 말하면 퍼지는 물결파 이다. 잔잔한 호수에 돌을 던져 생기는 물결파를 떠올려 보자. 동그란 원형의 파원을 일으키며 퍼져나간다. 이렇게 동일한 거리의 지점들은 동시에 탐색을 하는 방법이다. 핵심은 1번의 탐색 루틴에서 하나의 level에 있는 모든 정점을 탐색한다는 것이다. 저번 DFS처럼 BFS방식을 그래프를 통해 설명해보겠다. 앞서 DFS에서 사용한 그래프와 동일한 형태의 그래프다. DFS와 마찬가지로 1번 정점부터 탐색을 시작해보자. 1번 정점을 탐색 완료했다면 현재 정점의 인접하는 정점들을 확인한다. BFS는 다음에 탐색할 위치를 인접한 모든 정점으로 선택한다. 따라서 다음 탐색은 2, 3번 정점으로 이동한다. 원리..

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마 www.acmicpc.net 문제를 요약하자면 익은 토마토가 토마토 상자에 있는 모든 토마토를 익히는 데 까지 얼마나 걸리는지 확인하는 것입니다. 바이러스가 퍼지듯이 ..