[SWEA-1953] 탈주범 검거

이 문제는 SWEA에 있는 모의 SW 역량테스트 탈주범 검거 문제이다. A형 정도의 구현력을 요구하는 문제라고 한다. 

보다시피 문제가 좀 길다ㅠ 그래서 지난번 처럼 링크로 가지고 올 까 했는데, 여기서는 문제를 같이 보는게 편할 것 같아 캡쳐해왔다. 

 

이 문제는 조건이 많아서 까다로운 문제이다. 각 파이프마다 갈 수 있는 곳이 달라서 그 부분 처리를 해주는데 조금 애를 먹었다. 그래도 조금만 생각해보면, 전역변수를 이용해 if문을 왕창 쓰는 것을 막을 수 있다. 

 

static int[][] dr = {{0,0,0,0},{-1,1,0,0},{-1,1,0,0},{0,0,0,0},{-1,0,0,0},{0,1,0,0},{0,1,0,0},{-1,0,0,0}}; //1번 - 7번
static int[][] dc = {{0,0,0,0},{0,0,-1,1},{0,0,0,0},{0,0,-1,1},{0,0,0,1},{0,0,0,1},{0,0,-1,0},{0,0,-1,0}};
static int[][] dir = {{1,2,5,6}, {1,2,4,7}, {1,3,4,5}, {1,3,6,7}}; //상하좌우

되게 뭐가 많아보이지만, 생각보다 간단하다. 

숫자를 dr과 dc는 각각 세로와 가로로, 파이프 번호에 따라 갈 수 있는 곳들을 미리 써 놓은 것이다.

dir은 내가 현재 위로 갈 수 있는 상황이면, 위의 파이프가 1,2,5,6 중에 하나여야 갈 수 있다는 것을 미리 써 놓은 것이다.

 

이렇게 해두면 보통 풀던 bfs랑 크게 다르지 않다.

 

1) 큐에 내가 있는 위치와 그 점에 도달하기 까지 걸린 시간을 넣어주고 while문 돌리기

2) 파이프의 갯수인 7번까지 돌면서, 내 파이프를 만나면

3) 상하좌우 중 어디 갈 수 있는지 살펴보기.

4) 상하좌우 중 갈 수 있는 길이 있고, 그 방향의 파이프가 내가 서 있는 파이프와 연결되어 있다면

5) 방문 처리 하고 큐에 넣어주기

 

이 과정을 반복하다가, 내가 원하는 시간이 나오면 그 때까지 방문한 파이프의 수를 출력해주면 된다.

 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class 탈주범검거 {
	static int N,M,R,C,L;
	static int[][] map;
	static boolean[][] visited;
	static int ans;
	static int[][] dr = {{0,0,0,0},{-1,1,0,0},{-1,1,0,0},{0,0,0,0},{-1,0,0,0},{0,1,0,0},{0,1,0,0},{-1,0,0,0}}; //1번 - 7번
	static int[][] dc = {{0,0,0,0},{0,0,-1,1},{0,0,0,0},{0,0,-1,1},{0,0,0,1},{0,0,0,1},{0,0,-1,0},{0,0,-1,0}};
	static int[][] dir = {{1,2,5,6}, {1,2,4,7}, {1,3,4,5}, {1,3,6,7}}; //상하좌우
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for(int tc=1; tc<=T; tc++) {
			N = sc.nextInt(); //세로
			M = sc.nextInt(); //가로
			R = sc.nextInt(); //맨홀 위치 세로
			C = sc.nextInt(); //맨홀 위치 가로
			L = sc.nextInt(); //지난 시간
			
			map = new int[N][M];
			visited = new boolean[N][M];
			ans = 1; //맨 처음 시작위치
			
			for(int i=0; i<N; i++) { //입력받기
				for(int j=0; j<M; j++) {
					map[i][j] = sc.nextInt();
				}
			}
			
			bfs(R,C,L);
			
			System.out.println("#"+tc+" "+ans);
			
		}
		
	}
	

	static void bfs(int y, int x, int l) {
		Queue<Point> q = new LinkedList<>();
		visited[y][x] = true;
		q.add(new Point(y,x,1));
		
		while(!q.isEmpty()) {
			Point p = q.poll();
			if(p.time == L) {
				return;
			}
			
			for(int i=1; i<8; i++) { 
				if(map[p.r][p.c] == i) { //내 파이프 모양 찾기
					for(int j=0; j<4; j++) { //상하좌우
						int nr = p.r + dr[i][j];
						int nc = p.c + dc[i][j]; 
						
						//지금 위치랑 다음 위치랑 같은 곳이면 못가는 곳이니까 pass
						if(p.r == nr && p.c == nc) 
							continue;
						
						//범위 넘어가면 pass
						if(nr<0 || nc<0 || nr>=N || nc>=M) 
							continue;
						
						if(map[nr][nc] == 0) //0이면 못가는 곳.
							continue;
						
						for(int k=0; k<4; k++) { //각 방향마다 갈 수 있는 곳 4군데씩 있음
							if(dir[j][k] == map[nr][nc]){ //가려고 했을 때 갈 수 있는 곳이면 가기
								if(!visited[nr][nc]){ 
									visited[nr][nc] = true;
									ans++;
									q.add(new Point(nr,nc, p.time+1));
								}
							}
						}
					}
				}
			}
		}
	}
	
	static class Point{
		int r,c,time; 
		Point(int r, int c, int time){
			this.r = r;
			this.c = c;
			this.time = time;
		}
	}

}