Algorithm with C/DFS
-
CheeseAlgorithm with C/DFS 2020. 8. 13. 17:55
1. 문제 2. 문제 분석 위의 문제에서 쓰이는 알고리즘이 흡사 스타크래프트에서 저그의 크립이 없어지는 알고리즘과 같을 것이라는 생각이 들지 않는가? 그리고, 이 문제는 앞에서 했던 "두더지 굴" 문제를 응용할 것이다. 아래와 같이 치즈가 놓여져 있는 이차원 배열이 있다고 가정해보자. 치즈가 놓여져있는 공간은 1, 없으면 0 . 첫 번째로 우리는 탐색 지점을 배열의 첫 번째 인덱스라고 가정하겠다. (0,0)이 초기값 탐색 방향은 편의상 "아래->오른쪽->위 -> 왼쪽" 이라고 하겠다. 처음에 시작점에 도착했는데, 치즈가 없는 공간이었다. 이 부분을 -1로 세팅을 한다. 그리고, 탐색을 해보자. 탐색은 치즈가 놓여있지 않은 곳을 시작으로 탐색을 한다. (재귀 호출을 이용해서.) 다만 탐색을 진행하다가 탐색..
-
두더지 굴Algorithm with C/DFS 2020. 8. 11. 17:59
1. 들어가기에 앞서 아래의 두더지 굴 문제에 들어가는 알고리즘을 Floud Fill 알고리즘이라 한다. 이 방식은 우리가 많이 한 "지뢰찾기"게임에서 쓰인다. 아래의 문제에서도 나왔다시피 "1이 상하좌우로 연결되어 있으면" 이라는 표현이 나오는데, 상하좌우란 의미가 곧, 탐색 방향이 네방향이다라는 사실을 알 수 있다. 2. 문제 3. 문제 분석 주어진 문제에서 가장 첫 번째로 해야할 일은 두더지 굴을 하나 찾아내는 함수를 만들어야 한다. 이 함수의 이름을 SearchDFS라고 하겠다. 함수 이름처럼 "이 우선 탐색"을 해서 하나의 굴을 찾는 함수이다. 하나의 굴을 찾았으면, 처음에 할 일은 두더지굴의 넘버링을 붙여주는 것이다. 그리고, 이 함수의 리턴형을 결정해주어야 하는데, 하나의 굴을 찾아서 알게되..