문제요약
- n*n크기의 마당에 3개의 꽃을 심는 최소비용 찾기, 단 마당을 벗어나거나 꽃이 겹치면 안됨
풀이 과정
완전탐색을 이용하여 풀이
- 무엇을 탐색해야 함? 꽃을 배치하는 모든 경우찾기
- 어떻게 모든 경우를 찾음? 가능한 자리에 하나씩 차례대로 배치
- 배치가 가능한 조건은? 마당 안에 있어야함, 겹치면 안됨
- 마당안에 있는지 확인하는 법은? 마당의 크기를 n+1*n+1로 표현하고 미리 체크해놓기
- 겹치는지 확인하는 법은? 마당을 배열로 표현하고 꽃이 위치할 지점이 체크 되었는지 확인
- DFS or BFS 무엇을 사용할지? 중복된 경우에서 우선순위가 존재하지 않기 때문에 그냥 BFS사용
- depth기록을 위해 배열의 [0,0]인덱스에는 depth기록, 1번 인덱스부터 모양저장
개선할 점
- DFS를 사용할 경우 현재 상황을 기록하는 배열을 DFS함수의 인자로 넘기지 않고 구현하는 법
- DFS는 1가지의 경우를 완전히 탐색 후 다음 경우를 처음부터 완전히 탐색하는 성질을 이용한다
DFS함수가 끝난 후 바뀐 값을 원래대로 되돌리는 작업을 진행한다.arrCheck(i, j, true); DFS(depth + 1, sum + tmpCost); arrCheck(i, j, false);
- 배열복사시 주의 해야 함!! 1차원 배열을 복사 하려면 값이 아닌 주소를 복사하기 때문에 clone()을 사용하여 복사함,
하지만 2차원 배열에서 clone사용시 배열의 값이 주소이기 때문에 clone를 사용하더라도 주소값을 복사하게 됨
