[백준 9944번] NxM 보드 완주하기

문제 링크: https://www.acmicpc.net/problem/9944

9944번: NxM 보드 완주하기

<문제 풀이> DFS, 백트래킹

 

아래와 같은 조건으로 DFS를 구현하면 됩니다.

1. 모든 빈칸을 방문했을 때 단계의 최솟값을 업데이트한다.

2. 현재 방향을 가지고 다음 좌표로 갈 수 있으면 방향을 유지해서 다음 좌표로 이동한다.

3. 현재 방향을 가지고 다음 좌표로 갈 수 없다면 다른 3가지 방향을 선택해서 다른 좌표로 이동한다.

 

단계의 최솟값을 구하기 위해서 단계 k를 DFS의 파라미터로 전달해야 됩니다.

1. 방향을 유지해서 다음 좌표로 갈 때는 단계를 증가시키지 않는다.

2. 방향을 바꿔서 다음 좌표로 이동할 때는 단계를 1 증가시킨다. 

 

단계를 구할 때 한 가지 주의할 점은 공이 시작점에 놓였을 때 사방이 장애물이면 공은 이동하지 않기 때문에 단계는 0이 됩니다.

 

공은 이미 지나간 곳, 장애물, 보드의 경계를 만날 때까지 한 방향을 유지해서 계속 이동하기 때문에 실제 시간복잡도는 가능한 4방향을 다 해보는 것보다 훨씬 줄어듭니다.

 

 

<C++소스코드>

#include <iostream>
#include <algorithm>
using namespace std;
 
 
const int dx[4] = { 0, 0, 1, -1 };
const int dy[4] = { 1, -1, 0 , 0 };
 
int n, m;
char board[30][30];
bool visited[30][30];
int blankCnt = 0;
int ans = 1e9;
 
void init() {
    blankCnt = 0;
    ans = 1e9;
}
 
//다음 좌표로 이동할 수 있는지 판별
bool check(int x, int y) {
    return !(x < 0 || y < 0 || x >= n || y >= m || visited[x][y] || board[x][y] == '*');
}
 
/*
x, y, dir : x,y 좌표에서 현재 dir 방향을 바라보고 있음
cnt : 현재까지 cnt개의 빈칸을 방문
k : 현재까지 총 k 단계 진행
*/
void dfs(int x, int y, int dir, int cnt, int k) {
    if (cnt == blankCnt) ans = min(ans, k); //모든 빈칸을 채웠을 경우에 최솟값 갱신
    visited[x][y] = true;
    int nx = x + dx[dir];
    int ny = y + dy[dir];
    if (check(nx, ny)) { // 현재 방향을 유지해서 다음 좌표로 갈 수 있으면
        dfs(nx, ny, dir, cnt + 1, k); // 방향을 유지해서 다음 좌표로 이동, 단계 유지
    }
    else { // 다음 좌표로 갈 수 없다면
        for (int nextDir = 0; nextDir < 4; nextDir++) {
            if (nextDir == dir) continue; // 방향을 바꿔서
            nx = x + dx[nextDir];
            ny = y + dy[nextDir];
            if (check(nx, ny)) { // 다른 좌표로 갈 수 있으면
                dfs(nx, ny, nextDir, cnt + 1, k + 1); // 다음 좌표로 이동, 단계 1 증가
            }
        }
        
    }
    visited[x][y] = false;
 
}
 
void solve() {
    int test_case = 0;
    while ((cin >> n >> m)) {
        init();
        test_case++;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cin >> board[i][j];
                if (board[i][j] == '.') blankCnt++;
            }
        }
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                for (int dir = 0; dir < 4; dir++) {
                    if (board[i][j] == '.' && check(i + dx[dir], j + dy[dir])) { 
                        dfs(i, j, dir, 1, 1); // 이동 방향으로 이동 가능하면 단계 1부터 시작
                    }
                    else if (board[i][j] == '.' && !check(i + dx[dir], j + dy[dir])) {
                        dfs(i, j, dir, 1, 0); // 제자리에만 있을 수 있으면 단계 0
                    }
                }
            }
        }
        if (ans == 1e9) {
            cout << "Case " << test_case << ": " << -1 << '\n';
        }
        else {
            cout << "Case " << test_case << ": " << ans << '\n';
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    solve();
 
    return 0;
 
}