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

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.


교도소로 이송 중이던 흉악범이 탈출하는 사건이 발생하여 수색에 나섰다.
탈주범은 탈출한 지 한 시간 뒤, 맨홀 뚜껑을 통해 지하터널의 어느 한 지점으로 들어갔으며,
지하 터널 어딘가에서 은신 중인 것으로 추정된다.
터널끼리 연결이 되어 있는 경우 이동이 가능하므로 탈주범이 있을 수 있는 위치의 개수를 계산하여야 한다.
탈주범은 시간당 1의 거리를 움직일 수 있다.
지하 터널은 총 7 종류의 터널 구조물로 구성되어 있으며 각 구조물 별 설명은 [표 1]과 같다.

[표 1]

[그림 1-1] 은 지하 터널 지도의 한 예를 나타낸다.

이 경우 지도의 세로 크기는 5, 가로 크기는 6 이다.
맨홀 뚜껑의 위치가 ( 2, 1 ) 으로 주어질 경우, 이는 세로 위치 2, 가로 위치 1을 의미하며 [그림 1-2] 에서 붉은 색으로 표기된 구역이다.
탈주범이 탈출 한 시간 뒤 도달할 수 있는 지점은 한 곳이다.
탈주범이 2시간 후 도달할 수 있는 지점은, [그림 1-3] 과 같이 맨홀 뚜껑이 위치한 붉은 색으로 표시된 지하도 와 파란색으로 표기된 지하도까지 총 3개의 장소에 있을 수 있다.
3시간 후에는 [그림 1-4] 과 같이 총 5개의 지점에 있을 수 있다.
       

                    

 

[그림 1-1]                                                      [그림 1-2]

       

                    

[그림 1-3]                                                      [그림 1-4]

[그림 2-1] 에서 맨홀뚜껑이 위치한 지점이 ( 2, 2 ) 이고 경과한 시간이 6 으로 주어질 경우,
[그림 2-2] 에서 맨홀뚜껑이 위치한 지점은 붉은 색, 탈주범이 있을 수 있는 장소가 푸른색으로 표기되어 있다.
탈주범이 있을 수 있는 장소는, 맨홀뚜껑이 위치한 지점을 포함하여 총 15 개 이다.
       

                    

[그림 2-1]                                                      [그림 2-2]

지하 터널 지도와 맨홀 뚜껑의 위치, 경과된 시간이 주어질 때 탈주범이 위치할 수 있는 장소의 개수를 계산하는 프로그램을 작성하라.


[제약 사항]

1. 시간 제한 : 최대 50개 테이트 케이스를 모두 통과하는데, C/C++/Java 모두 1초
2. 지하 터널 지도의 세로 크기 N, 가로 크기 M은 각각 5 이상 50 이하이다. (5 ≤ N, M ≤ 50)
3. 맨홀 뚜껑의 세로 위치 R 은 0 이상 N-1이하이고 가로 위치 C 는 0 이상 M-1이하이다. (0 ≤ R ≤ N-1, 0 ≤ C ≤ M-1)
4. 탈출 후 소요된 시간 L은 1 이상 20 이하이다. (1 ≤ L ≤ 20)
5. 지하 터널 지도에는 반드시 1개 이상의 터널이 있음이 보장된다.
6. 맨홀 뚜껑은 항상 터널이 있는 위치에 존재한다.

[입력]

첫 줄에 총 테스트 케이스의 개수 T가 주어진다.
두 번째 줄부터 T개의 테스트 케이스가 차례대로 주어진다.
각 테스트 케이스의 첫 줄에는 지하 터널 지도의 세로 크기 N, 가로 크기 M, 맨홀 뚜껑이 위치한장소의 세로 위치 R, 가로 위치 C, 그리고 탈출 후 소요된 시간 L 이 주어진다.
그 다음 N 줄에는 지하 터널 지도 정보가 주어지는데, 각 줄마다 M 개의 숫자가 주어진다.
숫자 1 ~ 7은 해당 위치의 터널 구조물 타입을 의미하며 숫자 0 은 터널이 없는 장소를 의미한다.

[출력]

테스트 케이스의 개수만큼 T줄에 T개의 테스트 케이스 각각에 대한 답을 출력한다.
각 줄은 “#x”로 시작하고 공백을 하나 둔 다음 정답을 기록한다. (x는 1부터 시작하는 테스트 케이스의 번호이다)
출력해야 할 정답은 탈주범이 위치할 수 있는 장소의 개수이다.

 

 

#include <iostream>
#include <string.h>
#include <queue>
 
using namespace std;
 
class dir{
public :
    bool con[4]; //u,r,d,l
};
dir arr[51][51];
bool visit[51][51];
int ans, mx[] = {-1,0,1,0}, my[] = {0,1,0,-1},n,m,r,c,l,idx;
int direction[7][4] = {{1,1,1,1},{1,0,1,0},{0,1,0,1},{1,1,0,0},{0,1,1,0},{0,0,1,1,},{1,0,0,1}};
 
void solve(int x, int y)
{
    queue<pair<int, int> > q;
    queue<int> len;
    q.push(make_pair(x,y));
    len.push(1);
    while(!q.empty())
    {
        int a = q.front().first;
        int b = q.front().second;
 
        q.pop();
        int run = len.front();
        run++;
        if(run>l) return;
        len.pop();
        for(int i=0;i<4;i++)
        {
            int nx = a + mx[i];
            int ny = b + my[i];
            if(nx<0||ny<0||nx>=n||ny>=m || visit[nx][ny] || !arr[a][b].con[i])continue;
 
            int next = (i + 2) % 4;
 
            if(arr[nx][ny].con[next])
            {
                visit[nx][ny] = true;
                q.push(make_pair(nx,ny));
                ans++;
                len.push(run);
            }
 
        }
 
 
    }
 
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int tc;
    cin>>tc;
    for(int t=1;t<=tc;t++)
    {
        ans = 1;
        cin>>n>>m>>r>>c>>l;
        memset(arr, false, sizeof(arr));
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                cin>>idx;
                if(idx == 0)continue;
                for(int aa=0;aa<4;aa++)
                    arr[i][j].con[aa] = direction[idx - 1][aa];
            }
 
        }
 
        memset(visit, false, sizeof(visit));
        visit[r][c] = true;
        solve(r,c);
        cout<<'#'<<t<<' '<<ans<<'\n';
 
    }
    return 0;
}
 

음.. 전에 프로그래머스 방문길이 문제랑 비슷하게 풀었다. dfs 는 시간초과 날거같아서 bfs로 풀었다.

파이프가 연결되어 있어야 진행할 수 있으므로, 방향을 표시하는 클래스를 이용했다.

그래서 입력이 좀 복잡하다 0이면 4방향 모두 이동 불가, 1~7까지는 그림 보고 했다.

 

위까지가 입력 받기

 

1. 방문한 노드는 다시 방문안하므로 visit 배열 사용

2. 현재 위치 방문 표시하고 시작

3. 노드 queue에 현재 위치 push 길이 queue에도 길이 push

 

4. 두개의 queue에서 각각 위치, 길이 pop

만약 길이가 l보다 크면 종료

5. 4방향 탐색 시작

배열 크기를 벗어나지 않고, 방문하지 않았고, 파이프가 연결되어 있으면 방문 체크

노드 queue에 해당 노드 push

길이 queue에 길이 push

ans++

 

길이  L 보다 크지 않을 때 4~5 반복

 

나쁘지 않은 실행시간

1ms도 있던데 대단하네...