[JAVA] SWEA_1953. 탈주범 검거

 

| 문제 해결방법

 

 

BFS (+ 사방탐색 가능 여부 체크)

 

 

이 문제는 단순한 BFS문제이다.

 

BFS로 탐색하면서 주어진 시간만큼동안 이동할 수 있는 위치의 개수를 출력해주면 된다. 

 

 

단, 

터널의 모양에 따라 다음 위치로의 이동 여부가 결정된다. 

 

 

 

터널은 1번부터 7번까지 다 다른 모양을 가지고 있다.

 

상, 우, 하, 좌 순서로 

터널 모양에 따라 이동 가능한 방향은 true, 이동이 불가한 방향은 false로 저장한 deltas 배열을 사용하였다. 

 

(터널이 1~7번까지 있기 때문에 0번째 열은 자리를 채워주기 위해 임의로 준 값- 사용하지 X)

static boolean[][] deltas = { 
            { false, false, false, false }, 
            { true, true, true, true }, // 1번 터널
            { true, false, true, false }, // 2번 터널
            { false, true, false, true }, // 3번 터널
            { true, true, false, false }, // 4번 터널
            { false, true, true, false }, // 5번 터널
            { false, false, true, true }, // 6번 터널
            { true, false, false, true }  // 7번 터널
};

 

BFS로 탐색하는 과정에서 

터널의 방향에 대해 2번의 검사를 해주어야 한다.

 

1. 터널의 모양에 따른 현재 위치에서의 이동할 수 있는 방향(상, 우, 하, 좌) 체크

2. 이동할 위치의 터널의 모양 체크

 

 

 

 

예를 들어,

 

 

현재 위치에서 위, 아래로 이동이 가능하지만,

위에서의 터널은 좌, 우로만 이동할 수 있는 터널이라면

 

이 길은 이동이 불가한 길이다. 

 

 

 

이 부분을 처리하기 위해

다음 이동할 위치의 터널의 정보를 얻는 과정은 

(i + 2) % 4

연산으로 처리하였다.

 

간단하게 설명하면

	// 사방탐색(상, 우, 하, 좌)
	for (int i = 0; i < 4; i++) {
 
                // 1. 현재 위치의 터널 정보 체크
                if (!deltas[dir][i])
                    continue;
                    
                    
                    
                // 만약, 현재 위치에서 '상향' 이동이 가능하다면, 
                // 다음 이동가능한 위치의 터널은 '하향' 이동이 가능해야한다.
                
                
                // 동일한 방법으로 사방을 우-좌, 좌-우, 상-하, 하-상으로 체크해주면 되기 때문에
                // 현재 방향에서 +2해준 후 4로 나눈 나머지를 사용(index가 4를 넘는 경우를 고려)
                int newI = (i + 2) % 4;
 


 
                // 2. 이동할 위치의 터널 정보 체크
                if (!deltas[newDir][newI])
                    continue;
 
 
      }

이렇게 처리하였다. 

 

[JAVA] 해설 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Solution {
 
    static int N, M, R, C, L, cnt;
    static int[] dr = { -1, 0, 1, 0 }; // 상, 우, 하, 좌
    static int[] dc = { 0, 1, 0, -1 };
    static int[][] arr;
    static boolean[][] visited;
    // 상, 우, 하, 좌
    static boolean[][] deltas = { { false, false, false, false }, { true, true, true, true },
            { true, false, true, false }, { false, true, false, true }, { true, true, false, false },
            { false, true, true, false }, { false, false, true, true }, { true, false, false, true } };
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());
 
        for (int tc = 1; tc <= T; tc++) {
            st = new StringTokenizer(br.readLine());
 
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            R = Integer.parseInt(st.nextToken());
            C = Integer.parseInt(st.nextToken());
            L = Integer.parseInt(st.nextToken());
 
            arr = new int[N][M];
 
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < M; j++) {
                    arr[i][j] = Integer.parseInt(st.nextToken());
 
                }
 
            }
            
	   //BFS 실행
            cnt = 1;
            bfs(R, C);

            // 출력
            sb.append("#" + tc + " ").append(cnt).append("\n");
 
        }
        System.out.println(sb.toString());
 
    }
 
    private static void bfs(int r, int c) {
        Queue<int[]> q = new LinkedList<>();
        visited = new boolean[N][M];
        q.offer(new int[] { r, c, 1 });
        visited[r][c] = true;
 
        while (!q.isEmpty()) {
            int[] point = q.poll();
            int dir = arr[point[0]][point[1]];
            int time = point[2];
 
            if (time == L)
                continue;
 
            for (int i = 0; i < 4; i++) {
 
                // 터널이 갈 수 없는 길인 경우
                if (!deltas[dir][i])
                    continue;
 
                int nr = point[0] + dr[i];
                int nc = point[1] + dc[i];
 
                // 범위 벗어나면 패스
                if (!isIn(nr, nc))
                    continue;
 
                int newDir = arr[nr][nc];
                int newI = (i + 2) % 4;
 
                // 길이 막혔다면
                if (!deltas[newDir][newI])
                    continue;
 
                // 방문 했었다면 패스
                if (visited[nr][nc])
                    continue;
 
                visited[nr][nc] = true;
                q.offer(new int[] { nr, nc, time + 1 });
                cnt++;
 
            }
 
        }
    }
 
    private static boolean isIn(int r, int c) {
        return r >= 0 && r < N && c >= 0 && c < M;
    }
 
}

 

 

[제출] 메모리 및 시간