SWEA 1953 - 탈주범 검거

Java

1953 번 - 탈주범 검거

문제

지하 터널 지도와 맨홀 뚜껑의 위치, 경과된 시간이 주어질 때 탈주범이 위치할 수 있는 장소의 개수를 계산하는 프로그램을 작성하라.

접근 방법

우선 파이프의 모양에 따른 방향들을 설정하였다.
상, 하, 좌, 우를 나타내는 1차원 배열 2개를 설정하고(Y,X)
각 파이프 타입에 따른 방향을 인덱스로 주어 방향들을 설정하였다.

BFS 사용하여 파이프를 탐색한다.
최대 L시간 만큼 반복하여 파이프가 갈 수 있는 길을 탐색한다.

현재 위치의 파이프 모양에 따라 4 방향 중 골라 이동하는데,
다음 파이프의 모양이 현재 가려는 방향의 반대 방향이어서, 이어지는지 확인하였다.

이는, 현재 이동하려는 위치의 파이프 타입에 있는 방향 인덱스 중, 현재 꽂으려는 방향과 반대로인 방향이 있으면 꽂을 수 있다.

BFS가 종료한 후, 맵에 방문한 파이프의 개수를 센다.

코드

import java.io.*;
import java.util.*;
// 탈주범 검거
class Solution {
	static int result = 0, n,m, r,c ,L;
	
	// 상 하 좌 우
	static int[] dy = {-1,1,0,0};
	static int[] dx = {0,0,-1,1};
	// 파이프의 모양에 따른 방향들
	static int[][] dir = { {}, {0,1,2,3}, {0,1}, {2,3}, {0,3}, {1,3}, {1,2}, {0,2}};
	
	// 맵
	static int[][] map;
	static boolean[][] vis;
	
	public static void main(String []args) throws Exception {  
		System.setIn(new FileInputStream("res/input.txt"));	//제출 할 때 주석해야함
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	int tc = stoi(br.readLine());
    	
    	for(int tidx = 1; tidx <= tc; tidx++) {
    		result = 0;
    		stk = new StringTokenizer(br.readLine());
    		
    		n = stoi(stk.nextToken());
    		m = stoi(stk.nextToken());
    		r = stoi(stk.nextToken());
    		c = stoi(stk.nextToken());
    		L = stoi(stk.nextToken());
    		
    		map = new int[n][m];
    		vis = new boolean[n][m];
    		
    		for(int i = 0; i < n; i++) {
    			stk = new StringTokenizer(br.readLine());
    			for(int j = 0; j < m; j++) {
    				map[i][j] = stoi(stk.nextToken());
    			}
    		}
    		
    		BFS(r,c,map[r][c]);
    		// 방문했던 모든 파이프의 개수를 센다
    		for(int i = 0; i < n; i++) {
    			for(int j = 0; j < m; j++) {
    				if(vis[i][j])
    					result++;
    			}
    		}
    		
    		System.out.println("#" + tidx + " " + result);
    	}	
	}
	
	static void BFS(int y, int x, int idx) {
		Queue<int[]> queue = new LinkedList<int[]>();
		queue.add(new int[] {y,x, idx});
		
		int loopCnt = 0;
		int[] temp;
		int ny,nx, nextGo, curDir;
		if(L > 0)		// 1초 일때는 현재 위치만 이동가능 하다
			vis[y][x] = true;
		// 주어진 시간 만큼 이동한다.
		while(L-- > 1) {
			loopCnt = queue.size();
			
			for(int k = 0; k < loopCnt; k++) {
				temp = queue.poll();
				y = temp[0];
				x = temp[1];
				nextGo = temp[2];
				
				for(int i = 0; i < dir[nextGo].length; i++) {
					curDir = dir[nextGo][i];
					ny = y + dy[curDir];
					nx = x + dx[curDir];
					// 지도 안에 있고, 방문하지 않았으며, 파이프가 있고, 파이프끼리 연결 될 수 있으면
					if(isIn(ny,nx) && !vis[ny][nx] && map[ny][nx] != 0 && isConn(curDir, ny, nx)) {
						vis[ny][nx] = true;
						queue.add(new int[] {ny, nx, map[ny][nx] });
					}
				}
			}
		}
	}
	
	// 연결 될 수 있는가
	static boolean isConn(int fromD, int y, int x) {
		int scape = map[y][x];	// 꽂으려는 파이프의 현재 모양

		int wantD = 0;
		if(fromD == 0)		// 올라오는 방향
			wantD = 1;		// 꽂히는 방향
		else if(fromD == 1)
			wantD = 0;
		else if(fromD == 2)
			wantD = 3;
		else if(fromD == 3)
			wantD = 2;
		// 꽂히는 방향이 현재 지도에 있는 파이프에 있는지 확인한다. 
		for(int i = 0; i < dir[scape].length; i++) {
			if(wantD == dir[scape][i])
				return true;
		}
		return false;
	}
	
	// 주어진 범위 안에 있는가
    public static boolean isIn(int y, int x){
        if(y < 0 || y >= n || x < 0 || x >= m)
            return false;
        return true;
    }
	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

L이 1일때 처음 위치도 기록되지 않아, 이를 고려해야겠다는 생각만 하고 실제로 적용하지 않아 처음에는 틀렸다.
이런 사소한 것이 합격 불합격을 나타내니, 매번 생각 날 때마다 주석으로 달자.
나중에 분명히 잊는다.

개선할 점

없