[SW Expert Academy] 1953. [모의 SW 역량테스트] 탈주범 검거 풀이 (C++)

2017. 10. 20. 에 쓰여진 글입니다.

---

문제링크

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

SW Expert Academy

 

문제풀이

-DFS풀이법

DFS풀이는 작년 풀이라 나도 뭔가 어색하긴 한데

dfs_call이라는 함수호출수를 이용해서 재귀로 들어가면서 탈주범이 갈수있는 최대 경로를 탐색한다.

그리고 그 최대경로까지 도달하면서 전부 방문체크해줌.

이때 방문 배열이 2개 있다고 생각하면 된다.

visited 배열은 재귀 빠져나오면서 복원되는 , 즉 다시 왔던길을 방문하지 않기 위한 용도 이고 

position배열은 방문배열처럼 체크하는데 복원을 해주지 않는다는 것임.

그래서 다 돌고 메인문으로 돌아왔을때 position 배열에는 탈주범이 도망갈수있는 모든좌표가 true로 표시되있을것임

그리고 그거 갯수를 세주면서 답을 출력하는 형태

 

-BFS풀이법

BFS풀이는 일단 큐를 이용함

그래서 큐를 돌면서 이동해주는것인데 큐는 퍼져나가는 형태의 탐색이기때문에 방문 복원 같은거 필요없고 그냥 쭉쭉 퍼뜨려주면됨.

이때 큐에 탈출소요시간을 같이 넣어줘서 이걸로 최대 도망갈수있는 지점을 체크함.

그래서 이것도 다돌고 메인문으로 들어오면 DFS에 position배열처럼 visited배열에 모든 탈주범 좌표가 true로 표시됬을것임.

  

하..

반년만에 다시 풀어본 문제.

다 풀고 내 작년 코드를 보고 깜놀했다. 

이걸 재귀로.. DFS로 풀었다니.. 나 자신한테 놀람. 

지금 생각해보니 내가 작년에는 완전 DFS에 빠져서 재귀의 끝을 보는 코드를 짠거같음 ㅋㅋㅋㅋㅋ

BFS가 편한문제조차도 DFS로 풀어버렸던 ㅋㅋㅋㅋㅋ 그러다가 시간초과 늪에 걸려 못푼 문제도 많고 ㅋㅋㅋ

그래서인지 내 블로그 작년 글은 거의 재귀로 짜놨.....

이제는 BFS에 빠져서 모든 문제를 큐로 푸는 큐사랑에 걸린 나.. ㅠㅠ 

왜 중간을 못하는지 ㅋㅋㅋㅋㅋ

DFS로도 다시 한번 풀어볼까...

 

소스코드

소스코드1 (재귀, DFS 이용)

#include <iostream>
 
using namespace std;
 
int N, M, R, C, L;
int map[50][50];        //지도
bool visited[50][50];    //방문체크
bool position[50][50];    //탈주범 이동가능한 위치 체크
int Answer;
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
int dfs_call;
 
void Init_map()
{
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            map[i][j] = 0;
}
void Init_visited()
{
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            visited[i][j] = false;
}
void Init_position()
{
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            position[i][j] = false;
}
 
bool IsCheck(int cur_x, int cur_y, int new_x, int new_y)        //이동가능 경로인지 확인해주는 함수
{
    int type, nType;
    type = map[cur_x][cur_y];
    nType = map[new_x][new_y];
    switch (type) {
    case(0):            //아무데도못감
        break;
    case(1):            //십자가로 다 이동가능
        if (cur_x - 1 == new_x && cur_y == new_y) {    //위로만 움직일수있을때
            if (nType == 1 || nType == 2 || nType == 5 || nType == 6)    //위로이동
                return true;
        }
        else if (cur_x + 1 == new_x &&cur_y == new_y) {
            if (nType == 1 || nType == 2 || nType == 4 || nType == 7)    //아래로이동
                return true;
        }
        else if (cur_x == new_x&&cur_y - 1 == new_y) {    //왼쪽으로 이동
            if (nType == 1 || nType == 3 || nType == 4 || nType == 5)
                return true;
        }
        else if (cur_x == new_x&&cur_y + 1 == new_y) {        //오른쪽으로 이동
            if (nType == 1 || nType == 3 || nType == 6 || nType == 7)
                return true;
        }
        break;
    case(2):            //위아래 이동가능
        if (cur_x - 1 == new_x && cur_y == new_y) {    //위로만 움직일수있을때
            if (nType == 1 || nType == 2 || nType == 5 || nType == 6)    //위로이동
                return true;
        }
        else if (cur_x + 1 == new_x &&cur_y == new_y) {
            if (nType == 1 || nType == 2 || nType == 4 || nType == 7)    //아래로이동
                return true;
        }
        break;
    case(3):            //왼쪽오른쪽 이동가능
        if (cur_x == new_x&&cur_y - 1 == new_y) {    //왼쪽으로 이동
            if (nType == 1 || nType == 3 || nType == 4 || nType == 5)
                return true;
        }
        else if (cur_x == new_x&&cur_y + 1 == new_y) {        //오른쪽으로 이동
            if (nType == 1 || nType == 3 || nType == 6 || nType == 7)
                return true;
        }
        break;
    case(4):        //위, 오른쪽 이동 가능 
        if (cur_x - 1 == new_x&&cur_y == new_y) {    //위로 이동
            if (nType == 1 || nType == 2 || nType == 5 || nType == 6)
                return true;
        }
        else if (cur_x == new_x&&cur_y + 1 == new_y) {    //오른쪽으로 이동
            if (nType == 1 || nType == 3 || nType == 6 || nType == 7)
                return true;
        }
        break;
    case(5):        //밑, 오른쪽 이동 가능
        if (cur_x + 1 == new_x &&cur_y == new_y) {
            if (nType == 1 || nType == 2 || nType == 4 || nType == 7)    //아래로이동
                return true;
        }
        else if (cur_x == new_x&&cur_y + 1 == new_y) {    //오른쪽으로 이동
            if (nType == 1 || nType == 3 || nType == 6 || nType == 7)
                return true;
        }
        break;
    case(6):        //밑, 왼쪽 이동가능
        if (cur_x + 1 == new_x &&cur_y == new_y) {
            if (nType == 1 || nType == 2 || nType == 4 || nType == 7)    //아래로이동
                return true;
        }
        else if (cur_x == new_x&&cur_y - 1 == new_y) {    //왼쪽으로 이동
            if (nType == 1 || nType == 3 || nType == 4 || nType == 5)
                return true;
        }
        break;
    case(7):        //위, 왼쪽 이동가능
        if (cur_x - 1 == new_x&&cur_y == new_y) {    //위로 이동
            if (nType == 1 || nType == 2 || nType == 5 || nType == 6)
                return true;
        }
        else if (cur_x == new_x&&cur_y - 1 == new_y) {    //왼쪽으로 이동
            if (nType == 1 || nType == 3 || nType == 4 || nType == 5)
                return true;
        }
        break;
    }
    return false;
}
 
void dfs(int cur_x, int cur_y)
{
    dfs_call++;        //함수 호출수 증가
    if (dfs_call > L) {        //탈주한 시간보다 함수호출수가 커지면 여긴 도망갈수없는 범위임
        dfs_call--;            //함수호출수를 하나줄여주고
        return;                //바로 리턴시킨다.
    }
    else if ((map[cur_x][cur_y] != 0) && !visited[cur_x][cur_y]) {        //터널이 있고, 방문하지 않았으면 
        visited[cur_x][cur_y] = true;        //현재위치 방문표시해줌, 체크안해주면 다음위치갔다가 for돌면서 원래위치로 다시 돌아옴. 그래서 무한루프 걸릴수있음 . 그러면 시간초과가 됨 
        for (int i = 0; i < 4; i++) {        //위아래왼쪽오른쪽 하나씩 탐색할꺼임
            if (0 <= cur_x + dx[i] && cur_x + dx[i] < N && 0 <= cur_y + dy[i] && cur_y + dy[i] < M&&        //탐색범위가 지도안에있고
                IsCheck(cur_x, cur_y, cur_x + dx[i], cur_y + dy[i]) && !visited[cur_x + dx[i]][cur_y + dy[i]]) {    //이동가능한 경로이며 아직 방문한 곳이 아니라면
                position[cur_x + dx[i]][cur_y + dy[i]] = true;        //그 이동한 후의 경로를 탈주범이 갈수있다고 표시해줌
                dfs(cur_x + dx[i], cur_y + dy[i]);                    //이동한 위치에서 dfs함수 다시 호출
            }
        }
        visited[cur_x][cur_y] = false;        //방문한거 원상복귀 시켜줌. 방문초기화를 해줘야지 다른경로로 돌때 갈수있음. 
    }
    dfs_call--;
}
 
int main()
{
    int T;
    cin >> T;
    for (int test_case = 1; test_case <= T; test_case++) {
        Answer = 0;            //정답초기화
        dfs_call = 0;        //함수호출 초기화
        cin >> N >> M >> R >> C >> L;
        Init_map();        //맵초기화
        Init_visited();    //방문초기화
        Init_position();//탈주범 위치 초기화
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                cin >> map[i][j];
        position[R][C] = true;    //초기위치체크
        dfs_call = 1;            //탈주후 소요된 시간 1로 해줌
        dfs(R, C);                //탈주범 초기위치부터 이동시작
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                if (position[i][j])
                    Answer++;        //현재 탈주범이 있을수있는 위치는 true로 되있기 때문에 그거 개수를 센다.
        cout << "#" << test_case << " " << Answer << endl;
    }
 
    return 0;
}

 

소스코드2 (BFS 이용)

#include <iostream>
#include <utility>    //pair 위한 헤더
#include <queue>    //queue 위한 헤더
 
using namespace std;
 
enum { BLANK = 0 };
enum DIR { EAST = 0, WEST = 1, SOUTH = 2, NORTH = 3 };    //방향 설정해줌
 
int N, M, L;            //세로 가로 탈주시간
int R, C;                //맨홀위치
int map[50][50];        //맵
bool visited[50][50];    //방문배열
queue < pair < pair < int, int > ,int > > q;
//x,y좌표 , 현재 시간
int dx[] = { 0,0,1,-1 }; //동서남북
int dy[] = { 1,-1,0,0 };
int Answer;    //정답
 
 
void Init()        //초기화
{
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++) {
            map[i][j] = 0;
            visited[i][j] = false;
        }
}
 
bool check_area(int new_x, int new_y)        //영역체크
{
    if (0 <= new_x&&new_x < N && 0 <= new_y&&new_y < M &&
        !visited[new_x][new_y])
        return true;        //가능하면 true 
    return false;            //불가능하면 false
}
 
void push_queue(int cur_x, int cur_y, int new_time, int dir)    //큐에 넣어줌
{
    int new_x = cur_x + dx[dir];    //내가 갈방향
    int new_y = cur_y + dy[dir];
    if (!check_area(new_x, new_y))    //갈수있는지 체크
        return;                        //못가면 바로 리턴해줘야지
    if (dir == EAST &&                    //동쪽으로 갈꺼면
        (map[new_x][new_y] == 1 ||        //동쪽을 받아줄수있는 파이프이면
            map[new_x][new_y] == 3 ||    //(갈수있는길이면)
            map[new_x][new_y] == 6 ||
            map[new_x][new_y] == 7)) {
        visited[new_x][new_y] = true;    //가자
        q.push(make_pair(make_pair(new_x, new_y), new_time));    //그리고 큐에 넣어준다
    }
    else if (dir == WEST &&                //서쪽도 똑같이
        (map[new_x][new_y] == 1 ||
            map[new_x][new_y] == 3 ||
            map[new_x][new_y] == 4 ||
            map[new_x][new_y] == 5)) {
        visited[new_x][new_y] = true;
        q.push(make_pair(make_pair(new_x, new_y), new_time));
    }
    else if (dir == NORTH &&            //북쪽도 똑같이
        (map[new_x][new_y] == 1 ||
            map[new_x][new_y] == 2 ||
            map[new_x][new_y] == 5 ||
            map[new_x][new_y] == 6)) {
        visited[new_x][new_y] = true;
        q.push(make_pair(make_pair(new_x, new_y), new_time));
    }
    else if (dir == SOUTH &&            //남쪽도 똑같이
        (map[new_x][new_y] == 1 ||
            map[new_x][new_y] == 2 ||
            map[new_x][new_y] == 4 ||
            map[new_x][new_y] == 7)) {
        visited[new_x][new_y] = true;
        q.push(make_pair(make_pair(new_x, new_y), new_time));
    }
}
 
void check(int cur_x,int cur_y,int cur_time)
{
    switch (map[cur_x][cur_y]) {        //현재 무슨 파이프냐에 따라 갈 방향 설정
    case 1:
        for (int i = EAST; i <= NORTH; i++)
            push_queue(cur_x, cur_y, cur_time + 1, i);
        break;
    case 2:
        for (int i = SOUTH; i <= NORTH; i++)
            push_queue(cur_x, cur_y, cur_time + 1, i);
        break;
    case 3:
        for (int i = EAST; i <= WEST; i++)
            push_queue(cur_x, cur_y, cur_time + 1, i);
        break;
    case 4:
        push_queue(cur_x, cur_y, cur_time + 1, EAST);
        push_queue(cur_x, cur_y, cur_time + 1, NORTH);
        break;
    case 5:
        push_queue(cur_x, cur_y, cur_time + 1, EAST);
        push_queue(cur_x, cur_y, cur_time + 1, SOUTH);
        break;
    case 6:
        push_queue(cur_x, cur_y, cur_time + 1, WEST);
        push_queue(cur_x, cur_y, cur_time + 1, SOUTH);
        break;
    case 7:
        push_queue(cur_x, cur_y, cur_time + 1, WEST);
        push_queue(cur_x, cur_y, cur_time + 1, NORTH);
        break;
    }
}
 
void solve()
{
    q.push(make_pair(make_pair(R, C), 1));    //맨홀위치좌표, 맨홀들어가는시간1 큐에 넣어주기
    visited[R][C] = true;                    //방문표시
    while (!q.empty()) {                    //큐빌때까지 돌림
        int cur_x = q.front().first.first;    //현재 좌표정보 저장
        int cur_y = q.front().first.second;
        int cur_time = q.front().second;    //현재소요시간저장
        q.pop();                            //큐빼줌
        if (cur_time == L)                    //만약 탈출후 소요시간==현재시간 이면 
            continue;                        //큐 더 안넣고 현재점은 끝냄
        check(cur_x, cur_y, cur_time);        //체크함수호출
    }
}
 
int main()
{
    int T;
    cin >> T;
    for (int test_case = 1; test_case <= T; test_case++) {    //테케 돌리자
        Answer = 0;        //정답초기화
        /*입력*/
        cin >> N >> M >> R >> C >> L;
        Init();
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                cin >> map[i][j];
        /*풀이*/
        solve();
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                if (visited[i][j])        //방문됬으면
                    Answer++;            //있을수있는 장소니까 갯수 늘려줌
        cout << "#" << test_case << " " << Answer << endl;    //정답출력
    }
    
    return 0;
}