후회가 없도록

문제 출처: https://www.acmicpc.net/problem/1012 1. 결과 1) BFS 이용: 메모리 32124KB, 시간 104ms 2) 스택으로 구현한 DFS 이용: 메모리 29452KB, 시간 88ms 2. 풀이 이 문제는 비교적 평범한 DFS 문제라고 생각한다. 전체 좌표를 탐색하다가 만약 1(배추가 심어진 곳)을 발견하면 이와 상, 하, 좌, 우로 연결된 모든 배추 좌표를 방문하고, 이 전체를 배추흰지렁이 한 마리로 해결할 수 있다. 즉, 방문한 적이 없는 1을 발견하면 필요한 배추흰지렁이의 수를 1만큼 추가하고, 값을 1을 가지면서 해당 위치와 상, 하, 좌, 우로 연쇄적으로 연결된 모든 좌표들을 방문한 상태로 바꾸면 된다. 하지만 이를 재귀로 구현한 DFS를 이용하면 재귀 오류..

문제 출처: https://www.acmicpc.net/problem/2667 1. 결과 1) BFS 이용: 메모리 32108KB, 시간 96ms 2) DFS 이용: 메모리 29304KB, 시간 76ms 2. 풀이 이 문제는 전형적인 그래프 탐색 문제이다. 그래프 탐색은 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS) 두 가지가 있는데, 비교적 간단한 문제는 두 방법 모두 가능하다. 여기서 잠깐 둘의 차이를 짚고 가면, BFS는 최적, 최단과 같은 요소를 구할 때 유용하고, DFS는 특정 경로나 요소에 대해 끝까지 경우를 끝까지 탐색해볼 때 유용하다. 그런 부분에서 이 문제는 DFS가 더 적합하다고 볼 수 있다. 특정 영역에 대해 끝까지 탐색한 넓이를 구하는 것이기 때문이다. 위의 결과에서도 알 수 ..

문제 출처: https://www.acmicpc.net/problem/1260 1. 결과 메모리 33100KB, 시간 144ms 2. 풀이 DFS와 BFS 모두 가능한 각 경로를 탐색하는 방법이지만, DFS는 루트 노드에서 시작하여 일단 하나의 분기를 끝까지 탐색해본 후, 다시 직전에서 다른 것을 탐색하는 방식이고, BFS는 루트 노드에 연결된 모든 자식 노드를 탐색, 이후 그 자식 노드의 자식 노드들을 탐색하는 방식으로 루트로부터 떨어진 높이마다 해당 높이에서 가능한 경우를 모두 탐색한다. 이런 특징 때문에 DFS는 특정 경로를 찾아내는 문제, 순열이나 조합 등을 찾을 때 주로 사용하고, BFS는 최단 거리를 찾을 때 주로 사용한다고 한다. 일단 이 문제는 간단한 DFS, BFS 구현이 요점이기 때문에..