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

1. 문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq 

SW Expert Academy

 

 

 

2. 풀이과정

 

간단한 BFS문제지만, 주의해야 할 점은 현재 칸과 다음 칸이 이어져있는지 확인해야 한다는 점이다. 처음엔 터널만 있으면 간다 생각하고 풀었다가 문제를 다시 읽고 수정했다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class SWEA1953 {
	static int N, M, L, map[][], result;
    static int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};//상 우 하 좌
    static boolean tunnel[][];
     
    public static void bfs(int sx, int sy) {
        Queue<int[]> q = new LinkedList<>();
        boolean visited[][] = new boolean[N][M];
        q.offer(new int[] {sx, sy});
        visited[sx][sy] = true;
         
        while(!q.isEmpty()) {
            int size = q.size();
            result+=size;
            if(--L==0) break;
            for(int s=0; s<size; s++) {
                int[] pos = q.poll();
                int x = pos[0];
                int y = pos[1];
                int t = map[x][y];//tunnel 번호
                for(int i=0; i<4; i++) {
                    if(tunnel[t][i]) {//방향이 유효하면
                        int nx = x + dx[i];
                        int ny = y + dy[i];
                        if(0<=nx && nx<N && 0<=ny && ny<M) {
                            //터널이 없거나, 이미 방문했거나, 현재 칸과 다음칸의 터널이 이어져있지 않으면 넘어감
                            if(map[nx][ny]==0 || visited[nx][ny] || !tunnel[map[nx][ny]][(i+2)%4]) {
                                continue;
                            }
                            visited[nx][ny] = true;
                            q.offer(new int[] {nx, ny});
                        }
                    }
                }
            }
        }
    }
 
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());
        tunnel = new boolean[8][];
        //방향들의 index값
        tunnel[1] = new boolean[]{true, true, true, true};
        tunnel[2] = new boolean[]{true, false, true, false};
        tunnel[3] = new boolean[]{false, true, false, true};
        tunnel[4] = new boolean[]{true, true, false, false};
        tunnel[5] = new boolean[]{false, true, true, false};
        tunnel[6] = new boolean[]{false, false, true, true};
        tunnel[7] = new boolean[]{true, false, false, true};
     
        for(int t=1; t<=T; t++) {
            sb.append("#").append(t).append(" ");
            result = 0;
            //
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());//가로세로
            M = Integer.parseInt(st.nextToken());
            int R = Integer.parseInt(st.nextToken());//맨홀 위치
            int C = Integer.parseInt(st.nextToken());
            L = Integer.parseInt(st.nextToken());//소요시간
             
            map = new int[N][M];
            for(int i=0;i<N;i++) {
                st = new StringTokenizer(br.readLine());
                for(int j=0;j<M;j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            bfs(R, C);
            sb.append(result).append("\n");
        }
        System.out.println(sb.toString());
    }
}