원래는 브루트 포스로 하나하나 대입해서 풀었는데 코드도 더럽고 내 취향이 아니라 다르게 풀어봤음
DFS를 이용하여 값을 더해가는 풀이
idx = 1 일 때(즉, 두개의 블럭을 선택했을 때) 새로운 블럭에서 다음 블럭을 탐색하는 것이 아니라 다시 기존블럭에서 탐색하게 만들면 ㅗ,ㅏ,ㅓ,ㅜ 모양을 만들 수 있다.
가지치기 하는 코드
2차원배열에서 최대값을 찾아서 max(map(max, graph)) 선택할 수 있는 남은 블럭의 갯수만큼 (3 - idx) 곱해주고 현재 누적합 total 에 더해서 max_result 와 비교해주는 방식
가지치기 안하니까 시간초과 나옴
***방문처리 주의하자***
'알고리즘 문제 > 백트래킹' 카테고리의 다른 글
| [Java] 백트래킹 (N과 M (1)) (0) | 2023.07.05 |
|---|---|
| 백트래킹 (좋은수열) (0) | 2022.01.30 |
| 백트래킹 (꽃 길) (0) | 2022.01.27 |
| 백트래킹 (부등호) (0) | 2022.01.26 |
| DFS + 백트래킹 (연산자 끼워넣기) (0) | 2022.01.19 |