SWEA_탈주범검거_1953

1. 과정

- 현재 칸에서 갈 수 있는 방향과, 다음 칸에서 현재칸을 받을 수 있는지 확인하는것이 이 문제의 핵심이다.

- 크게 어려울것 없는 bfs 응용 문제이다.

 

2. 구현

언어 : JAVA

메모리 : 27,668 kb

실행시간 : 152 ms

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

public class SWEA_탈주범검거_1953_O {
	static int R, C, sr, sc, L, answer;
	static int[][] map;
	static int[] dr = { -1, 1, 0, 0 };
	static int[] dc = { 0, 0, -1, 1 };
	static boolean[][] visit;

	static class Pair {
		int r, c;

		public Pair(int r, int c) {
			this.r = r;
			this.c = c;
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for (int testCase = 1; testCase <= T; ++testCase) {
			String[] s = br.readLine().split(" ");
			R = Integer.parseInt(s[0]);
			C = Integer.parseInt(s[1]);
			sr = Integer.parseInt(s[2]);
			sc = Integer.parseInt(s[3]);
			L = Integer.parseInt(s[4]);
			map = new int[R][C];
			visit = new boolean[R][C];
			for (int i = 0; i < R; ++i) {
				s = br.readLine().split(" ");
				for (int j = 0; j < C; ++j) {
					map[i][j] = Integer.parseInt(s[j]);
				}
			}
			solve();
			System.out.println("#" + testCase + " " + answer);
		}
	}

	private static void solve() {
		Queue<Pair> q = new LinkedList<>();
		q.add(new Pair(sr, sc));
		visit[sr][sc] = true;
		answer = 1;
		ArrayList<Integer> checkList = new ArrayList<Integer>();
		// level로 최대 L초까지 계산한다.
		int level = 1;
		while (!q.isEmpty()) {
			// 현재 레벨과 L과 같으면 탈출
			if(level==L)
				break;
			int qSize = q.size();
			for (int k = 0; k < qSize; ++k) {
				Pair p = q.poll();
				int r = p.r;
				int c = p.c;
				int hallNum = map[r][c];
				checkList.clear();
				// 터널 번호에 따라서 그 방향만 탐색한다.
				switch (hallNum) {
				case 0:
					break;
				case 1:
					checkList.add(0);
					checkList.add(1);
					checkList.add(2);
					checkList.add(3);
					break;
				case 2:
					checkList.add(0);
					checkList.add(1);
					break;
				case 3:
					checkList.add(2);
					checkList.add(3);
					break;
				case 4:
					checkList.add(0);
					checkList.add(3);
					break;
				case 5:
					checkList.add(1);
					checkList.add(3);
					break;
				case 6:
					checkList.add(1);
					checkList.add(2);
					break;
				case 7:
					checkList.add(0);
					checkList.add(2);
					break;
				}
				int tr, tc;
				for (int i = 0; i < checkList.size(); ++i) {
					int dir = checkList.get(i);
					tr = r + dr[dir];
					tc = c + dc[dir];
					if (tr < 0 || tc < 0 || tr >= R || tc >= C || visit[tr][tc])
						continue;
					// 다음칸에서 받을 수 있는지 체크해야한다.
					// 예를들어 dir==0이면 상 방향이므로 윗칸 입장에서는 아랫쪽으로 터널이 나 있어야 한다.
					if (dir == 0 && (map[tr][tc] == 1 || map[tr][tc] == 2 || map[tr][tc] == 5 || map[tr][tc] == 6)) {
						q.add(new Pair(tr, tc));
						visit[tr][tc] = true;
						answer++;
					} else if (dir == 1
							&& (map[tr][tc] == 1 || map[tr][tc] == 2 || map[tr][tc] == 4 || map[tr][tc] == 7)) {
						q.add(new Pair(tr, tc));
						visit[tr][tc] = true;
						answer++;
					} else if (dir == 2
							&& (map[tr][tc] == 1 || map[tr][tc] == 3 || map[tr][tc] == 4 || map[tr][tc] == 5)) {
						q.add(new Pair(tr, tc));
						visit[tr][tc] = true;
						answer++;
					} else if (dir == 3
							&& (map[tr][tc] == 1 || map[tr][tc] == 3 || map[tr][tc] == 6 || map[tr][tc] == 7)) {
						q.add(new Pair(tr, tc));
						visit[tr][tc] = true;
						answer++;
					}
				}
			}
			level++;
		}
	}
}