[JAVA] SWEA 탈주범 검거

문제 링크

SW Expert Academy

import java.util.*;
import java.io.*;
 
public class Solution {
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
         
        for(int t=1; t<=T; t++) {
            StringTokenizer 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];
            visit = 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());
                Arrays.fill(visit[i], Integer.MAX_VALUE);
            }
 
             
            dfs(R, C, 0);
             
            int ans = 0;
            for(int i=0;i<N;i++) {
                for(int j=0;j<M;j++) {
                    if(visit[i][j]<=L) ans++;
                }
            }
            System.out.println("#"+t+" "+ans);
        }
 
    }
     
    static int N, M, L;
    static int[][] map;
    static int[][] visit;
    static int[][][] pipe = {{{-1,1,0,0}, {0,0,-1,1}}, {{-1,1},{0,0}}, {{0,0},{-1,1}}, {{-1,0},{0,1}}, {{1,0},{0,1}}, {{1,0},{0,-1}}, {{-1,0},{0,-1}}};
     
    public static void dfs(int r, int c, int time) {
        if(time==L) return;
        visit[r][c] = time;
         
        int p = map[r][c]-1;
        for(int i=0; i< pipe[p][0].length;i++) {
            int nr = r + pipe[p][0][i];
            int nc = c + pipe[p][1][i];
             
            if(0<=nr && nr<N && 0<=nc && nc<M && visit[nr][nc]>time && canGo(nr-r, nc-c, map[nr][nc]-1) ) {
                dfs(nr, nc, time+1);
            }
        }
    }
     
    public static boolean canGo(int dr, int dc, int p) {
        if(p<0) return false;
         
        for(int i=0; i< pipe[p][0].length;i++) {
            if(pipe[p][0][i]==(dr*-1) && pipe[p][1][i]==(dc*-1)) return true;
        }
         
        return false;
    }
 
}