#1953. [모의 SW 역량테스트] 탈주범 검거

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq

1. 문제 이해

L 시간동안 탈주범이 있을 수 있는 공간의 갯수를 세어보는 문제입니다.

2. 접근 방법

- dfs를 통해 문제에 접근하였습니다.

- 4방향으로 나누어 현재와 다음단계의 파이프를 비교하여 갈수 없는곳을 continue 시켰습니다.

- ret 이라는 변수를 따로 두어 지나간 곳을 1로 체크하여 1이 체크된 곳의 수를 세어 출력하였습니다.

(visit은 ret과 다른 용도 입니다. ret을 쓰지 않으면 갔던곳을 또 갈수 없기 때문에 1번(+)파이프일 경우에 오류가 생기게 됩니다.)

3. 문제 해결

#include <iostream>
#include <string.h>
#define MAX_SIZE 51
 
using namespace std;
 
int map[MAX_SIZE][MAX_SIZE];
bool visit[MAX_SIZE][MAX_SIZE];
bool ret[MAX_SIZE][MAX_SIZE];
int dx[] = { 0, 1, 0, -1 };
int dy[] = { -1, 0, 1, 0 };
 
void dfs(int m, int n, int x, int y, int l, int d) {
    if (d == l) return;
 
    ret[y][x] = 1;
    int cur = map[y][x];
 
    for (int i = 0; i < 4; i++) {
        if (i == 0 && (cur == 3 || cur == 5 || cur == 6)) continue;
        if (i == 1 && (cur == 2 || cur == 6 || cur == 7)) continue;
        if (i == 2 && (cur == 3 || cur == 4 || cur == 7))continue;
        if (i == 3 && (cur == 2 || cur == 4 || cur == 5))continue;
 
        int nx = x + dx[i];
        int ny = y + dy[i];
 
        int next = map[ny][nx];
 
        if (nx < 0 || ny < 0 || nx >= m || ny >= n)continue;
        else if (map[ny][nx] == 0 || visit[ny][nx]) continue;
 
        if (i == 0 && (next == 3 || next == 4 || next == 7)) continue;
        if (i == 1 && (next == 2 || next == 4 || next == 5)) continue;
        if (i == 2 && (next == 3 || next == 5 || next == 6)) continue;
        if (i == 3 && (next == 2 || next == 6 || next == 7)) continue;
        
        visit[y][x] = 1;
        dfs(m, n, nx, ny, l, d + 1);
        visit[y][x] = 0;
    }
}
 
int main() {
    int t;
    cin >> t;
    for (int i = 1; i <= t; i++) {
        int n, m, r, c, l;
        cin >> n >> m >> r >> c >> l;
 
        memset(map, 0, sizeof(map));
        memset(ret, false, sizeof(ret));
 
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < m; k++) {
                cin >> map[j][k];
            }
        }
 
        dfs(m, n, c, r, l, 0);
 
        int res = 0;
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < m; k++) {
                if (ret[j][k]) res++;
            }
        }
 
        cout << '#' << i << ' ' << res << '\n';
    }
    return 0;
}