[SWEA] 1953.탈주범 검거

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

SW Expert Academy

---

import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;

class Solution {
	
	static int N, M, R, C, L, time, answer;
	static int[][] map;
	static Queue<Pair> queue;
	static boolean[][] visited;
	static int[][] dir = {{1,0},{0,1},{-1,0},{0,-1}};	// 아래, 오른쪽, 위, 왼쪽
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int T = sc.nextInt();
		
		for(int i=0; i<T; i++) {
			N = sc.nextInt();
			M = sc.nextInt();
			R = sc.nextInt();
			C = sc.nextInt();
			L = sc.nextInt();
			map = new int[N][M];
			visited = new boolean[N][M];
			queue = new LinkedList<Pair>();
			answer = 1;
			
			for(int j=0; j<N; j++) {
				for(int k=0; k<M; k++) {
					map[j][k] = sc.nextInt();
				}
			}
			if(L==1) {
                System.out.println("#" + (i+1) + " 1");
                continue;
            }
            
			BFS(R, C);
			
			System.out.println("#" + (i+1) + " " + answer);
		}
	}
	
	public static void BFS(int x, int y) {
		queue.offer(new Pair(x, y));
		visited[x][y] = true;
		
		while(!queue.isEmpty()) {
			int len = queue.size();
			L--;
			
			for(int i=0; i<len; i++) {
				Pair p = queue.poll(); 
				int type = map[p.x][p.y];
				
				for(int j=0; j<4; j++) {
					// 아래 오른쪽 위 왼쪽
					if(j==0 && (type==3||type==4||type==7)) continue;
					if(j==1 && (type==2||type==6||type==7)) continue;
					if(j==2 && (type==3||type==5||type==6)) continue;
					if(j==3 && (type==2||type==4||type==5)) continue;
						
					int nx = p.x+dir[j][0];
					int ny = p.y+dir[j][1];
					
					
					if(!isInside(nx, ny) || map[nx][ny] == 0 || visited[nx][ny]) continue;
					int ntype = map[nx][ny];
					if(j==0&&(ntype==3||ntype==5||ntype==6)) continue;
					if(j==1&&(ntype==2||ntype==4||ntype==5)) continue;
					if(j==2&&(ntype==3||ntype==4||ntype==7)) continue;
					if(j==3&&(ntype==2||ntype==6||ntype==7)) continue;
					
//					System.out.println(" x : " + nx + "/ y : " + ny + " / ntype : " +  ntype + " / time : " + L);
					queue.offer(new Pair(nx, ny));
					visited[nx][ny] = true;
					answer++;
				
				}
				
			}
			if(L==1) return;
		}
	}
	
	public static boolean isInside(int x, int y) {
		if(x>=0&&x<N&&y>=0&y<M) return true;
		else return false;
	}
	
}

class Pair {
	int x;
	int y;
	Pair(int x, int y){
		this.x=x;
		this.y=y;
	}
}

---

지도에 터널 구조물 타입이 모양별로 주어졌을 때, 시작 위치를 보고 탈주범이 위치할 수 있는 곳이 몇개인지 구하는 문제입니다. 주어진 시작점에서 BFS를 하면서 구조물 별로 갈 수 있고 없고를 판단할 때 어떻게 할지 몰라서 답변을 찾아본 문제입니다. 중요한 점은 처음 현재 타입의 상하좌우를 확인할 때 될 수 없는 타입이면 continue 하는 것이고, 만약 된다면 다음 상하좌우를 확인해서 다음 타입이 될 수 없는 것을 판단하여 continue하는 것이었습니다. 코드에서 이 부분을 잘 보고 이해해야 합니다. 그리고 마지막에 체크해야 할 부분은, 만약 L=1이었다면 소요된 시간이 1이라는 의미기 때문에 정답은 무조건 1이 나와야 한다는 점입니다.