[SW Expert 1953] 탈주범 검거

[문제 바로가기]👇

SW Expert Academy

 

 

 

 

풀이

• 탈주범이 맨홀 뚜껑부터 시작해 시간당 1의 거리만큼 계속 이동
• 탈주범이 있을 수 있는 장소를 찾아야 하기 때문에 bfs로 같은 거리에 있는 위치들을 모두 탐색
• 탈주범이 탈출 후 소요된 시간(L) == bfs 깊이가 되면 탐색 종료

 

1. 입력 받기

	static int[] dr = {-1,0,1,0}; //상우하좌
	static int[] dc = {0,1,0,-1}; //상우하좌
	static int N, M, L, answer;
	static int[][] map;
	static boolean[][] v;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		System.setIn(new FileInputStream("res/input_sw1953.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		
		for(int t=1; t<=T; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			int r = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			L = Integer.parseInt(st.nextToken());
			
			map = new int[N][M];
			for(int i=0; i<N; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				for(int j=0; j<M; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			v = new boolean[N][M];
			answer = 0;
			bfs(r,c, map[r][c]);
			sb.append("#").append(t).append(" ").append(answer).append("\\n");
		}
		System.out.println(sb);
		br.close();
	}

 

2. bfs

큐에 넣을 수 있는 것들을 체크할 때 현재 파이프와 이동할 곳에 있는 파이프가 서로 연결되어 있어야만 이동할 수 있기 때문에 연결 여부를 체크해줘야 한다

static void bfs(int r, int c, int pipe) {
		ArrayDeque<int[]> q = new ArrayDeque<>();
		answer++;
		v[r][c] = true;
		q.offer(new int[] {r,c, pipe, 1}); // r,c, 파이프 번호, depth
		
		while(!q.isEmpty()) {
			int[] cur = q.poll();
			if(cur[3]==L) break;
			
			for(int d=0; d<4; d++) {
				int nr = cur[0] + dr[d];
				int nc = cur[1] + dc[d];
				
				if(0<=nr&&nr<N && 0<=nc&&nc<M && !v[nr][nc] && map[nr][nc]!=0) {
					// 현재 파이프와 이동 가능한 것만 큐에 추가
					if(isConnected(nr, nc, cur[2], d)) { 
						answer++;
						v[nr][nc] = true;
						q.offer(new int[] {nr,nc, map[nr][nc], cur[3]+1});
					}
				}
			}
		}
}

 

2-1. 파이프 연결 여부 확인

현재 이동하려는 방향의 반대 방향을 이동할 파이프가 이동할 수 있으면 연결 되어 있다고 판단

static boolean isConnected(int r, int c, int pipe, int d) {
		int cPipe = map[r][c];
		
		if(d==0) { // 현재 파이프 -이동할 파이프(상 - 하)
			if((pipe==1||pipe==2||pipe==4||pipe==7) &&
				(cPipe==1||cPipe==2||cPipe==5||cPipe==6)) return true;
		}
		else if(d==1) { // 현재 파이프 -이동할 파이프(우 - 좌)
			if((pipe==1||pipe==3||pipe==4||pipe==5) &&
					(cPipe==1||cPipe==3||cPipe==6||cPipe==7)) return true;
		}
		else if(d==2) { // 현재 파이프 -이동할 파이프(하 - 상)
			if((pipe==1||pipe==2||pipe==5||pipe==6) &&
					(cPipe==1||cPipe==2||cPipe==4||cPipe==7)) return true;
		}
		else { // 현재 파이프 -이동할 파이프(좌 - 우)
			if((pipe==1||pipe==3||pipe==6||pipe==7) &&
					(cPipe==1||cPipe==3||cPipe==4||cPipe==5)) return true;
		}
		return false;
}

 

전체 코드

package Day_0404;

import java.io.*;
import java.util.*;

public class Solution {
	static int[] dr = {-1,0,1,0}; //상우하좌
	static int[] dc = {0,1,0,-1}; //상우하좌
	static int N, M, L, answer;
	static int[][] map;
	static boolean[][] v;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		System.setIn(new FileInputStream("res/input_sw1953.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		
		for(int t=1; t<=T; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			int r = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			L = Integer.parseInt(st.nextToken());
			
			map = new int[N][M];
			for(int i=0; i<N; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				for(int j=0; j<M; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			v = new boolean[N][M];
			answer = 0;
			bfs(r,c, map[r][c]);
			sb.append("#").append(t).append(" ").append(answer).append("\\n");
		}
		System.out.println(sb);
		br.close();
	}
	
	static void bfs(int r, int c, int pipe) {
		ArrayDeque<int[]> q = new ArrayDeque<>();
		answer++;
		v[r][c] = true;
		q.offer(new int[] {r,c, pipe, 1}); // r,c, 파이프 번호, depth
		
		while(!q.isEmpty()) {
			int[] cur = q.poll();
			if(cur[3]==L) break;
			
			for(int d=0; d<4; d++) {
				int nr = cur[0] + dr[d];
				int nc = cur[1] + dc[d];
				
				if(0<=nr&&nr<N && 0<=nc&&nc<M && !v[nr][nc] && map[nr][nc]!=0) {
					// 현재 파이프와 이동 가능한 것만 큐에 추가
					if(isConnected(nr, nc, cur[2], d)) { 
						answer++;
						v[nr][nc] = true;
						q.offer(new int[] {nr,nc, map[nr][nc], cur[3]+1});
					}
				}
			}
		}
	}
	
	static boolean isConnected(int r, int c, int pipe, int d) {
		int cPipe = map[r][c];
		
		if(d==0) { // 현재 파이프 -이동할 파이프(상 - 하)
			if((pipe==1||pipe==2||pipe==4||pipe==7) &&
				(cPipe==1||cPipe==2||cPipe==5||cPipe==6)) return true;
		}
		else if(d==1) { // 현재 파이프 -이동할 파이프(우 - 좌)
			if((pipe==1||pipe==3||pipe==4||pipe==5) &&
					(cPipe==1||cPipe==3||cPipe==6||cPipe==7)) return true;
		}
		else if(d==2) { // 현재 파이프 -이동할 파이프(하 - 상)
			if((pipe==1||pipe==2||pipe==5||pipe==6) &&
					(cPipe==1||cPipe==2||cPipe==4||cPipe==7)) return true;
		}
		else { // 현재 파이프 -이동할 파이프(좌 - 우)
			if((pipe==1||pipe==3||pipe==6||pipe==7) &&
					(cPipe==1||cPipe==3||cPipe==4||cPipe==5)) return true;
		}
		return false;
	}

}