[JAVA] SWEA 1953 탈주범 검거

문제

2차원 배열 위에서 주어진 파이프의 배치를 보고 주어진 시간 내에 탈주범이 방문할 수 있는 파이프의 위치의 개수를 찾는 문제이다.

입력

첫 줄에 총 테스트 케이스의 개수 T가 주어진다. 두 번째 줄부터 T개의 테스트 케이스가 차례대로 주어진다. 각 테스트 케이스의 첫 줄에는 지하 터널 지도의 세로 크기 N, 가로 크기 M, 맨홀 뚜껑이 위치한장소의 세로 위치 R, 가로 위치 C, 그리고 탈출 후 소요된 시간 L 이 주어진다.
그 다음 N 줄에는 지하 터널 지도 정보가 주어지는데, 각 줄마다 M 개의 숫자가 주어진다. 숫자 1 ~ 7은 해당 위치의 터널 구조물 타입을 의미하며 숫자 0 은 터널이 없는 장소를 의미한다.

출력

테스트 케이스의 개수만큼 T줄에 T개의 테스트 케이스 각각에 대한 답을 출력한다. 각 줄은 “#x”로 시작하고 공백을 하나 둔 다음 정답을 기록한다. (x는 1부터 시작하는 테스트 케이스의 번호이다)
출력해야 할 정답은 탈주범이 위치할 수 있는 장소의 개수이다.

풀이: bfs, 인접행렬

1. 2차원 행렬에 Index값을 부여해서 1차원으로 치환한다. ( index = {세로 위치} X 행너비 + 가로위치 )
2. 모든 위치에 대해 인접 리스트를 생성한다.
3. 파이프의 배치를 보고 인접 리스트에 이동 가능한 위치의 인덱스를 추가한다.
4. bfs로 방문 가능한 위치를 찾는다.

코드

package swea;

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

public class p1953탈주범검거 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int testcase = Integer.parseInt(br.readLine());
		for(int t=1; t<=testcase; t++) {
			st = new StringTokenizer(br.readLine());
			int height = Integer.parseInt(st.nextToken());
			int width = Integer.parseInt(st.nextToken());
			int posI = Integer.parseInt(st.nextToken());
			int posJ = Integer.parseInt(st.nextToken());
			int time = Integer.parseInt(st.nextToken());
			int grid[][] = new int[height][width];
			for(int i=0; i<height; i++) {
				st= new StringTokenizer(br.readLine());
				for(int j=0; j<width; j++) {
					grid[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			int num = height*width;
			ArrayList<Integer>[] adj = new ArrayList[num];
			for(int i=0; i<num; i++) {
				adj[i] = new ArrayList<Integer>();
			}
			for(int i=0; i<height; i++) {
				for(int j=0; j<width-1; j++) {
					if((grid[i][j]==1||grid[i][j]==3||grid[i][j]==4||grid[i][j]==5)&&(grid[i][j+1]==1||grid[i][j+1]==3||grid[i][j+1]==6||grid[i][j+1]==7)) {
						adj[i*width+j].add(i*width+j+1);
						adj[i*width+j+1].add(i*width+j);
					}
				}
			}
			for(int i=0; i<height-1; i++) {
				for(int j=0; j<width; j++) {
					if((grid[i][j]==1||grid[i][j]==2||grid[i][j]==5||grid[i][j]==6)&&(grid[i+1][j]==1||grid[i+1][j]==2||grid[i+1][j]==4||grid[i+1][j]==7)) {
						adj[i*width+j].add((i+1)*width+j);
						adj[(i+1)*width+j].add(i*width+j);
					}
				}
			}
			
			int ans  =0;
			boolean visited[] = new boolean[num];
			Queue<int[]> queue = new LinkedList<int[]>();
			queue.offer(new int[] {width*posI+posJ, 0});
			ans ++;
			visited[width*posI+posJ] = true;
			
			while(!queue.isEmpty()) {
				int[] cur = queue.poll();
				for(int next: adj[cur[0]]) {
					if(!visited[next]&&cur[1]<time-1) {
						visited[next] = true;
						ans ++;
						queue.offer(new int[] {next, cur[1]+1});
					}
				}
			}
			System.out.println("#"+t+" "+ans);
		}
	}
}