반응형 깊이 우선 탐색4 [C/C++] #2583 영역 구하기(깊이 우선 탐색) 이번 문제는 복합 문제입니다. 색종이 붙이기 문제와, 섬의 갯수 구하기 문제가 결합된 문제라고 생각하시면 편합니다. https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 색종이 붙이기 문제는 캔버스를 생성한다음, 색칠하기만을 하시면 됩니다. \(O(MNK)\) 알고리즘이긴 하지만, 조금 더 개선을 하시면, \(O(MN+K)\) 알고리즘으로도 하실 수 있습니다. https://sdev.tistory.com/1547 [C/C++] 백.. 2024. 1. 2. [C/C++] 백준 #1991 트리순회(깊이 우선 탐색) 트리를 순회하는 방법은 크게 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS)가 있습니다. 깊이 우선 탐색은 스택(또는 재귀호출)을 이용하고 너비 우선 탐색은 큐를 사용하죠. 그런데, 깊이 우선 탐색의 경우에는 방문을 했다는 표시를 하는 방법에 따라서 전위(pre), 중위(in), 후위(post) 탐색으로 나눌 수 있습니다. 이번문제는 깊이 우선 탐색에서 전위, 중위, 후위 탐색의 결과를 출력하는 것입니다. 이 세가지 방법은 사실 기본적으로 호출하는 것은 똑같지만, 언제 방문 여부를 표시하는가에 따라서 다를 뿐입니다. 각각의 탐색 방법에 따라 함수를 따로 만드는 것이 시간상으로 더 효율적이겠지만, 저는 하나의 함수로 작성해보았습니다. 이 방법이 좋다는 것은 아니지만, 세가지 탐색 방법을 알아보기 좋게 .. 2023. 1. 13. [C/C++] 백준 #1987 알파벳(깊이 우선 탐색) 이번 문제는 깊이 우선 탐색(DFS)를 이용해서 풀었습니다. 백트랙킹과도 같은 기법이긴 합니다. 백트랙킹 자체가 깊이 우선 탐색을 이용하여 푸는 것인만큼 딱히 구분을 지을 필요는 없어보입니다. 갈 수 있는 길이냐 아니냐를 따지기 위해서는 알파벳 마스크(Alphabet mask)를 사용합니다. 일반적인 깊이 우선 탐색은 방문했는지 여부를 따지게 되는 것과는 다릅니다. 알파벳은 오직 한번만 지나갈 수 있기 때문에, 이미 지나온 자리는 다시 방문할 수가 없습니다. 다음으로는 가장 짧은 경로가 아니라 가장 긴 경로를 찾는 것이기 때문에 모든 경로를 다 살펴보아야 합니다. 그러다보면 꽤 많은 경로를 검색하게 됩니다. 문제에서 행과 열의 개수가 상당히 적기 때문에 (\( 1 \ge R,~C \ge 20\)), 깊이.. 2023. 1. 12. [C/C++] 백준 #1743 음식물 피하기(너비우선탐색) 이번 문제는 섬의 개수 구하기라든지, 섬의 넓이 구하기 문제와 비슷한 유형으로 너비 우선 탐색(BFS)나 깊이 우선 탐색(DFS)를 이용해서 푸시면 됩니다. 구현 자체는 깊이 우선 탐색이 더 쉽습니다. 너비 우선 탐색은 일단 큐를 사용해야 하기때문에 구현이 조금 더 까다롭다고 볼 수 있습니다. 그에 비해서 깊이 우선 탐색을 이용하면 재귀함수만 이용하면 되죠. 구현도 훨씬 간단하고요. 제가 작성한 소스입니다. 소스는 참고로 봐주세요. //-------------------------------------------------------------------- // baekjoon #1743 - Avoid The Lakes // - by Aubrey Choi // - created at 2019-08-06 .. 2022. 10. 6. 이전 1 다음 728x90
