이번에는 백준 1189번 컴백홈 문제를 풀어보았습니다.
문제를 처음 봤을 때 시작점에서 도착점까지 이동하는 모든 경우를 탐색해야 하고, 한 번 방문한 곳은 다시 방문할 수 없다는 조건이 있었습니다.
또한 이동 거리가 정확히 K인 경우만 정답으로 인정되기 때문에 DFS와 백트래킹을 이용하여 해결할 수 있다고 생각했습니다.
현재 이동한 거리를 함께 관리하면서 가능한 모든 경로를 탐색하도록 구현하였습니다.
문제 설명
한수는 왼쪽 아래에서 출발하여 오른쪽 위의 집으로 이동해야 합니다.
상하좌우로 이동할 수 있으며, 한 번 방문한 곳은 다시 방문할 수 없습니다.
또한 장애물(T)은 지나갈 수 없습니다.
거리가 정확히 K인 경우의 수를 구하는 문제입니다.
풀이 아이디어
DFS를 이용하여 모든 이동 경로를 탐색하였습니다.
현재 이동 거리를 함께 전달하면서 탐색을 진행하였습니다.
도착했지만 거리가 K가 아닌 경우에는 더 이상 탐색할 필요가 없으므로 바로 종료하였습니다.
또한 현재 이동 거리가 이미 K를 초과한 경우 역시 더 이상 탐색하지 않도록 가지치기를 수행하였습니다.
DFS가 종료되면 방문 표시를 다시 제거하여 다른 경로를 탐색하도록 구현하였습니다.
코드
#include <bits/stdc++.h>
using namespace std;
int R,C,K;
int visited[5][5];
char inp_map[5][5];
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};
int ret;
void dfs(int y, int x, int distance){
if (distance > K || (distance != K && y == 0 && x == C-1) )
return;
if (y == 0 && x == C-1 && distance == K) {
ret += 1;
return;
}
for (int i=0; i<4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || nx < 0 || ny >= R || nx >= C || visited[ny][nx] || inp_map[ny][nx] == 'T')
continue;
visited[ny][nx] = 1;
dfs(ny, nx, distance+1);
visited[ny][nx] = 0;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> R >> C >> K;
for (int i=0; i<R; i++) {
string s;
cin >> s;
for (int j=0; j<C; j++) {
inp_map[i][j] = s[j];
}
}
visited[R-1][0] = 1;
dfs(R-1, 0, 1);
cout << ret << '\n';
return 0;
}풀이 흐름
- 지도를 입력받습니다.
- 시작 위치를 방문 처리한 뒤 DFS를 시작합니다.
- 현재 위치에서 상하좌우를 탐색합니다.
- 이미 방문한 칸이나 장애물은 이동하지 않습니다.
- 이동 거리가 K를 초과하면 탐색을 종료합니다.
- 도착 위치에 거리 K로 도착한 경우 정답을 증가시킵니다.
- 탐색이 끝나면 방문 표시를 제거하고 다른 경로를 탐색합니다.
구현 포인트
1. 방문 가능한 위치 확인
이미 방문한 위치이거나 장애물인 경우에는 이동하지 않았습니다.
if (ny < 0 || nx < 0 || ny >= R || nx >= C || visited[ny][nx] || inp_map[ny][nx] == 'T')
continue;현재 이동 가능한 위치만 DFS를 수행하였습니다.
2. 거리 가지치기
현재 이동 거리가 K보다 커진 경우에는 더 이상 탐색하지 않았습니다.
if (distance > K)
return;또한 도착했지만 거리가 K가 아닌 경우에도 바로 종료하였습니다.
if (distance != K && y == 0 && x == C-1)
return;불필요한 탐색을 줄이기 위한 가지치기입니다.
3. 정답 조건 확인
도착 위치에 정확히 K의 거리로 도착한 경우에만 정답을 증가시켰습니다.
if (y == 0 && x == C-1 && distance == K) {
ret += 1;
return;
}문제에서 요구하는 조건을 만족하는 경우만 카운트하였습니다.
4. 백트래킹
현재 위치를 방문 처리한 뒤 탐색을 진행하였습니다.
visited[ny][nx] = 1;
dfs(ny, nx, distance+1);
visited[ny][nx] = 0;탐색이 끝나면 다시 방문 표시를 제거하여 다른 경로도 탐색할 수 있도록 하였습니다.
5. 시작 위치 방문 처리
DFS를 시작하기 전에 시작 위치를 미리 방문 처리하였습니다.
visited[R-1][0] = 1;
dfs(R-1, 0, 1);출발 지점을 다시 방문하는 경우가 발생하지 않도록 처리하였습니다.
