[SWEA] 1953. 탈주범 검거

문제주소: 클릭!

SW Expert Academy

멘홀 뚜껑으로 들어간 탈주범이 제한시간 동안 이동할 수 있는 블럭의 크기를 세는 문제입니다.

큐를 사용한 BFS 탐색기법을 사용하여 갈 수 있는 모든 경우를 시간별로 시뮬레이션 해봄으로써 어디까지 이동할 수 있는지를 알 수 있습니다.

 

1). BFS를 할 때는 가장 중요한 아이디어가

 

큐에 어떤 것을 집어넣을 것인가?

인 것 같습니다.

 

저는 주로 int 배열을 사용하여 데이터를 저장합니다.

그래서 큐에서 다음과 같은 데이터를 빼서 이를 참고하여 다음 길을 찾아갈 수 있습니다.

int head[] = q.poll();
int y = head[0];
int x = head[1];
int shape = head[2];
int time = head[3];

현재 지점의 y,x 좌표와 현재 시각, 현재 파이프의 모양을 넣어주었습니다.

 

 

2). 방문했던 지점을 기억해둬야 할 것 같습니다.

 방문한 지점은 인풋으로 저장했던 int[][] map 의 값을 -1로 바꾸고 모든 계산이 끝났을 때, -1의 개수를 세면 정답을 알 수 있을 것 같습니다.

 

3). 언제 탐색을 종료할 것인가?

 종료조건을 주지 않으면 계속 시각을 늘려가면서 무한루프에 빠지고 말 것입니다.

문제에서는 L시간 이내에 도둑이 위치할 수 있는 지점의 개수를 구하라고 하였으므로

시뮬레이션을 L시간만 하면 될 것 같습니다.

 

다행히도 우리는 큐에 시각을 저장한 정보를 넣어두었기 때문에

큐에서 뺀 시간값이 L이 되면 계산을 종료하고 -1을 세러 가면 될 것 같습니다.

 

4). 모양마다 갈 수 있는 방향이 정해져 있다.

 문제에서 제시했던 것처럼 모양값(shape)이 4인 경우에는 'ㄴ' 자 모양의 파이프로

이 파이프에서는 위 또는 오른쪽으로만 이동할 수 있습니다.

이와같은 방법으로 다른 모양들도 각자 갈 수 있는 방향을 알 수 있습니다.

 

따라서 모양에 따라 갈 수 있는 방향으로 이동시켜주는 함수를 만들어주면 코드도 깔끔하고 디버깅도

편할 것 같습니다.

 

switch 문을 통해 해당 모양에 맞는 방향으로 이동시키는 코드를 작성해봅시다.

				// 갈 수 있는 길을 탐색한다.
                switch(shape)
                {
                    // ↕↔
                    case 1:
                        for (int i = 0; i < 4; i++) 
                        	go(y, x, time, i);
                        break;
                    // ↕
                    case 2:
                    	go(y, x, time, 0);
                    	go(y, x, time, 2);
                        break;
                    // ↔
                    case 3:
                        go(y, x, time, 1);
                        go(y, x, time, 3);
                        break;
                    // └
                    case 4:
                    	go(y, x, time, 0);
                    	go(y, x, time, 1);
                        break;
                    // ┌
                    case 5:
                    	go(y, x, time, 1);
                    	go(y, x, time, 2);
                    	break;
                    // ┐
                    case 6:
                    	go(y, x, time, 2);
                    	go(y, x, time, 3);
                        break;
                    // ┘
                    case 7:
                    	go(y, x, time, 0);
                    	go(y, x, time, 3);
                        break;
                }
            }

 

public static int[][] dir = {{-1,0},{0,1},{1,0},{0,-1}};
public static int[][] canGo = {{1,2,5,6},{1,3,6,7},{1,2,4,7},{1,3,4,5}};
public static void go(int y, int x, int time, int direction)
{
    int ny = y + dir[direction][0];
    int nx = x + dir[direction][1];
    // 범위를 벗어나지 않고 이미 왔던 길이 아닐 경우
    if(inRange(ny, nx) && map[ny][nx] != -1)
    {
    	// 가려고 하는 곳의 파이프 모양
    	int ns = map[ny][nx];
    	for (int i = 0; i < 4; i++) 
    	{
    		// 그 모양으로 갈 수 있는 파이프는 canGo에 정해져있음. 갈 수 있는 길이면 가본다.
    		if(ns == canGo[direction][i])
    			q.add(new int[] {ny,nx,ns,time+1});
		}
    }
}

 

5). Solution

 
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Solution
{
    public static int Y,X;
    public static int[][] map;
    public static Queue<int[]> q;
    
    public static void main(String[] args) throws Exception
    {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int tc = Integer.parseInt(br.readLine());
        for (int t = 1; t <= tc; t++)
        {
            sb.append("#").append(t).append(" ");
            ///////////////////////////////////////////////////////////////////////
            StringTokenizer st = new StringTokenizer(br.readLine());
            Y = Integer.parseInt(st.nextToken());
            X = Integer.parseInt(st.nextToken());
            int R = Integer.parseInt(st.nextToken());
            int C = Integer.parseInt(st.nextToken());
            int L = Integer.parseInt(st.nextToken());
            
            q = new LinkedList<>();
            map = new int[Y][X];
            for (int y = 0; y < Y; y++)
            {
                st = new StringTokenizer(br.readLine());
                for (int x = 0; x < X; x++)
                    map[y][x] = Integer.parseInt(st.nextToken());
            }
            
            q.add(new int[]{R, C, map[R][C], 0});  // 멘홀의 위치를 시작점으로 한다.
            while (!q.isEmpty())
            {
                int head[] = q.poll();
                int y = head[0];
                int x = head[1];
                int shape = head[2];
                int time = head[3];

                // 종료조건
                if(time == L) break;

                // 방문체크
                map[y][x] = -1;

                // 갈 수 있는 길을 탐색한다.
                switch(shape)
                {
                    // ↕↔
                    case 1:
                        for (int i = 0; i < 4; i++) 
                        	go(y, x, time, i);
                        break;
                    // ↕
                    case 2:
                    	go(y, x, time, 0);
                    	go(y, x, time, 2);
                        break;
                    // ↔
                    case 3:
                        go(y, x, time, 1);
                        go(y, x, time, 3);
                        break;
                    // └
                    case 4:
                    	go(y, x, time, 0);
                    	go(y, x, time, 1);
                        break;
                    // ┌
                    case 5:
                    	go(y, x, time, 1);
                    	go(y, x, time, 2);
                    	break;
                    // ┐
                    case 6:
                    	go(y, x, time, 2);
                    	go(y, x, time, 3);
                        break;
                    // ┘
                    case 7:
                    	go(y, x, time, 0);
                    	go(y, x, time, 3);
                        break;
                }
            }

            // 방문했던 지점(-1)을 센다.
            int cnt = 0;
            for (int y = 0; y < Y; y++)
            {
            	for (int x = 0; x < X; x++)
            	{
            		if (map[y][x] == -1)
                        cnt++;
            	}
            }
            ///////////////////////////////////////////////////////////////////////
            sb.append(cnt).append("\n");
        }
        bw.write(sb.toString());
        bw.flush();
    }

    // 범위 체크 및 디버깅 함수
    public static boolean inRange(int y, int x) { return (0 <= y && y < Y) && (0 <= x && x < X) && map[y][x] != 0; }
    public static void print(int[][] map) { for(int y = 0; y < Y; y++) { for(int x = 0; x < X; x++) System.out.printf("%2d ", map[y][x]);System.out.println(); }System.out.println(); }
    // 탐색 함수
    public static int[][] dir = {{-1,0},{0,1},{1,0},{0,-1}};
    public static int[][] canGo = {{1,2,5,6},{1,3,6,7},{1,2,4,7},{1,3,4,5}};
    public static void go(int y, int x, int time, int direction)
    {
    	int ny = y + dir[direction][0];
    	int nx = x + dir[direction][1];
    	// 범위를 벗어나지 않고 이미 왔던 길이 아닐 경우
    	if(inRange(ny, nx) && map[ny][nx] != -1)
    	{
    		// 가려고 하는 곳의 파이프 모양
    		int ns = map[ny][nx];
    		for (int i = 0; i < 4; i++) 
    		{
    			// 그 모양으로 갈 수 있는 파이프는 canGo에 정해져있음. 갈 수 있는 길이면 가본다.
    			if(ns == canGo[direction][i])
    				q.add(new int[] {ny,nx,ns,time+1});
			}
    	}
    }
}