[BFS] SWEA1953 탈주범 검거

문제 출처: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq&categoryId=AV5PpLlKAQ4DFAUq&categoryType=CODE&&&

 

Solution

• 맨홀 시작점부터 시작해서 주어진 시간 동안 BFS하면서 영역을 늘려간다.

Point

• 각 칸의 속성에 따라 주변 이동할 수 있는 경우의 수가 달라지는게 포인트인데, 이를 t에 저장해두고, 속성에 맞게 주변 칸 탐색하도록 한다.
• 이동할 때, 현재 칸과 다음칸이 연결되어 있어야만 한다. 즉, 현재 칸에서 오른쪽으로 움직이려면 현재칸에서 오른쪽 연결되어 있어야 하고, 다음 칸은 왼쪽으로 연결되어 있어야 한다.
• 이차원 배열에서 [x][y]라면 x가 세로 y가 가로라는 것에 주의, dx, dy 정의에서 주의해야 한다.

---

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

int T, N, M, R, C, L;
int dy[4] = { 0, 1, 0, -1 }; //U, R, D, L
int dx[4] = { -1, 0, 1, 0 }; //U, R, D, L
vector<vector<int>> t = { {0}, {0, 1, 2, 3}, {0, 2}, {1, 3}, {0, 1}, {1, 2}, {2, 3}, {0, 3} }; //tunnel type
int dist[50][50];
int map[50][50];
int result;

void input() {
    result = 0;
    memset(map, 0, sizeof(map));
    memset(dist, 0, sizeof(dist));
    cin >> N >> M >> R >> C >> L;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> map[i][j];
        }
    }
}

bool IsWay(int nx, int ny, int d) {
    if (!map[nx][ny])
        return false;
    int reverse = (d + 2) % 4;
    int t_type = map[nx][ny];
    for (int i = 0; i < t[t_type].size(); i++) {
        if (t[t_type][i] == reverse)
            return true;
    }
    return false;
}

void bfs() {
    queue<pair<int, int>> q;
    result = 1;
    dist[R][C] = 1;
    q.push(make_pair(R, C));
    while (!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();

        if (dist[cur.first][cur.second] == L)
            break;

        int t_type = map[cur.first][cur.second];
        for (int i = 0; i < t[t_type].size(); i++) {
            int d = t[t_type][i];
            int nx = cur.first + dx[d];
            int ny = cur.second + dy[d];
            if (0 <= nx && nx < N && 0 <= ny && ny < M && !dist[nx][ny] && IsWay(nx, ny, d)) {
                dist[nx][ny] = dist[cur.first][cur.second] + 1;
                q.push(make_pair(nx, ny));
                result++;
            }
        }
    }
}

int main()
{
    freopen("input.txt", "r", stdin);
    cin >> T;
    for (int t = 1; t <= T; t++) {
        input();
        bfs();
        cout << "#" << t << " " << result << endl;
    }
}