[SWEA] 1953 - 탈주범검거

[문제링크]

SW Expert Academy

 

0. 현재 파이프의 모양 - 인접 파이프의 모양 에 따라 갈수 있는지 없는지 여부가 결정된다

  - 총 4방향이므로, 4개의 bit에 bitmask로 저장해 정보를 나타낸다.

 

1. 입력값(0~7)에 따라 해당하는 bitmask정보를 부여한다

 

2. 시작점에서 time만큼 bfs를 돌며

  - 현재 노드에서 상/하/좌/우 통로가 존재하고 + 진행 노드에서 하/상/우/좌 통로가 존재한다면

  - 진행 가능, 큐에 넣는다

  - 방문체크 대신 큐에 넣을때 자기 위치의 값을 0으로 바꿔 재방문을 방지한다

 

3. time이 다 지났다면 (혹은 도중에 탐색을 마쳐 qu가 비었다면)

  - 방문할때마다 1씩 증가시켜준 cnt를 출력, 종료한다

 

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

public class Solution{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int tc = pint(br.readLine());
		for (int testcase = 1; testcase <= tc; testcase++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int n = pint(st.nextToken());
			int m = pint(st.nextToken());
			int x = pint(st.nextToken())+1;
			int y = pint(st.nextToken())+1;
			int t = pint(st.nextToken());
			
			int[][] map = new int[n+2][m+2];
			
			for (int i = 1; i < n+1; i++) {
				st=new StringTokenizer(br.readLine()," ");
				for (int j = 1; j < m+1; j++) {
					int temp = pint(st.nextToken());
					if(temp==1)map[i][j]=0b1111;
					else if(temp==2)map[i][j]=0b1100;
					else if(temp==3)map[i][j]=0b0011;
					else if(temp==4)map[i][j]=0b1001;
					else if(temp==5)map[i][j]=0b0101;
					else if(temp==6)map[i][j]=0b0110;
					else if(temp==7)map[i][j]=0b1010;
				}
			}
			
			Queue<int[]> qu = new LinkedList<int[]>();
			qu.add(new int[] {x,y});
			int cnt=0;
			int time=0;
			while(time++<t && !qu.isEmpty()) {
				int len = qu.size();
				
				for (int i = 0; i < len; i++) {
					int[] cur=qu.poll();
					int temp = map[cur[0]][cur[1]];
					if(temp==0)continue;
					
					if((temp&1<<3)!=0 && (map[cur[0]-1][cur[1]]&1<<2)!=0)
						qu.offer(new int[] {cur[0]-1,cur[1]});
					if((temp&1<<2)!=0 && (map[cur[0]+1][cur[1]]&1<<3)!=0)
						qu.offer(new int[] {cur[0]+1,cur[1]});
					if((temp&1<<1)!=0 && (map[cur[0]][cur[1]-1]&1<<0)!=0)
						qu.offer(new int[] {cur[0],cur[1]-1});
					if((temp&1<<0)!=0 && (map[cur[0]][cur[1]+1]&1<<1)!=0)
						qu.offer(new int[] {cur[0],cur[1]+1});
					
					cnt++;
					map[cur[0]][cur[1]]=0;
				}
			}
			sb.append("#").append(testcase).append(" ").append(cnt).append("\n");
		}//end of tc
		System.out.println(sb);
	}

	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면