[SWEA] JAVA - 1953. [모의 SW 역량테스트] 탈주범 검거

생각

파이프는 상하좌우 네가지 방향성을 가지고 있습니다. 파이프가 가질 수 있는 방향 상태의 조합을 비트마스킹으로 표현하여 상하좌우 -> 1111 과 같이 나타냈습니다.

즉, 상 : 1000, 하 : 0100, 좌 : 0010, 우: 0001 로 나타내었고 파이프의 형태에 따라 OR 연산으로 갈 수 있는 방향에는 비트를 1로 설정하여 초기화 시켰습니다.

 

탈주범의 시작위치로부터 주어진 시간까지 어떤 칸을 갈 수 있는지는 BFS 를 사용하여 문제를 풀었습니다.

 

BFS 내부에서 다음칸으로 갈수있을지 체크를 할 때 파이프의 연결성을 체크하는 메소드를 만들었습니다. 갈려고 하는 칸과 현재의 방향값 비트를 파라미터로 받아 다음 칸으로 갈수있는지를 체크해줬습니다.

현재 방향값 비트가 1000일때 위쪽 방향을 나타내므로 다음칸은 아래칸 방향 비트가 켜져있어야 하므로 if((bit & (1<<2)) > 0) 과 같이 체크했습니다.

 

Java Code

package com.java.algorithm;

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

public class SWEA_1953_탈주범검거 {
	static int R,C;
	static int my,mx;
	static int time;
	static int[][] map;

	static int[] dy = {0,0,1,-1};
	static int[] dx = {1,-1,0,0};
	static int up = 1<<3; 
	static int down = 1<<2; 
	static int left = 1<<1; 
	static int right = 1<<0;
	
	static int[] pipe = {
			0, 
			up|down|left|right,
			up|down,
			left|right,
			up|right,
			down|right,
			down|left,
			up|left
	};
	
	static class Pos{
		int y,x,t;

		public Pos(int y, int x, int t) {
			super();
			this.y = y;
			this.x = x;
			this.t = t;
		}
		
	}
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		StringBuilder sb = new StringBuilder();
		int TC = Integer.parseInt(br.readLine());
		for (int t = 1; t <= TC; t++) {
			st = new StringTokenizer(br.readLine(), " ");
			R = Integer.parseInt(st.nextToken());
			C = Integer.parseInt(st.nextToken());
			my = Integer.parseInt(st.nextToken());
			mx = Integer.parseInt(st.nextToken());
			time = Integer.parseInt(st.nextToken());
			
			map = new int[R][C];
			for (int i = 0; i < R; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				for (int j = 0; j < C; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
					if(map[i][j] > 0) {
						map[i][j] = pipe[map[i][j]];
					}
				}
			}
			
			
			
			sb.append("#").append(t).append(" ").append(solve()).append("\n");
//			int test = 0;
//			System.out.println();
//			for (int i = 0; i < R; i++) {
//				for (int j = 0; j < C; j++) {
//					System.out.print(visited[i][j] + " ");
//					if(visited[i][j]) test++;
//				}
//				System.out.println();
//			}
//			System.out.println("test : " + test);
		}
		System.out.println(sb);

	}
	private static int solve() {
		Queue<Pos> q = new LinkedList<>();
		boolean[][] visited = new boolean[R][C];
		
		q.add(new Pos(my,mx,1));
		visited[my][mx] = true;
		
		int cnt = 1;

		while(!q.isEmpty()) {
			Pos now = q.poll();
			int y = now.y;
			int x = now.x;
			int pipeNum = map[y][x]; // 파이프 방향 비트 조합 상태 (상하좌우)
			
			if(now.t == time) return cnt;
			
			for (int i = 0; i < 4; i++) { // i : 3 상 ,2 하,1 좌, 0 우
				if((pipeNum & (1<<i)) > 0) {
					int ny = y + dy[i];
					int nx = x + dx[i];

					if(ny >= R || ny < 0 || nx >= C || nx < 0) continue;
					//파이프 연결성 체크
					int nextPipe = map[ny][nx];
					if(map[ny][nx] > 0 && !visited[ny][nx]) {
						if(check(nextPipe, i)) {
							visited[ny][nx] = true;
							q.add(new Pos(ny,nx,now.t+1));
							cnt++;
						}

					}
					

				}
			}
			
			
		}
		return cnt;

	}
	//bit : 연결하려는 다음 파이프 비트 조합 상태, dir : 현재 확인해야하는 방향 비트 
	private static boolean check(int bit, int dir) { // // dir : 3 상 ,2 하,1 좌, 0 우
		switch (dir) {
			case 0:
				//좌 연결되야함
				if((bit & (1<<1)) > 0) return true;
				break;
			case 1:
				//우 연결되야함
				if((bit & (1<<0)) > 0) return true;
				break;
			case 2:
				//상 연결되야함
				if((bit & (1<<3)) > 0) return true;
				break;
			case 3:
				//하 연결되야함
				if((bit & (1<<2)) > 0) return true;
				break;
		}
		
		return false;
	}

}