프로그래머스 수레 움직이기

About this offer

프로그래머스 수레 움직이기 — DFS와 백트래킹으로 풀이하기 1. 문제를 처음 봤을 때 이 문제는 빨간 수레와 파란 수레를 동시에 움직여서 각각의 도착 지점에 도달시키는 문제다. 단순히 각각의 수레에 대해 최단 경로를 찾으면 되는 문제가 아니다. 이유는 다음과 같다. 두 수레가 같은 칸으로 이동할 수 없다. 두 수레가 서로의 위치를 바꿀 수 없다. 각 수레는 자신이 방문했던 칸을 다시 방문할 수 없다. 한 수레가 도착하면 그 자리에 고정된다. 매 턴마다 두 수레를 함께 이동시켜야 한다. 따라서 현재 상태에서 가능한 모든 다음 상태를 탐색해야 한다. 이 문제에서는 격자 크기가 최대 4 × 4 이므로 DFS와 백트래킹을 사용해서 모든 경우를 탐색할 수 있다. 2. DFS란? DFS(Depth First Search)는 말 그대로 한 경로를 최대한 깊게 탐색하는 방법 이다. 예를 들어 수레가 다음과 같이 이동한다고 생각해보자. 시작 ↓ A ↓ B ↓ C DFS는 일단 시작 → A → B → C 처럼 한 방향으로 끝까지 들어간다. 더 이상 갈 수 없다면 이전 상태로 돌아와서 다른 선택을 해본다. 시작 / \ A D / \ B E 먼저 시작 → A → B 를 끝까지 탐색하고, 그 경로가 실패하면 돌아와서 시작 → A → E 를 탐색한다. 이처럼 현재 상태에서 가능한 다음 상태를 선택하고, 그 상태에서 다시 DFS를 호출하는 구조 가 핵심이다. 3. 이 문제에서 DFS의 상태는 무엇인가? 이 문제에서 현재 상태를 나타내려면 두 수레의 현재 위치가 필요하다. void dfs(int rr, int rc, int br, int bc, int cnt) 각 변수는 다음을 의미한다. rr : 빨강의 행 rc : 빨강의 열 br : 파랑의 행 bc : 파랑의 열 cnt : 현재까지 움직인 턴 수 예를 들어 빨강 = (1, 2) 파랑 = (3, 0) 이라면 DFS는 dfs(1, 2, 3, 0, cnt); 형태로 현재 상태를 표현한다. 즉 DFS는 "현재 빨강과 파랑이 이 위치에 있는데, 여기서부터 퍼즐을 풀 수 있는가?" 를 탐색하는 함수라고 생각하면 된다. 4. 왜 방문 배열이 2개 필요한가? 문제에는 중요한 조건이 있다. 수레는 자신이 방문했던 칸으로 다시 이동할 수 없다. 빨강과 파랑의 방문 기록은 서로 다르다. 따라서 방문 배열도 각각 필요하다. bool redVisited[4][4]; bool blueVisited[4][4]; 예를 들어 빨강이 A → B → C 로 이동했다면 redVisited[A] = true; redVisited[B] = true; redVisited[C] = true; 가 된다. 파랑이 같은 칸을 방문했는지는 빨강에게 영향을 주지 않는다. 그래서 redVisited 와 blueVisited 를 분리한다. 5. 한 턴에 두 수레를 동시에 움직인다 이 문제에서 가장 중요한 부분이다. 빨강은 최대 4방향으로 움직일 수 있고, 파랑도 최대 4방향으로 움직일 수 있다. 따라서 한 턴의 경우의 수는 최대 4 × 4 = 16 가지다. 그래서 먼저 빨강의 이동 후보를 만든다. vector<pair<int, int>> redNext; 그리고 파랑의 이동 후보도 만든다. vector<pair<int, int>> blueNext; 그 다음 두 후보를 조합한다. for (auto r : redNext) { for (auto b : blueNext) { // 하나의 다음 상태 } } 이 구조를 통해 빨강 → 오른쪽 파랑 → 위 빨강 → 오른쪽 파랑 → 아래 빨강 → 아래 파랑 → 왼쪽 ... 과 같은 모든 조합을 탐색할 수 있다. 6. 반드시 제거해야 하는 두 가지 이동 두 수레의 이동 후보를 조합한 뒤에는 두 가지 특수한 상황을 제거해야 한다. 6-1. 같은 칸으로 이동 if (nrr == nbr && nrc == nbc) continue; 빨강과 파랑이 같은 칸으로 이동하려는 경우다. 문제에서 허용하지 않으므로 해당 경우를 탐색하지 않는다. 6-2. 서로 자리 바꾸기 현재 상태가 빨강 → A 파랑 → B 이고 다음 상태가 빨강 → B 파랑 → A 라면 두 수레가 서로 자리를 바꾼 것이다. 문제에서 금지되어 있으므로 다음 조건으로 제거한다. if (nrr == br && nrc == bc && nbr == rr && nbc == rc) continue; 7. 백트래킹이 필요한 이유 이 문제에서 DFS만 생각하면 "DFS를 계속 호출하면 되는 것 아닌가?" 라는 생각이 들 수 있다. 하지만 방문 배열을 사용하기 때문에 문제가 생긴다. 예를 들어 빨강이 시작 → A → B 로 이동했다고 하자. 현재 방문 기록은 시작 = 방문 A = 방문 B = 방문 이다. 그런데 B 에서 더 이상 해결할 수 없어서 DFS가 끝났다고 하자. 이제 다른 경로를 탐색해야 한다. 시작 → A → C 를 시도하려면 이전 경로에서 추가했던 B 의 방문 기록을 제거해야 한다. 그렇지 않으면 이전 경로의 방문 정보가 새로운 경로까지 영향을 준다. 그래서 DFS가 끝나면 내가 추가했던 방문 기록을 다시 원래 상태로 되돌린다. 이것이 백트래킹이다. 8. 백트래킹의 핵심 구조 이 문제에서 백트래킹의 핵심은 사실 세 줄이다. redVisited[nrr][nrc] = true; dfs(nrr, nrc, nbr, nbc, cnt + 1); redVisited[nrr][nrc] = false; 순서는 반드시 이렇게 된다. 선택 ↓ 방문 처리 ↓ DFS로 깊게 탐색 ↓ 탐색 종료 ↓ 방문 처리 취소 ↓ 다음 선택 즉, true; dfs(); false; 라고 생각하면 된다. true 는 "이번 선택을 사용하겠다." dfs() 는 "그 선택으로 가능한 모든 경우를 탐색하겠다." false 는 "이번 선택은 끝났으니 원래대로 돌리고 다른 선택을 해보겠다." 라는 의미다. 9. 왜 DFS 이후에 false를 하는가? 이 부분이 처음에는 가장 헷갈렸다. 예를 들어 시작 → A → B 라는 경로를 탐색한다고 하자. B 로 이동하기 직전에 redVisited[B] = true; 로 기록한다. 그 상태로 DFS에 들어간다. 그러면 B 에서 다시 이전에 방문했던 칸으로 돌아가는 것을 막을 수 있다. DFS가 끝난 뒤에야 redVisited[B] = false; 로 되돌린다. 왜냐하면 이제 B 를 선택했던 경로가 끝났기 때문이다. 따라서 다른 경로를 탐색할 때는 B 가 마치 이번 경로에서는 방문하지 않은 것처럼 만들어야 한다. 10. 목표 지점에 도착한 수레는 어떻게 하는가? 문제에서는 수레가 자신의 도착 지점에 도착하면 더 이상 움직이지 않는다. 따라서 빨강이 이미 도착했다면 빨강의 다음 위치 후보는 현재 위치 하나뿐이다. if (rr == redGoal[0] && rc == redGoal[1]) { redNext.push_back({rr, rc}); } 즉 빨강은 빨강 → 목표 에 도착한 이후 빨강 → 가만히 빨강 → 가만히 빨강 → 가만히 있는 것이다. 파랑은 계속 움직인다. 둘 다 목표에 도착하면 DFS를 종료한다. if (rr == redGoal[0] && rc == redGoal[1] && br == blueGoal[0] && bc == blueGoal[1]) { if (answer == 0 || cnt < answer) answer = cnt; return; } 11. 내가 처음 작성하면서 틀렸던 부분 직접 코드를 작성하면서 몇 가지 실수를 했다. 11-1. 빨강의 방문 체크를 빼먹음 처음에는 빨강의 다음 위치를 검사할 때 벽만 확인했다. if (maze[nr][nc] == 5) continue; redNext.push_back({nr, nc}); 하지만 문제에는 자신의 방문했던 칸으로 이동할 수 없다. 는 조건이 있다. 따라서 다음 코드가 필요하다. if (redVisited[nr][nc]) continue; 최종적으로: if (maze[nr][nc] == 5) continue; if (redVisited[nr][nc]) continue; redNext.push_back({nr, nc}); 이 된다. 이걸 빼먹으면 빨강이 A → B → A → B → A → ... 처럼 계속 이동할 수 있다. 그 결과 DFS가 끝나지 않고 재귀 호출이 계속되어 segmentation fault 가 발생할 수 있다. 12. = 와 == 를 헷갈렸던 부분 방문 처리에서는 redVisited[nrr][nrc] = true; 를 사용해야 한다. = 는 대입이다. 반면 redVisited[nrr][nrc] == true; 는 비교 연산이다. 즉 방문 처리를 할 때 == 를 쓰면 실제 값이 변경되지 않는다. 13. 자리 교환 조건에서의 실수 자리 교환은 if (nrr == br && nrc == bc && nbr == rr && nbc == rc) 이다. 현재 빨강 위치와 파랑의 다음 위치가 같고, 현재 파랑 위치와 빨강의 다음 위치가 같으면 빨강 A → B 파랑 B → A 가 되는 것이므로 제거한다. 14. 전체적인 DFS 구조 결국 이 문제의 DFS는 다음 구조로 정리할 수 있다. 현재 빨강/파랑 위치 ↓ 목표 도착 여부 확인 ↓ 빨강의 이동 후보 생성 ↓ 파랑의 이동 후보 생성 ↓ 빨강 × 파랑 조합 ↓ ┌───────────────┐ │ 같은 칸인가? │ → YES → 제외 │ 자리 교환인가? │ → YES → 제외 └───────────────┘ ↓ 방문 처리 ↓ DFS(다음 상태) ↓ 방문 처리 취소 ↓ 다음 조합 탐색 15. 이번 문제에서 배운 핵심 이번 문제에서 가장 중요한 것은 단순히 코드를 외우는 것이 아니다. DFS 현재 상태에서 가능한 다음 상태를 하나 선택하고, 그 상태에서 다시 같은 작업을 반복한다. 백트래킹 DFS를 위해 변경했던 상태를 탐색이 끝난 뒤 원래대로 되돌린다. 이 문제에서의 핵심 패턴 방문 처리 ↓ DFS ↓ 방문 해제 그리고 두 수레가 동시에 움직이기 때문에 for (빨강의 이동 후보) { for (파랑의 이동 후보) { DFS(); } } 라는 구조가 만들어진다. 결국 이 문제는 "두 수레의 현재 상태를 DFS로 탐색하면서, 각 경로의 방문 정보를 백트래킹으로 관리하는 문제" 라고 정리할 수 있다.