나의 공부장

위의 세 가지 모두 경우의 수를 다 돌려보는 느낌이 들지만, 정확히 따지자면 다음과 같다고 합니다. 백트래킹 이미 지나쳐온 곳을 다시 돌아가서 다른 가능성을 시도해보는 걸 반복하는 기법입니다. 반드시 DFS만으로 가능한 게 아니고 BFS 등으로도 가능하지만 일반적으로는 DFS와 연관이 깊다고 합니다. 브루트 포스 꼭 '깊이'나 '탐색'의 개념이 아니더라도, 모든 경우의 수를 다 대입해보는 기법입니다. DFS 여러 지점을 한 단계씩 거쳐가면서 탐색하고, 스택의 개념을 이용해서 이전 단계로 돌아가야만 DFS라고 합니다.

문제 링크 : https://www.acmicpc.net/problem/1743 1743번: 음식물 피하기 문제 코레스코 콘도미니엄 8층은 학생들이 3끼의 식사를 해결하는 공간이다. 그러나 몇몇 비양심적인 학생들의 만행으로 음식물이 통로 중간 중간에 떨어져 있다. 이러한 음식물들은 근처에 있는 것끼리 뭉치게 돼서 큰 음식물 쓰레기가 된다. 이 문제를 출제한 선생님은 개인적으로 이러한 음식물을 실내화에 묻히는 것을 정말 진정으로 싫어한다. 참고로 우리가 구해야 할 답은 이 문제를 낸 조교를 맞추는 것이 아니다. 통로에 떨어진 음식물을 피해가기란 쉬운 일이 아 www.acmicpc.net 문제 풀이 DFS 알고리즘을 이용해서, 가장 큰 음식물의 크기를 구해주면 됩니다. 기존에 구한 음식물의 크기보다 더 큰 ..

문제 링크 : https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수 www.acmicpc.net 문제 풀이 기존 DFS에 정렬을 섞은 문제입니다. 따로 방문 배열 필요 없이, DFS를 탐색하면서 탐색한 지점을 0으로 만들고, 단지의 수를 구합니다..