[SWEA] 탈주범 검거

👀 문제 설명

문제

로그인해야 문제를 볼 수 있다.

 

✍🏻풀이

BFS를 사용해 각 칸까지 이동하는데 걸리는 시간을 구한다.

 

map[r][c]는 지하 터널의 상태를 저장하는 배열이고, time[r][c]는 (r, c)까지 이동하는데 걸리는 시간을 저장하는 배열이다.

이 배열들을 사용해 BFS를 구현하면 된다.

 

map[r][c]가 터널 구조물이라면(1~7이라면) 타입에 맞게 인접한 nextX, nextY를 구해준다.

isPossibleScope은 (nextX, nextY)가 이동할 수 있는 곳인지 확인하는 메서드이다. (nextX, nextY)가 범위를 벗어나거나, 이미 방문한 곳이거나, 이동할 수 없는 곳(구조물이 없는 경우. 즉, map[nextX][nextY] = 0)이라면 false를, 아니라면(이동할 수 있다면) true를 리턴한다.

up(), down(), left(), right() 메서드는 각각 상, 하, 좌, 우로 이동하는 메서드이다.

(cur[0], cur[1])이 위쪽으로 이동하려면, 위(nextX, nextY)의 터널 구조물 타입은 1, 2, 5, 6 중 하나여야 한다.

아래로 이동하려면, 아래(nextX, nextY)의 구조물 타입이 1, 2, 4, 7 중 하나여야 하고,

왼쪽으로 이동하려면, 왼쪽(nextX, nextY)의 구조물 타입이 1, 3, 4, 5 중 하나여야 한다.

오른쪽으로 이동하려면, 오른쪽(nextX, nextY)의 구조물 타입이 1, 3, 6, 7 중 하나여야 한다.

(nextX, nextY)가 이것들을 만족한다면, time[nextX][nextY]를 time[cur[0]][cur[1]] + 1로 바꾸고, 덱에 (nextX, nextY)를 넣는다.

* 상, 하, 좌, 우로 이동하기 전에 time[cur[0]][cur[1]]이 L이라면, return해준다. (L시간동안 가능한 곳을 모두 방문했다는 뜻이므로)

 

L 시간동안 이동할 수 있는 곳에 모두 방문했다면, time[i][j]를 확인한다. time[i][j]가 0이 아니라면, L시간 내에 이동할 수 있는 곳이므로 ans + 1을 해주면 된다.

 

코드

package swea;

// 탈주범 검거 (https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq&categoryId=AV5PpLlKAQ4DFAUq&categoryType=CODE&problemTitle=%ED%83%88%EC%A3%BC%EB%B2%94+%EA%B2%80%EA%B1%B0&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 )

import java.util.*;
import java.io.*;

public class SWEA_1953 {
	
	private static int N, M, R, C, L;
	private static int[][] map;
	private static int[][] time;
	private static int[] dx = { -1, 1, 0, 0 }; // 상, 하, 좌, 우
	private static int[] dy = { 0, 0, -1, 1 }; // 상, 하, 좌, 우
	private static Deque<int[]> deque = new ArrayDeque<>();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		int T;

		T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {
			// input
			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());
			
			map = new int[N][M];
			time = new int[N][M];
			deque.clear();
			
			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());
				}
			}
			
			// solve
			move();
			int ans = 0;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (time[i][j] != 0) {
						ans++;
					}
				}
			}
			bw.write("#" + tc + " " + ans + "\n");
		}

		bw.flush();
		bw.close();
	}
	
	private static void move() {
		deque.offer(new int[] { R, C });
		time[R][C] = 1;
		
		while (!deque.isEmpty()) {
			int[] cur = deque.poll();
			if (time[cur[0]][cur[1]] == L) return;
			
			switch (map[cur[0]][cur[1]]) {
			case 1:
				up(cur);
				down(cur);
				left(cur);
				right(cur);
				break;
			case 2:
				up(cur);
				down(cur);
				break;
			case 3:
				left(cur);
				right(cur);
				break;
			case 4:
				up(cur);
				right(cur);
				break;
			case 5:
				down(cur);
				right(cur);
				break;
			case 6:
				down(cur);
				left(cur);
				break;
			case 7:
				up(cur);
				left(cur);
				break;
			}
		}
	}
	
	private static boolean isPossibleScope(int nextX, int nextY) {
		// 범위를 벗어나거나, 이미 방문했거나, 이동할 수 없는 곳(구조물이 없는 경우)이라면 return false
		if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= M || time[nextX][nextY] != 0 || map[nextX][nextY] == 0) return false;
		
		return true;
	}
	
	private static void up(int[] cur) {
		int nextX = cur[0] + dx[0];
		int nextY = cur[1] + dy[0];
		
		if (!isPossibleScope(nextX, nextY)) return;
	
		if (map[nextX][nextY] == 1 || map[nextX][nextY] == 2 || map[nextX][nextY] == 5 || map[nextX][nextY] == 6) {
			time[nextX][nextY] = time[cur[0]][cur[1]] + 1;
			deque.offer(new int[] { nextX, nextY });
		}
	}
	
	private static void down(int[] cur) {
		int nextX = cur[0] + dx[1];
		int nextY = cur[1] + dy[1];
		
		if (!isPossibleScope(nextX, nextY)) return;
	
		if (map[nextX][nextY] == 1 || map[nextX][nextY] == 2 || map[nextX][nextY] == 4 || map[nextX][nextY] == 7) {
			time[nextX][nextY] = time[cur[0]][cur[1]] + 1;
			deque.offer(new int[] { nextX, nextY });
		}
	}
	
	private static void left(int[] cur) {
		int nextX = cur[0] + dx[2];
		int nextY = cur[1] + dy[2];
		
		if (!isPossibleScope(nextX, nextY)) return;
		
		if (map[nextX][nextY] == 1 || map[nextX][nextY] == 3 || map[nextX][nextY] == 4 || map[nextX][nextY] == 5) {
			time[nextX][nextY] = time[cur[0]][cur[1]] + 1;
			deque.offer(new int[] { nextX, nextY });
		}
	}
	
	private static void right(int[] cur) {
		int nextX = cur[0] + dx[3];
		int nextY = cur[1] + dy[3];
		
		if (!isPossibleScope(nextX, nextY)) return;
	
		if (map[nextX][nextY] == 1 || map[nextX][nextY] == 3 || map[nextX][nextY] == 6 || map[nextX][nextY] == 7) {
			time[nextX][nextY] = time[cur[0]][cur[1]] + 1;
			deque.offer(new int[] { nextX, nextY });
		}
	}
	
}