9376 탈옥

오늘 포스팅할 문제는9376번 탈옥입니다.

 

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

9376번: 탈옥

 

저번 포스팅한 백조를 풀고 자신감이 짱짱해져서 도전했는데 후두려 맞았습니다. (지난 번 백조: https://hardworking-sloth.tistory.com/3)

 

문제가 굉장히 어려워서 장고 끝에 결국 검색을 통해 힌트를 얻어서 풀었습니다.

 

 

-나의 풀이- 

 

(제가 해결하지 못했지만 그래도 저의 생각의 과정을 남기면 좋을 것 같아서 메모합니다.)

구현에 있어서 어려웠던 부분들을 표시해보았습니다.

 

이 문제는 하나의 테스트 케이스를 O(N^2)으로 해결해함.

 

매 시간이 진행될 때, 상황이 바뀌는 경우 최소값을 구하기 위해서는 모든 경우를 끝까지 다 확인해야한다고 생각.

 

모든 경우를 끝까지 확인하면서 시간복잡도가 적합한 방법을 생각해봄. 

 

두 죄수가 문의 열고 닫힘을 공유함. 

1. 하나의 죄수의 관점에서 최소 문을 갯수를 구한다고해도, 나머지 죄수의 상황을 생각하면 결국 모든 문의 열고 닫힘의 경우를 조사하여야함. O(N^4)

2. 문을 공유한다는 것은 죄수 1이 탈출가능한 상황에서 죄수 2의 기준으로 탐색을 해야함. 즉 하나의 탐색마다 문의 열고 닫힘 상황이 달라짐. 

 

역으로 출구에서 죄수를 찾는 방법도 생각.> 하지만 이 방법 또한 모든 출구를 조사해야함. K * O(N^2) ( K는 대략 2N)

 

대충 이런 생각 끝에 도저히 방법이 생각나지 않아서 검색을 해보았습니다. ㅠ

 

 

-해답- 

 

(출처 : https://suhyeokeee.tistory.com/13)

(출처 : https://shinyou1024.tistory.com/48)

 

3가지 아이디어가 필요.

 

1. 죄수가 모든 구역을 얼마의 문을 열고 갈 수 있는가?

> 제가 집착했던 문을 열고 닫힘에서 관점을 바꿔야했습니다. 쉽게 구할 수 있는 죄수가 모든 구역을 얼마의 문을 열고 갈 수 있는가? 를 이용하는 것 

 

2. 그렇다면 두 죄수의 경우를 구하고, 두 경우를 합한다면 그 값이 두 죄수가 만났을 때 문을 연 갯수이다. 

> 문을 한번만 열면 연상태가 지속되니, 문에 해당하는 값은 -1를 한다. 

 

3. 외부 탐색자를 추가한다. 

> 탈출의 여부를 외부 탐색차를 설정하여 구한다! 두 죄수만으로는 두 죄수가 만날 경우만 구할 수 있다. 외부의 탐색자를 추가한다면, 3명이 만나는 경우가 죄수 두명이 탈출가능하는 것을 의미한다. (문에 해당하는 값은 -2를 한다.) 

 

*예외 처리

만일 벽에 둘러쌓인 공간이 존재한다면, 그 값은 최소값으로 계산되면 안된다.

ex)

1
7 7
***#***
*.....*
*.***.*
*#*.*#*
*.***.*
*.$*$.*
*******

-코드-

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;

class Location implements Comparable<Location>{
	int h;
	int w;
	int count ;
	public Location(int h, int w, int count) {
		this.h = h;
		this.w = w;
		this.count = count;
	}
	@Override
	public int compareTo(Location oj){
		return this.count -oj.count;
	}
}
public class Num9376 {
	static boolean[][] passcheck; //예외값을 처리해주기 위함
	static List<Location> prisoners = new LinkedList<>();
	static int[] dx = {1,0,-1,0} , dy = {0,1,0,-1};
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int numberOfTest = Integer.parseInt(bf.readLine());
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<numberOfTest; i++) {
			prisoners.clear();
			String[] tmp = bf.readLine().split(" ");
			int h = Integer.parseInt(tmp[0]);
			int w = Integer.parseInt(tmp[1]);
			char[][] map = new char[h+2][w+2];
			for(int k=0; k<h+2; k++) {
				Arrays.fill(map[k], '.');
			}
			for(int j=1; j<=h;j++) {
				String input = bf.readLine();
				for(int m=0; m<w;m++) {
					map[j][m+1] = input.charAt(m);
					if(map[j][m+1]=='$') {
						prisoners.add(new Location(j,m+1,0));
					}
				}
				
			}
			sb.append(solution(h,w,map)+"\n");
		}
		System.out.println(sb);
	}
	public static int solution(int h, int w, char[][] map) {
		int[][] answer = new int [h+2][w+2];
		for(int k=0; k<h+2; k++) {
			Arrays.fill(answer[k], 0);
		}
		passcheck = new boolean[h+2][w+2];
		answer[0][0]=0;
		BFS(new Location(0,0,0),h,w,map,answer);
		BFS(prisoners.get(0),h,w,map,answer);
		BFS(prisoners.get(1),h,w,map,answer);
		
		int minvalue = Integer.MAX_VALUE;
		for(int i =0;i<h+2; i++) {
			for(int j=0; j<w+2; j++) {
				if(map[i][j]!='*') {
					if(map[i][j] =='#') {
						answer[i][j] -= 2;
					}
					if(!passcheck[i][j]) {
						continue;
					}
					minvalue = Math.min(minvalue, answer[i][j]);
				}
				
			}
		}
		return minvalue;
		
	}
	public static void BFS(Location start, int h, int w,char[][] map, int[][] answer) {
		PriorityQueue<Location> pq = new PriorityQueue<>();
		boolean [][] vist = new boolean[h+2][w+2];
		pq.add(start);
		vist[start.h][start.w] = true;
		while(!pq.isEmpty()) {
			Location now = pq.poll();
			for(int i = 0; i<4; i++) {
				if(now.h+dx[i]>=0 && now.h+dx[i]<=h+1 &&
						now.w+dy[i]>=0 && now.w+dy[i]<=w+1) {
					if(map[now.h+dx[i]][now.w+dy[i]] != '*' && !vist[now.h+dx[i]][now.w+dy[i]]) {
						vist[now.h+dx[i]][now.w+dy[i]] = true;
						passcheck[now.h+dx[i]][now.w+dy[i]] = true;
						if(map[now.h+dx[i]][now.w+dy[i]] == '#') {
							answer[now.h+dx[i]][now.w+dy[i]] += now.count+1;
							pq.add(new Location(now.h+dx[i],now.w+dy[i],now.count+1));
						}else {
							answer[now.h+dx[i]][now.w+dy[i]] += now.count;
							pq.add(new Location(now.h+dx[i],now.w+dy[i],now.count));
						}
					}
				}
			}
		}
	}

}

 

- 후기 -

1. 이걸 생각해..내라고?

2. 미래의 나는 가능할지도.

3. 아닐지도..