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

SW Expert Academy

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

public class Solution {
	
	static class Position {
		int x;
		int y;
		
		Position(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	
	static int N, M, L;
	static int[] dx = { 1, 0, -1, 0 }, dy = { 0, -1, 0, 1 };
	static int[][] direction = {
			{ 0 },
			{ 0, 1, 2, 3 },
			{ 1, 3 },
			{ 0, 2 }, 
			{ 0, 1 },
			{ 0, 3 },
			{ 2, 3 }, 
			{ 1, 2 }
	};
	static int[][] board;
	static boolean[][] visited;
	
	private static void bfs(int r, int c) {
		Queue<Position> queue = new LinkedList<>();
		queue.offer(new Position(c, r));
		visited[r][c] = true;
		
		for (int i = 2; i <= L; i++) {
			int size = queue.size();
			for (int j = 0; j < size; j++) {
				Position cur = queue.poll();
				int x = cur.x;
				int y = cur.y;
				for (int d = 0; d < direction[board[y][x]].length; d++) {
					int dir = direction[board[y][x]][d];
					int nx = x + dx[dir];
					int ny = y + dy[dir];
					if (nx < 0 || nx >= M || ny < 0 || ny >= N || visited[ny][nx] || board[ny][nx] == 0) continue;
					for (int k = 0; k < direction[board[ny][nx]].length; k++) {
						if ((dir + 2) % 4 == direction[board[ny][nx]][k]) {
							visited[ny][nx] = true;
							queue.offer(new Position(nx, ny));
						}
					}
				}
			}
		}
	}

	private static int getCount() {
		int cnt = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (visited[i][j])
					cnt+= 1;
			}
		}
		return cnt;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = null;
		
		int T = Integer.parseInt(br.readLine());
		for (int t = 1; t <= T; t++) {
			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());
			
			board = new int[N][M];
			visited = new boolean[N][M];
			
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < M; j++) {
					board[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			bfs(R, C);
			
			sb.append("#").append(t).append(" ");
			sb.append(getCount()).append("\n");
		}
		
		br.close();
		System.out.println(sb.toString());
	}

}