기록보관소

토마토 문제는 BFS를 이용하는 문제입니다. BFS의 flood fill 기법을 사용하는 문제로 여러 개의 루트 노드에서 BFS를 수행한다는 점에서 다른 BFS 문제와의 차이를 확인할 수 있습니다. 문제를 해결하기 위해 BFS를 수행하기 직전 처음에 큐에 여러 개의 루트 노드를 삽입한다는 점을 제외하면 이외의 BFS flood fill 기법 응용 문제의 해결 방식과 매우 유사합니다. BFS 문제에 대한 전형적인 구현 방식은 다음의 글에서 확인할 수 있습니다. 2021.09.07 - [알고리즘/문제풀이] - [알고리즘/문제풀이][BOJ 1260번] DFS와 BFS [알고리즘/문제풀이][BOJ 1260번] DFS와 BFS DFS와 BFS는 DFS와 BFS에 대한 가장 기초적이면서도 중요한 문제입니다. DFS..

유기농 배추 문제는 이전에 풀었던 단지 번호 붙이기 문제와 매우 유사한 문제입니다. 따라서 코드를 재활용하여 문제를 해결할 수 있습니다. 이 문제에서는 Flood fill 기법을 활용하여 그룹의 개수만 세어줌으로써 문제를 해결할 수 있습니다. 따라서 그룹 내 원소의 개수를 더 이상 셀 필요가 없습니다. 단지번호 붙이기 문제와 유사하므로 자세한 설명은 단지 번호붙이기 문제를 참고하기 바랍니다. 2021.09.09 - [알고리즘/문제풀이] - [알고리즘/문제풀이][BOJ 2667번] 단지번호붙이기 [알고리즘/문제풀이][BOJ 2667번] 단지번호붙이기 단지번호붙이기 문제는 BFS의 특성을 이용하여 해결할 수 있는 문제입니다. BFS가 연결된 모든 노드를 탐색한다는 특성을 응용한 Flood Fill 기법을 사..

단지번호붙이기 문제는 BFS의 특성을 이용하여 해결할 수 있는 문제입니다. BFS가 연결된 모든 노드를 탐색한다는 특성을 응용한 Flood Fill 기법을 사용하여 해결할 수 있습니다. 첫 번째 셀부터 마지막 셀까지 순차적으로 탐색하다 단지가 발견되면 그 지점을 루트로 삼아 BFS로 단지를 탐색합니다. 단지가 모든 발견되면 다시 셀을 순차적으로 탐색하며 모든 단지가 발견될 때까지 이를 반복합니다. 작성한 코드는 다음과 같습니다. #include #pragma warning(disable : 4996) //https://ark-hive.tistory.com/ int N; int dx[] = { 0,0,1,-1 }; int dy[] = { 1,-1,0,0 }; int map[30][30]; int house..