탈출 [백준 3055][JAVA][골드 5][BFS]

 

[광고 누르면 오늘의 행운 상승!!]

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

3055번: 탈출

백준 4179 '불'과 비슷한 문제

1. 참고사항

- 큐를 두개 사용해서 불과 고슴도치를 따로 관리해 주어야 한다.
- 각 큐의 사이즈만큼  실행하면 1타임 지난것과 같다.

2. 구현

- 'S'라면 좌표를 Q에 집어넣고 map을 '.'로 만든다.
- '*'라면 좌표를 WaterQ에 집어넣는다.
- 두개의 큐를 이용하여 WaterQ 먼저 WaterQ의 사이즈 만큼 번져나간다 (물이 퍼져나간다) 
- 그 다음 Q의 사이즈만큼 물과 바위가 아닌 지역으로 퍼져나간다. 
- 'D'(비버의 집)을 발견하면 TRUE를 리턴, 큐의 사이즈가 0이 되면(D에 도달하지 못하고 끝났다) FALSE 를 리턴

package Study8;

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


public class 탈출 {
	static class Dochi{
		int row, col, cnt;
		public Dochi(int row, int col, int cnt) {
			this.row = row;
			this.cnt = cnt;
			this.col = col;
		}
	}
	
	static int dx[] = {-1,0,1,0};
	static int dy[] = {0,1,0,-1};
	static char[][] map;
	static boolean[][] visit;
	static int R,C,N,ans,water;
	static Queue<int[]> waterQ = new LinkedList<>();
	static Queue<Dochi> q = new LinkedList<>();
	
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		
		map = new char[R][C];
		visit = new boolean[R][C];
		
		for (int i = 0; i < R; i++) {
			char ch[] = br.readLine().toCharArray();
			for (int j = 0; j < C; j++) {
				map[i][j] = ch[j];
				if(map[i][j] == 'S') {
					q.add(new Dochi(i,j,0));
					visit[i][j] = true;
					map[i][j] = '.';
				}
				if(map[i][j] == '*') {
					waterQ.add(new int[] {i,j});
				}
			}
		}
		
		if(bfs()) System.out.println(ans);
		else	  System.out.println("KAKTUS");
		
	}
	private static boolean bfs() {
		
		while(true) {
			int size = waterQ.size();
			
			//물
			for (int i = 0; i < size; i++) {
				int[] pos = waterQ.poll();
				
				for (int dir = 0; dir < 4; dir++) {
					int nx = pos[0] + dx[dir];
					int ny = pos[1] + dy[dir];
					
					if(nx< 0 || nx >= R || ny < 0 || ny >=C) continue;
					
					if(map[nx][ny] == '.') {
						map[nx][ny] = '*';
						waterQ.add(new int[] {nx,ny});
					}
				}
			}
			size = q.size();
			if(size == 0) break;
			//도치
			for (int i = 0; i < size; i++) {
				Dochi dochi = q.poll();
				for (int dir = 0; dir < 4; dir++) {
					int nx = dochi.row + dx[dir];
					int ny = dochi.col + dy[dir];
					
					if(nx< 0 || nx >= R || ny < 0 || ny >=C) continue;
					if(map[nx][ny] == 'D') {
						ans = dochi.cnt+1;
						return true;
					}
					
					if(visit[nx][ny]) continue;
					if(map[nx][ny] == '.') {
						visit[nx][ny] = true;
						q.add(new Dochi(nx,ny,dochi.cnt+1));
					}
				}
			}
		}
		return false;
	}
}