[DFS] BJ16954 움직이는 미로 탈출

문제 출처: https://www.acmicpc.net/problem/16954

 

Solution

• DFS로 갈 수 있는 길을 탐색하며 목적지에 도달할 수 있는지 판별한다.

Point

• 주의할 점은 이동 시에 현재 위치에 머무를 수 있다는 점, 갔던 길로 다시 되돌아갈 수 있다는 점이다. 따라서 visit이 필요 없다.
• 맵을 업데이트 할 때 주의할 점이 row가 큰 값부터 먼저 업데이트해줘야하고, 맨 윗 열까지 확실하게 모두 업데이트 해줘야한다. 반복문 조건에서 r>=0을 r>0으로 해서 틀렸었다.
• DFS 리턴 시에 맵을 롤백해줘야 한다.

---

#include <iostream>
#include <cstring>

using namespace std;

int map[8][8];
int dr[] = {-1, -1, 0, 1, 1, 1, 0, -1, 0}; //N NE E SE S SW W NW no
int dc[] = {0, 1, 1, 1, 0, -1, -1, -1, 0};
bool result = false;

void input() {
    char c;
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            cin >> c;
            if (c == '#') map[i][j] = 1;
            else map[i][j] = 0;
        }
    }
}

void updateMap() {
    for (int r = 7; r >= 0; r--) {
        for (int c = 0; c < 8; c++) {
            if (r == 7) { map[r][c] = 0; continue; }
            if (map[r][c]) { map[r + 1][c] = 1; map[r][c] = 0; }
        }
    }
}

bool dfs(int cr, int cc) {
    if (map[cr][cc]) return false;
    for (int i = 0; i < 9; i++) {
        int nr = cr + dr[i], nc = cc + dc[i];
        if (0 <= nr && nr < 8 && 0 <= nc && nc < 8 && !map[nr][nc]) {
            if (nr == 0) return true; //if(nr==0&&nc==7) cuz, wall getting down, don't need to check column
            int tmp_map[8][8];
            memcpy(tmp_map, map, sizeof(map));
            updateMap();
            if (dfs(nr, nc)) return true;
            memcpy(map, tmp_map, sizeof(map));
        }
    }
    return false;
}

int main() {
    input();
    if (dfs(7, 0)) cout << 1 << endl;
    else cout << 0 << endl;
}