[코드트리][백트래킹] 단순한 동전 챙기기 : Medium(Feat. DFS 관점 바꾸기)
방향 DFS로 풀려던 문제를 조합 DFS로 바꿔본 과정!! 처음 이 문제를 봤을 때는 격자에서 S부터 출발해 상하좌우로 이동하면서 동전을 줍고, 3개를 주운 뒤 E까지 도착하는 문제라고 생각했다.그래서 자연스럽게 다음과 같은 DFS를 떠올렸다.dfs(현재 위치, 마지막으로 먹은 동전 번호, 먹은 동전 개수, 이동 횟수) 상하좌우 네 방향으로 이동하면서, 현재 칸에 있는 동전 번호가 이전에 먹은 동전보다 크면 먹고, 아니면 그냥 지나가는 방식이다.처음에는 이 방식이 직관적이고 정석이라 생각했다... 1. 처음 접근: 방향 DFS처음 풀이에서는 다음과 같은 상태를 관리했다.static int[] dx = {-1, 1, 0, 0};static int[] dy = {0, 0, -1, 1};static boole..
2026. 5. 18.
