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

문제

SWEA 모의 SW 역량테스트 - 1953 탈주범 검거

SW Expert Academy

 

---

문제 풀이

접근 방식

파이프 모양을 고려하여 BFS로 문제를 해결하였다.

우선, location 구조체를 만들어 위치(r, c)와 남은 시간(l)을 저장해주었고, 이를 큐에 넣어 BFS를 시행하였다.

BFS 내에서는 switch문을 사용하여 파이프의 모양에 따라 이동할 수 있는 방향을 각각 넣어주었다.

(0 : 상, 1 : 우, 2 : 하, 3 : 좌)

switch (map[now.r][now.c]) {
	case 1:
		go_dirs = {0, 1, 2, 3};
		break;
	case 2:
		go_dirs = {0, 2};
		break;
	case 3:
		go_dirs = {1, 3};
		break;
	case 4:
		go_dirs = {0, 1};
		break;
	case 5:
		go_dirs = {1, 2};
		break;
	case 6:
		go_dirs = {2, 3};
		break;
	case 7:
		go_dirs = {0, 3};
		break;
 }

 

그 후, go 함수를 실행하여 다음으로 이동할 수 있는 칸의 위치와 남은 시간(l-1)을 큐에 넣어주었다.

이동할 수 있는 곳인지는 이동할 수 없는 곳을 제외한 모든 곳으로 구해주었다.

이동할 수 없는 곳은 파이프가 없는 칸이거나, 연결될 수 없는 파이프 모양이거나, 이미 방문한 곳이다.

예를 들어 위로 가는 경우에는 다음 칸에 파이프가 없거나,

파이프 모양이 아래쪽과 연결되어 있지 않은 경우, 이미 방문한 칸인 경우에 이동할 수 없다.

void go(int x, int y, int l)
{
    int nx, ny, next;
    int len = go_dirs.size();
    for (int i = 0; i < len; i++)
    {
        nx = x + dir[go_dirs[i]][0];
        ny = y + dir[go_dirs[i]][1];
        if (nx < 0 || nx >= N || ny < 0 || ny >= M)
            continue;
        next = map[nx][ny];
        bool check = true;

        switch (go_dirs[i])
        {
        case 0:
            if (next == 0 || next == 3 || next == 4 || next == 7 || visit[nx][ny] == 1)
                check = false;
            break;
        case 1:
            if (next == 0 || next == 2 || next == 4 || next == 5 || visit[nx][ny] == 1)
                check = false;
            break;
        case 2:
            if (next == 0 || next == 3 || next == 5 || next == 6 || visit[nx][ny] == 1)
                check = false;
            break;
        case 3:
            if (next == 0 || next == 2 || next == 6 || next == 7 || visit[nx][ny] == 1)
                check = false;
            break;
        }

        if (check)
        {
            cnt++;
            visit[nx][ny] = 1;
            q.push({nx, ny, l - 1});
        }
    }
}

 

---

풀이 코드 - C++

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
struct location {
    int r, c, l;
};
 
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
vector<vector<int>> map;
vector<vector<bool>> visit;
vector<int> go_dirs;
queue<location> q;
int cnt, N, M, R, C, L;
 
void go(int x, int y, int l) {
    int nx, ny, next;
    int len = go_dirs.size();
    for (int i = 0; i < len; i++) {
        nx = x + dir[go_dirs[i]][0];
        ny = y + dir[go_dirs[i]][1];
        if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
        next = map[nx][ny];
        bool check = true;
 
        switch (go_dirs[i]) {
        case 0:
            if (next == 0 || next == 3 || next == 4 || next == 7 || visit[nx][ny] == 1)
                check = false;
            break;
        case 1:
            if (next == 0 || next == 2 || next == 4 || next == 5 || visit[nx][ny] == 1)
                check = false;
            break;
        case 2:
            if (next == 0 || next == 3 || next == 5 || next == 6 || visit[nx][ny] == 1)
                check = false;
            break;
        case 3:
            if (next == 0 || next == 2 || next == 6 || next == 7 || visit[nx][ny] == 1)
                check = false;
            break;
        }
 
        if (check) {
            cnt++;
            visit[nx][ny] = 1;
            q.push({ nx, ny, l - 1 });
        }
    }
}
 
 
int main(int argc, char** argv)
{
    int test_case;
    int T;
 
    //freopen("input.txt", "r", stdin);
    cin >> T;
    for (test_case = 1; test_case <= T; ++test_case) {
        cin >> N >> M >> R >> C >> L;
        map.assign(N, vector<int>(M));
        visit.assign(N, vector<bool>(M));
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                cin >> map[i][j];
            }
        }
        q.push({ R,C,L - 1 });
        cnt = 1;
        visit[R][C] = 1;
        while (!q.empty()) {
            location now = { q.front().r, q.front().c, q.front().l };
            q.pop();
            if (now.l == 0) continue;
            switch (map[now.r][now.c]) {
            case 1:
                go_dirs = { 0,1,2,3 };
                break;
            case 2:
                go_dirs = { 0,2 };
                break;
            case 3:
                go_dirs = { 1,3 };
                break;
            case 4:
                go_dirs = { 0,1 };
                break;
            case 5:
                go_dirs = { 1,2 };
                break;
            case 6:
                go_dirs = { 2,3 };
                break;
            case 7:
                go_dirs = { 0,3 };
                break;
            }
            go(now.r, now.c, now.l);
        }
        cout << "#" << test_case << " " << cnt << endl;
    }
    return 0;
}

실행 결과