SWEA1953.md

탈주범검거

https://swexpertacademy.com/ [1953]

개요

좌표(x, y)가 주어진 탈주범이 이동한다. 지하터널(1~7)이 연결되어 있는 경로만 이동할 수 있으며 처음 한 시간은 제자리(x, y)에 1시간당 1칸을 이동한다. Map의 크기는 세로 N<=50, 가로 M<=50 이며 탈주범이 이동하는 시간 L<=20 이다.

분석

단순한 좌표이동이므로 재귀함수로 조건을 따지며 step==L 까지 함수를 호출하는 방법도 사용할 수 있다.(DFS) (x,y)부터 시작해서 다음좌표들을 큐에 넣으면 step별 모든 노드를 방문하는 BFS로 구현할 수 있다. chk배열을 두어 터널 구조물들을 저장하면 검사에 필요한 코드를 줄일 수 있다. 좌표이동에서는 이동할 때 지도 밖으로 나가는 지를 검사해주어야 한다.

알고리즘

1. chk[8][4]={{1,1,1,1},{1,1,0,0}...}, bang[4][2]={{-1,0},{1,0},{0,-1},{0,1}} //터널연결(상, 하, 좌, 우), 이동(상, 하, 좌, 우)

2. nx=x+bang[i][0], ny=y+bang[i][1] //i는 0~3까지 상, 하, 좌, 우 -> 상, 하, 좌, 우로 갈 곳이 (nx, ny), 원래 위치가 (x,y)

3. chk[map[x][y]][i]==1 && chk[map[nx][ny]][ir]==1 && 안 간곳 이면 이동하며 카운트 및 큐에 nx, ny입력(BFS)//ir은 if문으로 i==0 이면 ir=1, 1이면 0, 2이면 3, 3이면 2 로 i와 반대 방향으로 설정

4. L시간만큼 2~3 반복.

5. 카운트 출력

소스

#include <stdio.h>
 
int bang[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };
int ck[8][4] = { {0,0,0,0},{1,1,1,1},{1,1,0,0},{0,0,1,1},{1,0,0,1},{0,1,0,1},{0,1,1,0},{1,0,1,0} };
int map[60][60], chk[60][60];
int que1[1000][2], que2[1000][2], f, r, ro;
 
int bc(int r, int c, int n, int m)
{
    if (r >= 0 && r < n && c >= 0 && c < m) return 1;
    return 0;
}
 
void push(int x, int y)
{
    que2[r][0] = x;
    que2[r][1] = y;
    ++r;
}
 
void pop(int x, int y)
{
    ++f;
}
void cq()
{
    int i;
    for (i = 0; i < r; i++)
    {
        que1[i][0] = que2[i][0];
        que1[i][1] = que2[i][1];
    }
}
 
int main()
{
    int T, n, m, x, y, l, i, j, k, k2, ct, nx, ny;
    scanf("%d", &T);
    for (i = 1; i <= T; i++)
    {
        scanf("%d%d%d%d%d", &n, &m, &x, &y, &l);
        for (j = 0; j < n; j++)
        {
            for (k = 0; k < m; k++)
            {
                scanf("%d", &map[j][k]);
                chk[j][k] = 0;
            }
        }
 
        ct = 1;
 
        chk[x][y] = 1;
 
        r = 0;
        push(x, y);
        f = 0;
 
        for (j = 2; j <= l; j++)
        {
            cq();
            ro = r;
            r = 0;
            f = 0;
            while(f<ro)
            {
                x = que1[f][0];
                y = que1[f][1];
                for (k = 0; k < 4; k++)
                {
                    if (k == 0) k2 = 1;
                    else if (k == 1) k2 = 0;
                    else if (k == 2) k2 = 3;
                    else k2 = 2;
 
                    nx = x + bang[k][0];
                    ny = y + bang[k][1];
 
                    if (ck[map[nx][ny]][k2]==1 &&ck[map[x][y]][k] == 1 && chk[nx][ny] == 0 && bc(nx, ny,n, m)==1 && map[nx][ny]!=0)
                    {
                        chk[nx][ny] = 1;
                        ++ct;
                        push(nx, ny);
                    }
                }
                f++;
            }
        }
        printf("#%d %d\n", i, ct);
    }
 
}