[SWEA] 1953. 탈주범 검거.java

SWEA에서 사람 탈주범 검거를 자바를 통해 풀어 보았다. 

 

SW Expert Academy

 

1953. 탈주범 검거.java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

1953번 탈주범 검거

문제

교도소로 이송 중이던 흉악범이 탈출하는 사건이 발생하여 수색에 나섰다.

탈주범은 탈출한 지 한 시간 뒤, 맨홀 뚜껑을 통해 지하터널의 어느 한 지점으로 들어갔으며,

지하 터널 어딘가에서 은신 중인 것으로 추정된다.

터널끼리 연결이 되어 있는 경우 이동이 가능하므로 탈주범이 있을 수 있는 위치의 개수를 계산하여야 한다.

탈주범은 시간당 1의 거리를 움직일 수 있다.

지하 터널은 총 7 종류의 터널 구조물로 구성되어 있으며 각 구조물 별 설명은 [표 1]과 같다.

설명

기본적으로 BFS를 통해 탈주번이 이동할 수 있는 파이프를 세는 문제이다. 단 각 파이프는 이동할 수 있는 방향이 정해져 있으며 해당 방향으로 이동하려면 다음 파이프와 이어져 있어야 한다. 다음 그림을 보자.

 

(0,1)에서 파이프는 위 방향을 향하고 있으나 (0,0)에 있는 파이프와 연결되어 있지 않기 때문에 (0,1)에서 (0,0)으로는 이동할 수 없다. 이를 확인하기 위해 다음 이동할 위치에 있는 파이프가 현재 파이프가 가는 방향의 반대 방향으로 갈 수 있는지 확인했다. 만약 이 조건을 만족한다면 해당 파이프로 방문이 가능하다.

 

출발점을 기준으로 0으로 시작하여 BFS를 타고 1씩 증가시켜주며 파이프들을 방문했다. 그렇게 방문한 파이프의 값들에 대해서 L보다 작은 파이프만 세준다면 그게 답이다.

 

코드

//1953. 탈주범 검거.java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.StringTokenizer;

public class 탈주범_검거_1953 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		int T = Integer.parseInt(br.readLine());
		for(int t=1;t<=T;t++) {
			st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken());
			int M = Integer.parseInt(st.nextToken());
			int R = Integer.parseInt(st.nextToken());
			int C = Integer.parseInt(st.nextToken());
			int L = Integer.parseInt(st.nextToken());
			
			int[][] tunnel = new int[N][M];
			for(int i=0;i<N;i++) {
				st = new StringTokenizer(br.readLine());
				for(int j=0;j<M;j++) {
					tunnel[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			int[][] visit = new int[N][M];
			bfs(new point(R,C), tunnel, visit);
			
			int count=0;
			for(int i=0;i<N;i++) {
				for(int j=0;j<M;j++) {
					if(visit[i][j]<=L && visit[i][j]!=0 && tunnel[i][j]!=0)count++;
				}
			}
			sb.append("#"+t+" "+count+"\n");
			
		}
		System.out.println(sb.toString());
	}
	
	static void bfs(point start, int[][] tunnel, int[][] visit) {
		int[] di = {0,0,1,-1};
		int[] dj = {1,-1,0,0};
		Map<Integer, int[]> map = new HashMap<>();
		map.put(1, new int[] {0,1,2,3});
		map.put(2, new int[] {2,3});
		map.put(3, new int[] {0,1});
		map.put(4, new int[] {0,3});
		map.put(5, new int[] {0,2});
		map.put(6, new int[] {1,2});
		map.put(7, new int[] {1,3});
		
		visit[start.i][start.j]=1;
		Queue<point> q = new LinkedList<point>();
		q.add(start);
		while(!q.isEmpty()) {
			point now = q.poll();
			int D = tunnel[now.i][now.j];
			for(int d=0;d<map.get(D).length;d++) {
				int nextI = now.i+di[map.get(D)[d]];
				int nextJ = now.j+dj[map.get(D)[d]];
				if(0<=nextI&&nextI<tunnel.length&&0<=nextJ&&nextJ<tunnel[0].length) {
					
					//구조물이 있는가 + 처음 방문하는가
					if(tunnel[nextI][nextJ]!=0 && visit[nextI][nextJ]==0) {
						//연결되어 있는가
						boolean check = false;
						int to = tunnel[nextI][nextJ];
						int nextD;
						if(map.get(D)[d]==0)nextD=1;
						else if(map.get(D)[d]==1)nextD=0;
						else if(map.get(D)[d]==2)nextD=3;
						else nextD=2;
						
						for(int k=0;k<map.get(to).length;k++) {
							if(map.get(to)[k]==nextD)
								check=true;
						}
						
						if(check){
							visit[nextI][nextJ]=visit[now.i][now.j]+1;
							q.add(new point(nextI,nextJ));
						}
					}
				}
			}
		}
	}
	
	static class point{
		int i;
		int j;
		point(int i, int j){
			this.i=i;
			this.j=j;
		}
	}
}