[Java] 백준9376 - 탈옥

https://www.acmicpc.net/problem/9376

9376번: 탈옥

 

이번엔 맞겠지..?  X 10 번 하면서 풀었던 문제... 생각하기 어려웠다!

ㅋㅋ 풀고 보니까 난이도가 플레티넘4더라ㅜㅜ

감옥에서 죄수 2명을 꺼내기 위해 열어야 하는 문의 최소 개수를 구해야한다.

 

느낌적인 느낌으로 BFS를 사용해야 하는 것을 알 수 있다.

 

문제에서 주어진 3가지

• # : 문
• * : 벽
• $ : 죄수

 

대충 방법을 설명하면 이렇다

• 외부인(상근이)가 감옥 밖과 안에서 각 위치마다 열어야 하는 최소 문 개수를 구함
• 죄수 2명이 감옥 안과 밖에서 각 위치마다 열어야 하는 최소 문 개수를 구함

(총 BFS 3번)

• 세 번의 BFS로 나온 결과물(각 위치마다 열어야 하는 문의 최소개수)를 더해서 전체 최소값 구하기

→ 전부 탐색해야 하나? YES! 어차피 문 다 찾아야 하니까~! (어디가 최소일지 모름)

 

주의할 점 / TIP

• 문은 한 번 열면 계속 열려있으므로 마지막에 더할때 문일 경우 -2를 해줘야 함 
• 3개의 BFS 실행 모두 방문하지 않은 위치는 취급 X ★ (나는 int형 2차원 배열을 놓고 방문 누적 횟수를 기록했다)
• BFS 실행시 Deque / PriorityQueue 사용 

      (→ 문의 최소 개수를 구해야 하기 때문에 문을 열면 일단 문 개수가 +1이 됨.)

난 일단 무조건 탐색하고 방문했던 자리면 값 비교해서 버리거나 갱신하거나 했는데, 그러면 시간이 너무 많이 걸리고! 문을 거치지 않은 경로를 우선순위로 탐색하면 이미 방문한 정점은 다음 방문보다 연 문의 개수가 무조건 적거나 같으니까 방문한 정점은 지나쳐도 됨

 

[코드]

package BOJ_1000;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class boj9376 {
	static class Node {
		int x, y;
		public Node(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	private static int N, H, M;
	private static char[][] map;
	private static int[][] totVisited;
	private ArrayList<int[][]> maps = new ArrayList<>();
	private static int[] dx = {1,-1,0,0};
	private static int[] dy = {0,0,1,-1};
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		N = Integer.parseInt(br.readLine());
		
		for(int t=0; t<N; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			H = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			totVisited = new int[H+2][M+2];
			
			map = new char[H+2][M+2];
			for(char[] c : map) {
				Arrays.fill(c, '.');
			}
			
			ArrayList<Node> prisoner = new ArrayList<>();
			
			for(int i=1; i<=H; i++) {
				String str = br.readLine();
				for(int j=1; j<=M; j++) {
					map[i][j] = str.charAt(j-1);
					if(map[i][j]=='$')
						prisoner.add(new Node(i,j));
				}
			}
			int[][] m1 = bfs(new Node(0,0));
			int[][] m2 = bfs(prisoner.get(0));
			int[][] m3 = bfs(prisoner.get(1));
			
			
			int min = Integer.MAX_VALUE;
			for(int i=0; i<=H+1; i++) {
				for(int j=0; j<=M+1; j++) {
					if(map[i][j] =='*')
						continue;
					
					if(totVisited[i][j]!=3)
						continue;
					
					int sum = m1[i][j]+m2[i][j]+m3[i][j];
					
					if(map[i][j]=='#')
						sum -= 2;
					
					min = Math.min(min, sum);
				}
			}
			bw.write(min+"\n");
		}
		bw.flush();
		bw.close();
	}
	
	public static int[][] bfs(Node start) {
		int[][] doorCnt = new int[H+2][M+2];
		boolean[][] visited = new boolean[H+2][M+2];

		visited[start.x][start.y] = true;
		
		Deque<Node> q = new ArrayDeque<>();
		q.add(start);		
		
		while(!q.isEmpty()) {
			Node now = q.poll();
			totVisited[now.x][now.y] += 1;
			int cnt = doorCnt[now.x][now.y];
			
			for(int i=0; i<4; i++) {
				int nx = now.x + dx[i];
				int ny = now.y + dy[i];
				
				if(!isInArea(nx, ny))
					continue;
				
				char ch = map[nx][ny];
				
				// 벽일때
				if(ch=='*')
					continue;
				
				// 이미 방문한 정점에 대하여
				if(visited[nx][ny])
					continue;
								
				if(ch=='#') {
					visited[nx][ny] = true;
					doorCnt[nx][ny] = cnt+1;
					q.addLast(new Node(nx, ny));	
					
				}else {
					visited[nx][ny] = true;
					doorCnt[nx][ny] = cnt;
					q.addFirst(new Node(nx, ny));	
				}					
			}
		}
		
		doorCnt[start.x][start.y] = 0;
		return doorCnt;
	}
	
	public static boolean isOutside(int x, int y) {
		return x == 0 || y == 0 || x == H+1 || y == M+1;
	}
	
	public static boolean isInArea(int x , int y) {
		return x>=0 && x<=H+1 && y>=0 && y<=M+1;
	}
}