[SWEA] 1953 탈주범 검거

1953 탈주범 검거

풀이)

bfs를 이용해 탈주범이 이동하게 푼 문제이다

핵심은

각 터널마다 어떤 방향(상하좌우)로 움직일 수 있는지,

방향으로 움직였을때 움직인 방향의 터널과 연결될 수 있는지를 저장해놓는 것이다.

나같은 경우는 

터널 구조물 1~7번 각각 어떤 방향으로 움직이는지를 vector <int> turner[8];에 저장하고

방향으로 움직였을때 터널에 이어질 수 있는 지를 vector <int> connect[4];에 저장했다.

turner[i] = i번째 터널일 경우 어떤 방향으로 움직일 수 있는지

상하좌우를 0, 1, 2, 3 이라고 할때

터널 구조물 1은 (십자가 모양) : 0, 1, 2, 3 방향 모두 움직일 수 있다.

터널 구조물 2는 (세로막대기 모양) : 0, 1 방향으로만 움직일 수 있다.

...

이런식으로 생각해 vector에 저장해놓았다.

결과물

vector <int> turner[8] = { {},{0,1,2,3},{0,1},{2,3},{0,3},{1,3},{1,2},{0,2} }; //터널은 1번부터 시작하니깐 0번은 빈공간으로 둠

그리고 현재 터널에서 다음 칸의 터널로 움직일때,

터널이 연결되어야 이동 가능하므로

connect[i] = i방향으로 움직여서 갈때, 다음 칸의 터널이 뭐여야 하는지 

예를 들어 

현재 터널이 2번(세로막대기 모양)이면 움직일 수 있는 방향은 상 하 이다.

그럼 상으로 갔을 때 연결될 수 있는 터널은

 이런식으로 1번터널, 5번터널, 6번터널이다.

이런식으로 생각해          상[0]      하[1]       좌[2]         우[3]        로 갈때 어떤 터널과 연결될 수 있는지 저장했다.

결과물

vector <int> connect[4] = { {1,2,5,6},{1,2,4,7},{1,3,4,5},{1,3,6,7} }; 

따라서,

이들을 이용해

1. 현재 좌표 어떤 터널인지

2. 그 터널에서는 어떤 방향(상하좌우)으로 갈 수 있는지

3. 각 방향으로 갈 수 있는 지(다음 칸 터널 확인)

를 반복해, 갈 수 있는 지점을 세어주면 결과가 나온다.

코드)

#include <stdio.h>
#include <queue>
#include <string.h>
#include <vector>
using namespace std;
 
int n,m,r,c,l;
int map[50][50];
bool visited[50][50];
//상하좌우 0123
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
vector <int> turner[8] = { {},{0,1,2,3},{0,1},{2,3},{0,3},{1,3},{1,2},{0,2} };
vector <int> connect[4] = { {1,2,5,6},{1,2,4,7},{1,3,4,5},{1,3,6,7} };
int bfs(int time) {
    int cnt = 1;//갈수 있는 위치개수
    visited[r][c] = true;
    queue <pair<int, int>> qu;
    qu.push({ r,c });
    while (!qu.empty())
    {
        int size = qu.size();
        while (size--)
        {
            int y = qu.front().first;
            int x = qu.front().second;
            int t = map[y][x];//현재 터널
            qu.pop();
            for (int i = 0; i < turnel[t].size(); i++) {
                int dir = turner[t][i];
                int ny = y + dy[dir];
                int nx = x + dx[dir];
                if (ny >= 0 && ny < n && nx >= 0 && nx < m) {
                    //이미 방문 터널 or 터널이 없는곳
                    if (visited[ny][nx] || map[ny][nx] == 0) continue;
                    //이동해온 방향과 다음 터널과 연결될수있는지
                    bool fail = true;
                    for (int j = 0; j < 4; j++) {
                        if (connect[dir][j] == map[ny][nx]) {
                            fail = false;
                            break;
                        }
                    }
                    if (fail) continue;
                    visited[ny][nx] = true;
                    cnt++;
                    qu.push({ ny,nx });
                }
            }
        }
        time--;
        if (time == 1) break;
    }
    memset(visited, false, sizeof(visited));
    return cnt;
}
 
int main() {
    freopen("sample_input (1).txt", "r", stdin);
    int T = 0;
    scanf("%d", &T);
    for (int test_case = 1; test_case <= T; test_case++) {
        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]);
            }
        }
        if (l == 1) {
            printf("#%d 1\n", test_case);
        }
        else {
            printf("#%d %d\n", test_case, bfs(l));
        }
        
    }
 
    return 0;
}