백준 3055 - 탈출

Java

3055 번 - 탈출

문제

접근 방법

물과 고슴도치는 동시에 이동하며, 상하좌우 한칸 씩 이동한다.

이 조건에 의해서 중첩 while문 BFS를 사용하였다.

S와 *의 정보를 담을 2개의 Queue를 사용한다.
이후 BFS를 통해 S와 *를 퍼뜨린다.
S가 D에 도다르면, 도착할 때 까지 걸린 시간을 리턴하여 결과로 출력한다.

주의할 점은, *가 S를 덮어 씌웠을 경우기 있으므로, S가 움직일 때 현재 자기 위치에 *가 있는지 확인한다.

코드

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

public class Main {
	static int n, m, result;
	static Queue<int[]> sQueue;
	static Queue<int[]> wQueue;
	static char[][] map;
	public static void main(String[] args) throws IOException {
		System.setIn(new FileInputStream("res/mainInput.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	n = stoi(stk.nextToken());
    	m = stoi(stk.nextToken());
    	
    	map = new char[n][m];
    	boolean[][] vis = new boolean[n][m];
    	
    	sQueue = new LinkedList<int[]>();
    	wQueue = new LinkedList<int[]>();
    	
    	String input;
    	for(int i = 0; i < n; i++) {
    		input = br.readLine();
    		for(int j = 0; j < m; j++) {
    			map[i][j] = input.charAt(j);
    			if(map[i][j] == 'S')
    				sQueue.add(new int[] {i,j});
    			if(map[i][j] == '*')
    				wQueue.add(new int[] {i,j});
    		}
    	}
    	
    	result = BFS();
    	if(result != -1)
    		System.out.println(result);
    	else
    		System.out.println("KAKTUS");
    	
    	br.close();
	}
	
	static int BFS() {
		int[] dy = {-1,1,0,0};
    	int[] dx = {0,0,-1,1};
    	
    	int size, x, y, nx, ny, count = 0;
    	int[] q;
    	while(!sQueue.isEmpty() || !wQueue.isEmpty()) {
    		size = sQueue.size();

    		// S 이동
    		while(size-- != 0) {
    			q = sQueue.poll();
    			y = q[0];
    			x = q[1];
    			
    			// 만약 현재 S의 위치가 물에 잠겨버렸으면
    			if(map[y][x] == '*')
    				continue;
    			
				// 상하좌우 이동
    			for(int i = 0; i < 4; i++) {
    				ny = y + dy[i];
    				nx = x + dx[i];
    				
    				if(isIn(ny,nx) && map[ny][nx] == 'D')
        				return count + 1;
    				
    				if(isIn(ny,nx) && map[ny][nx] == '.') {
    					map[ny][nx] = 'S';
    					sQueue.add(new int[] {ny,nx});
    				}
    			}
    		}
    		
    		size = wQueue.size();
    		// * 이동
    		while(size-- != 0) {
    			q = wQueue.poll();
    			y = q[0];
    			x = q[1];
    			
    			for(int i = 0; i < 4; i++) {
    				ny = y + dy[i];
    				nx = x + dx[i];
    				
    				if(isIn(ny,nx) && (map[ny][nx] == '.' || map[ny][nx] == 'S')) {
    					map[ny][nx] = '*';
    					wQueue.add(new int[] {ny,nx});
    				}
    			}
    		}
    		count++;
    	}
    	return -1;
	}
	
	static boolean isIn(int y, int x) {
		if(0 <= y && y < n && 0 <= x && x < m)
			return true;
		return false;
	}
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

개선할 점