1953 탈주범 검거

첫번째 방법은 bfs를 통해 탐색하였다.

일반 길찾기와 달리 여러 조건들이 있어 구조체에 time 정보를 추가로 저장하였고,

이를 토대로 비교하며 갈 수 있을 경우에만 큐에 넣으면서 문제를 해결했다.

두번째 방법은 dfs를 통해 탐색하여 해결하였는데, 여기서는 visited에 time(몇시간 지났는지)를 기록하여

탐색하지 못하는 부분이 없도록 처리하였다.

또한 깔끔하게 짤 수 있는 부분이 있어 가독성을 높여 보았다.

<BFS를 이용한 코드>

#include <stdio.h>
#include <queue>
#include <memory.h>
using namespace std;
 
int t, n, m, sx, sy, l, x, y, ax, ay, time, cnt;
int map[50][50];
bool visited[50][50];
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
 
struct Node {
    int x;
    int y;
    int time;
    Node(int _x, int _y, int _time) {
        x = _x;
        y = _y;
        time = _time;
    }
};
 
int getResult() {
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (visited[i][j]) {
                cnt++;
            }
        }
    }
    return cnt;
}
 
void bfs(int a, int b) {
    queue<Node> q;
    q.push(Node(a, b, 1));
    visited[a][b] = true;
 
    while (!q.empty()) {
        x = q.front().x;
        y = q.front().y;
        time = q.front().time;
        q.pop();
 
        if (time == l) {
            continue;
        }
 
        for (int i = 0; i < 4; i++) {
            ax = x + dx[i];
            ay = y + dy[i];
            if (ax >= 0 && ay >= 0 && ax < n&&ay < m) {
                // i : 0=하,1=상,2=우,3=좌
                // stat :
                // 1 : 상하좌우
                // 2 : 상하
                // 3 : 좌우
                // 4 : 상우
                // 5 : 우하
                // 6 : 좌하
                // 7 : 좌상
                if (!visited[ax][ay]) {
                    if (map[x][y] == 2) {
                        if (i == 2 || i == 3) continue;
                    }
                    else if (map[x][y] == 3) {
                        if (i == 0 || i == 1) continue;
                    }
                    else if (map[x][y] == 4) {
                        if (i == 0 || i == 3) continue;
                    }
                    else if (map[x][y] == 5) {
                        if (i == 1 || i == 3) continue;
                    }
                    else if (map[x][y] == 6) {
                        if (i == 1 || i == 2) continue;
                    }
                    else if (map[x][y] == 7) {
                        if (i == 0 || i == 2) continue;
                    }
 
                    if (i == 0) {
                        if (map[ax][ay] == 1 || map[ax][ay] == 2 || map[ax][ay] == 4 || map[ax][ay] == 7) {
                            q.push(Node(ax, ay, time + 1));
                            visited[ax][ay] = true;
                        }
                    }
                    else if (i == 1) {
                        if (map[ax][ay] == 1 || map[ax][ay] == 2 || map[ax][ay] == 5 || map[ax][ay] == 6) {
                            q.push(Node(ax, ay, time + 1));
                            visited[ax][ay] = true;
                        }
                    }
                    else if (i == 2) {
                        if (map[ax][ay] == 1 || map[ax][ay] == 3 || map[ax][ay] == 6 || map[ax][ay] == 7) {
                            q.push(Node(ax, ay, time + 1));
                            visited[ax][ay] = true;
                        }
                    }
                    else {
                        if (map[ax][ay] == 1 || map[ax][ay] == 3 || map[ax][ay] == 4 || map[ax][ay] == 5) {
                            q.push(Node(ax, ay, time + 1));
                            visited[ax][ay] = true;
                        }
                    }
                }
            }
        }
    }
}
 
void init() {
    memset(visited, false, sizeof(visited));
    memset(map, 0, sizeof(map));
}
 
int main() {
    scanf("%d", &t);
    for (int tc = 1; tc <= t; tc++) {
        init();
 
        scanf("%d %d %d %d %d", &n, &m, &sx, &sy, &l);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                scanf("%d", &map[i][j]);
            }
        }
 
        bfs(sx, sy);
 
        printf("#%d %d\n", tc, getResult());
    }
}

<DFS를 이용한 코드>

#include <stdio.h>
#include <memory.h>
using namespace std;
 
int t, n, m, r, c, l, dest;
int map[50][50];
int visited[50][50];
// {상, 하, 좌, 우}
int direct[8][4] = { { 0,0,0,0 },{ 1,1,1,1 },{ 1,1,0,0 },{ 0,0,1,1 },
{ 1,0,0,1 },{ 0,1,0,1 },{ 0,1,1,0 },{ 1,0,1,0 } };
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
 
void solve(int x, int y, int time) {
    if (time == l) {
        return;
    }
 
    for (int i = 0; i < 4; i++) {
        int ax = x + dx[i];
        int ay = y + dy[i];
 
        if (i == 0) dest = 1;
        else if (i == 1) dest = 0;
        else if (i == 2) dest = 3;
        else dest = 2;
 
        if (ax >= 0 && ay >= 0 && ax < n && ay < m) {
            if (direct[map[x][y]][i] == 1 && direct[map[ax][ay]][dest] == 1) {
                if (!visited[ax][ay] || visited[ax][ay]>visited[x][y]+1) {
                    visited[ax][ay] = time+1;
                    solve(ax, ay, time + 1);
                }
            }
        }
    }
}
 
int getResult() {
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (visited[i][j]) {
                cnt++;
            }
        }
    }
    return cnt;
}
 
void init() {
    memset(visited, false, sizeof(visited));
    memset(map, 0, sizeof(map));
}
 
int main() {
    scanf("%d", &t);
    for (int tc = 1; tc <= t; tc++) {
        init();
 
        scanf("%d %d %d %d %d", &n, &m, &r, &c, &l);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                scanf("%d", &map[i][j]);
            }
        }
 
        visited[r][c] = 1;
        solve(r, c, 1);
        printf("#%d %d\n", tc, getResult());
    }
}