[Algorithm] SW Expert Academy - 1953. [모의 SW 역량테스트] 탈주범 검거 해설

삼성 SW 모의 테스트

#1953 - 탈주범 검거

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

사용한 개념

1. BFS탐색

2. 시뮬레이션

이 문제에서 2가지 포인트만 알면 됩니다..

1. 각 파이프마다 이동할 수 있는 방향이 정해져 있다는 것

2. 정해진 방향으로 넘어가더라도 넘어간 파이프의 모양이 연결되어 있지 않다면 실제로 넘어갈 수 없다.

이 2가지를 조건을 걸어서 필터를 해줘야합니다..

아래는 전체소스 입니다.

package SWE;

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;

public class SWTest_1953 {

	static int[] dX = {-1,0,1,0};
	static int[] dY = {0,1,0,-1};
	static int ansList[];
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int tc = Integer.parseInt(br.readLine());
		ansList = new int[tc];
		
		for(int t=0; t<tc; t++){
			String str = br.readLine();
			String[] strArr = str.split(" ");
			
			int h = Integer.parseInt(strArr[0]);
			int w = Integer.parseInt(strArr[1]);
			int mX = Integer.parseInt(strArr[2]);
			int mY = Integer.parseInt(strArr[3]);
			int time = Integer.parseInt(strArr[4]);
			
			int[][] map = new int[h][w];
			for(int i=0; i<map.length; i++){
				String str1 = br.readLine();
				String[] strArr1 = str1.split(" ");
				for(int j=0; j<map[0].length; j++){
					map[i][j] =  Integer.parseInt(strArr1[j]);
				}
			}
			
			LinkedList<Point> q = new LinkedList<>();
			q.add(new Point(mX, mY));
			
			int[][] check = new int[h][w];
			
			int size = q.size();
		
			while(!q.isEmpty()){
				Point p = q.poll();
				check[p.x][p.y] = 1;
				for(int i=0; i<4; i++){
					int v = map[p.x][p.y];
					if(v==2 && (i==1 || i==3))continue;
					if(v==3 && (i==0 || i==2))continue;
					if(v==4 && (i==2 || i==3))continue;
					if(v==5 && (i==0 || i==3))continue;
					if(v==6 && (i==0 || i==1))continue;
					if(v==7 && (i==1 || i==2))continue;
					
					int nX = p.x + dX[i];
					int nY = p.y + dY[i];
					if(-1<nX && nX<map.length && -1<nY && nY<map[0].length &&
							map[nX][nY] != 0 && check[nX][nY] == 0){
						if(checkPipe(v, i, map[nX][nY]))
						q.add(new Point(nX, nY));
					}
				}
				size--;
				if(size == 0){
					time--;
					size = q.size();
				}
				if(time == 0){
					break;
				}
			}
			int ans = 0;
			for(int i=0; i<check.length; i++){
				for(int j=0; j<check[0].length; j++){
					if(check[i][j] == 1)ans++;
				}
			}
			ansList[t] = ans;
			
		}//tc-end
		for(int i=0; i<ansList.length; i++){
			System.out.println("#"+(i+1)+" "+ansList[i]);
		}

	}
	private static boolean checkPipe(int v, int i, int nV) {
		
		if(i==0  && (nV == 3 || nV == 4 || nV == 7)) return false;
		if(i==1  && (nV == 2 || nV == 4 || nV == 5)) return false;
		if(i==2  && (nV == 3 || nV == 5 || nV == 6)) return false;
		if(i==3  && (nV == 2 || nV == 6 || nV == 7)) return false;
		
		return true;
	}


}