[Algorithm][C++] SWEA 1953. [모의 SW 역량테스트] 탈주범 검거

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

SW Expert Academy

 

풀이 핵심

1. BFS 문제

 

2. 큐에 push 할 때 조건 (터널이 연결되어 있음) 을 잘 구현해야 한다.

먼저 터널 종류에 따른 방향 정보가 담긴 dr[7 + 1][4], dc[7 + 1][4] 배열을 미리 만들어 준다.

이 때 행은 터널 구조물 타입을 의미한다.

따라서 맵을 탐색하며 map[r][c] 에 0이 아닌 수가 들어 있다면 터널이 연결되어 있는지를 확인한다.

터널이 연결되어 있는지를 확인하는 방법은 현재 방향의 반대 방향 정보가 탐색 중인 위치 (map[nr][nc]) 의 터널에 있는지를 파악해주면 된다. 

...
int rev_dr = -1 * dr[type][dir]; // 반대 방향 
int rev_dc = -1 * dc[type][dir]; // 반대 방향
int next_type = map[nr][nc]; // 탐색 중인 위치 터널 타입
bool flag = false;
for (int next_dir = 0; next_dir < 4; next_dir++) {
  if (rev_dr == dr[next_type][next_dir] && \
    rev_dc == dc[next_type][next_dir]) {
    flag = true;
	}
}
if (!flag) { // flag가 true로 변하지 않았다면 터널 연결 되지 않음
  continue;
}
...

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <queue>
#define MAXN    50
#define MAXM    50
using namespace std;
 
int T, N, M, R, C, L;
int map[MAXN][MAXM];
int visit[MAXN][MAXM];
struct INFO {
    int r, c, t;
};
const int dr[7 + 1][4] = {
    {0,},
    {1,0,-1,0},
    {1,-1,0,0},
    {0,0,0,0},
    {-1,0,0,0},
    {1,0,0,0},
    {1,0,0,0},
    {-1,0,0,0}
};
const int dc[7 + 1][4] = {
    {0,},
    {0,1,0,-1},
    {0,0,0,0},
    {1,-1,0,0},
    {0,1,0,0},
    {0,1,0,0},
    {0,-1,0,0},
    {0,-1,0,0}
};
 
inline void _init() {
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < M; c++) {
            visit[r][c] = 0;
        }
    }
}
 
int solve() {
	_init(); // visit 초기화
    queue<INFO> q;
    visit[R][C] = true;
    q.push({ R,C,1 });
    while (!q.empty()) {
        INFO cur = q.front();
        q.pop();
        if (cur.t == L) {
            break;
        }
        int type = map[cur.r][cur.c];
        for (int dir = 0; dir < 4; dir++) {
            int nr = cur.r + dr[type][dir];
            int nc = cur.c + dc[type][dir];
            if (nr < 0 || nr >= N || nc < 0 || nc >= M || visit[nr][nc]) {
                continue;
            }
            if (map[nr][nc]) {
                int rev_dr = -1 * dr[type][dir];
                int rev_dc = -1 * dc[type][dir];
                int next_type = map[nr][nc];
                bool flag = false;
                for (int next_dir = 0; next_dir < 4; next_dir++) {
                    if (rev_dr == dr[next_type][next_dir] && \
                        rev_dc == dc[next_type][next_dir]) {
                        flag = true;
                    }
                }
                if (!flag) {
                    continue;
                }
                visit[nr][nc] = cur.t + 1;
                q.push({ nr,nc,cur.t + 1 });
            }
        }
    }
 
    int ret = 0;
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < M; c++) {
            if (visit[r][c]) {
                ret++;
            }
        }
    }
    return ret;
}
 
int main() {
    // freopen("sample_input.txt", "r", stdin);
    scanf("%d", &T);
    for (int tc = 1; tc <= T; tc++) {
        scanf("%d %d %d %d %d", &N, &M, &R, &C, &L);
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < M; c++) {
                scanf("%d", &map[r][c]);
            }
        }
        int ret = solve();
        printf("#%d %d\n", tc, ret);
    }
    return 0;
}