[SWEA] 1953.탈주범 검거 (java) / BFS

@BFS / 35m

무난한 BFS 문제.

인덱스 조절만 효율적으로 하면 금방 풀 수 있는 문제다.

 

 

문제 링크

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

SW Expert Academy

 

구현 포인트

1. map을 map[x위치][y위치][4방향]인 3차원 boolean형 배열로 입력받았다.

main에서 값을 입력받을 때 switch 문을 활용하여 연결 가능한 부분에만 true값을 넣어줬다.

 

 

2. 방향을 상좌하우로 입력받는다.

이렇게 하면 (지금 방향 + 2) % 4 == 반대편 방향이 된다.

즉, 반대 방향 값을 쉽게 얻을 수 있게 된다.

BFS로 이동할 때, 지금 나의 방향과 이동하려는 칸의 반대 방향이 모두 true면 이동 가능함을 알 수 있다.

아기상어, 톱니바퀴와 비슷한 느낌이다.

 

 

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

public class Solution {
	
	private static class Node {
		int x, y, dir, time;
		public Node(int x, int y, int time) {
			this.x = x;
			this.y = y;
			this.time = time;
		}
	}
	private static int N, M, R, C, L, count;
	private static boolean map[][][], visit[][];
	private static int[] dx = {-1, 0, 1, 0}, dy = {0, -1, 0, 1};
	private static Queue<Node> q;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		for (int t = 1; t <= T; t++) {
			q = new LinkedList<>();
			
			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 boolean[N][M][4];
			visit = new boolean[N][M];
			
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < M; j++) {
					int temp = Integer.parseInt(st.nextToken());
					switch (temp) {
					case 1:
						map[i][j][0] = true; map[i][j][1] = true; map[i][j][2] = true; map[i][j][3] = true;
						break;
					case 2:
						map[i][j][0] = true; map[i][j][2] = true;
						break;
					case 3:
						map[i][j][1] = true; map[i][j][3] = true;
						break;
					case 4:
						map[i][j][0] = true; map[i][j][3] = true;
						break;
					case 5:
						map[i][j][2] = true; map[i][j][3] = true;
						break;
					case 6:
						map[i][j][1] = true; map[i][j][2] = true;
						break;
					case 7:
						map[i][j][0] = true; map[i][j][1] = true;
						break;
					}
				}
			}
			visit[R][C] = true;
			count = 1;
			q.add(new Node(R, C, 1));
			bfs();
			sb.append("#" + t + " " + count + "\n");
		}
		System.out.println(sb);
	}

	private static void bfs() {
		while (!q.isEmpty()) {
			Node temp = q.poll();
			if (temp.time >= L) return;
			
			for (int d = 0; d < 4; d++) {
				int nx = temp.x + dx[d];
				int ny = temp.y + dy[d];
				
				if (nx < 0 || nx >= N || ny < 0 || ny >= M || visit[nx][ny]) continue;
				
				if (map[temp.x][temp.y][d] && map[nx][ny][(d + 2) % 4]) {
					count++;
					visit[nx][ny] = true;
					q.add(new Node(nx, ny, temp.time + 1));
				}
			}
		}
	}
}

 

 

무난한 문제였다. 목표했던 하루 3문제 풀기에 성공했다!

 

끝!