BOJ - 3197 ) 백조의호수

---

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

3197번: 백조의 호수

---

최적화의 끝.. 문제는 쉽다. MAP에서 . 와 인접한 X는 매초 녹는다. 녹으면서 생기는 .을 통하여 

 두개의 L이 만날수있는지 물어보는 BFS문제이다.

 

하지만 그냥 있는대로 코딩해주면 1500X1500 map을 BFS로 1500번탐색해야하는 경우가 생긴다.

 

내가해준 최적화는 3가지이다.

 

1 ) VISIT 배열의 재사용 -> VISIT배열을 정수로 선언하여 특정 값이 아니면 탐색할 수 있도록하여 메모리를 

아낀다.

 

2 ) BFS로 녹을수있는 배열 COUNT를 선언, 매 번 BFS시 사라지는 X를 미리 표시해두어서 탐색에 활용한다.

 

3 ) 힙영역접근 최소화, 거의모든 변수를 지역변수나 static영역에서 활용하였다.

 

사실 visit배열을 int로 활용하는것은 앞으로도 사용해야 할 부분..

 

문제 해결 알고리즘은 BFS를 통한 Binary Search이다. 시간 T에서 백조끼리 만날수 있다면,

T+1에서도 만날수 있을것이다 ( 빙산이 생기지는 않기 때문에 )

그렇다면 count배열에서 가장큰값과 0의 중간값에서 만난다면,

mid ~ max 값은 탐색하지 않아도, 만날것이다.

 

반대로, 만나지 않는다면 그 이하는 볼 필요가 없게된다. BFS와 이분탐색을 동시에 활용해야하는

새로운 유형의 문제였다. 문제좋은듯

 

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;

public class 백조의호수 {
	
	public static char 	  map[][];
	public static int 	visit[][];
	public static int 	count[][];
	public static int day=1,sty,stx,endy,endx,y,x;
	public static int ny,nx,r,c,t;
	public static int dir[][] = {{1,0},{-1,0},{0,1},{0,-1}};
	public static ArrayDeque<int[]> dq = new ArrayDeque<>();
	
	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader( System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		y = Integer.parseInt(st.nextToken());
		x = Integer.parseInt(st.nextToken());
		
		map = new char[y][x];
		visit = new int[y][x];
		count = new int[y][x];
		boolean first = true;
		for(int i = 0 ; i < y ; i++) {
			char []temp = br.readLine().toCharArray();
			for(int j = 0 ; j < x ; j++) {
				map[i][j] = temp[j];
				if(temp[j] == 'L' && first) {
					sty= i ; stx=j; first = false;
					map[i][j] ='.';
				}
				else if(temp[j] == 'L' && !first) {
					endy= i ; endx=j; 
					map[i][j] ='.';
				}
			}
		}
		
		
		
		
		for(int i = 0 ; i < y ; i++) {
			for(int j = 0 ; j < x ; j++) {
				if(map[i][j]=='.') {
					for(int k = 0 ; k < 4 ; k ++) {
						ny = i + dir[k][0];
						nx = j + dir[k][1];
						if(ny >=0 && nx >=0 && nx < x && ny < y && map[ny][nx] =='X' && count[ny][nx]==0) {
							count[ny][nx] = day;
							dq.add(new int[] {ny,nx,day});
						}
					}
				}
			}
		}
		int max = 0;
		while(!dq.isEmpty()) {
			
			int now[] = dq.poll();
			r = now[0];
			c = now[1];
			t = now[2];
			max = max > t ? max: t;
			for(int i = 0 ; i < 4 ; i ++) {
				ny = r + dir[i][0];
				nx = c + dir[i][1];
				if(ny >=0 && nx >=0  && ny < y && nx < x ) {
					if(map[ny][nx] =='X' && count[ny][nx] ==0) {
						count[ny][nx] = t + 1;
						dq.add(new int[] {ny,nx,t+1});
					}
				}
			}
		}
		int answer = 2000;
		int start = 0, end = max;
		while(start <= end) {
			int mid = (start + end)>>1;
			
			if(!find(mid)) {
				start = mid +1;
			} else {
				if(answer > mid ) answer = mid;
				end = mid-1;
			}
		
		}
		System.out.println(answer);
	}

	private static boolean find(int mid) {
		
		dq.add(new int[] {sty, stx});
		visit[sty][stx] = mid;
		// count[][]가 mid보다  같거나 작고, visit[][]가  mid가 아닌 값들은 이동할 수 있다.
		
		while(!dq.isEmpty()) {
			int now[] = dq.poll();
			
			for(int i = 0 ; i < 4 ; i++) {
				ny = now[0] + dir[i][0];
				nx = now[1] + dir[i][1];
				
				if(ny >= 0 && nx >=0 && ny < y && nx < x) {
					if(count[ny][nx] <= mid && visit[ny][nx] != mid) {
						visit[ny][nx] = mid; 
						if(ny == endy && nx == endx) {
							dq.clear();
							return true;
						}
						dq.add(new int[] {ny,nx});
					}
				}
			}
		}
		return false;
	}
}

---

덱을 초기화 안해주어서 계속 뻘짓..