[백준] 3055. 탈출 (Java)

BFS지만 동시성을 생각해야 하는 문제

 

3055번: 탈출

 

풀이

물과 고슴도치 각각 방문체크를 할 큐를 두고 물 → 고슴도치순으로 BFS탐색을 했다.

Logic

1. 데이터를 입력 받을때 고슴도치의 시작 위치를 hedgehog큐에 넣고 해당 map의 위치는 S에서 .으로 마킹한다. 물의 위치를 입력받을 경우 water 큐에 넣고 visited = true로 놓는다.
2. BFS 탐색을 시작한다. while문은 더이상 고슴도치 무빙이 불가능할 때 까지 반복된다.
   1. 물부터 영역을 넓힌다. 큐 크기가 유동적이기 때문에 int형 변수로 미리 크기를 받아놓는다. 범위 내부에 있고, 비버굴 위치가 아니면 map을 물로 마킹하고 visited = true로 변경한다.
   2. 고슴도치 이동도 마찬가지로 큐 사이즈를 int형 변수에 받아놓고 시작한다. 비버굴이면 바로 나갈 수 있도록 하고, 그렇지 않다면 범위체크를 통해 이동 여부를 판단한다.

범위체크 (isIn(int x, int y)) method에서 하는 일

• map 크기 벗어나는지
• (x, y)가 이미 방문된 좌표인지
• (x, y)가 물인지
• (x, y)가 돌인지

 

 

코드

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

public class Main {
	static int R, C, startX, startY;
	static int[] pos_x = { 1, 0, -1, 0 };
	static int[] pos_y = { 0, 1, 0, -1 };
	static boolean[][] visited;
	static char[][] map;
	static Queue<Coord> water = new LinkedList<>();
	static Queue<Coord> hedgehog = new LinkedList<>();
	
	public static void main(String[] args) throws IOException {
		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 + 2][C + 2];
		visited = new boolean[R + 2][C + 2];
		
		for (int i = 0; i < R; i++) {
			map[i] = br.readLine().toCharArray();
			for (int j = 0; j < C; j++) {
				if (map[i][j] == 'S') {
					hedgehog.offer(new Coord(i, j, 0));
					visited[i][j] = true;
					map[i][j] = '.';
				}
				else if (map[i][j] == '*') {
					water.offer(new Coord(i, j));
					visited[i][j] = true;
				}
			}
		}
		solve();
		br.close();
	}
	
	public static void solve() {
		while(!hedgehog.isEmpty()) {
			int size = water.size();
			for (int i = 0; i < size; i++) {
				int wx = water.peek().x;
				int wy = water.peek().y;
				water.poll();
				for (int d = 0; d < 4; d++) {	
					int nx = wx + pos_x[d];
					int ny = wy + pos_y[d];
					
					if (!isIn(nx, ny) || map[nx][ny] == 'D') continue;
					visited[nx][ny] = true;
					map[nx][ny] = '*';
					water.offer(new Coord(nx, ny));
				}
			}
			size = hedgehog.size();
			for (int i = 0; i < size; i++) {
				int x = hedgehog.peek().x;
				int y = hedgehog.peek().y;
				int t = hedgehog.peek().time;
				hedgehog.poll();
				
				if (map[x][y] == 'D') {
					System.out.println(t);
					return;
				}
				
				for (int d = 0; d < 4; d++) {	
					int nx = x + pos_x[d];
					int ny = y + pos_y[d];
					
					if (!isIn(nx, ny)) continue;
					visited[nx][ny] = true;
					hedgehog.offer(new Coord(nx, ny, t + 1));
				}
			}
		}
		System.out.println("KAKTUS");
	}
	
	public static boolean isIn(int x, int y) {
		if (x < 0 || x >= R || y < 0 || y >= C || visited[x][y] || map[x][y] == '*' || map[x][y] == 'X') return false;
		
		return true;
	}
	
	static class Coord {
		int x;
		int y;
		int time;
		
		public Coord(int x, int y) {
			this.x = x;
			this.y = y;
		}
		
		public Coord(int x, int y, int time) {
			this(x, y);
			this.time = time;
		}
		
	}

}

실행 결과