[백준/Java] 3055 탈출

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

문제 요약

지도는 R행 C열로 이루어진다.
비어있는 곳은 '.', 물이 있는 곳은 '*', 돌은 'X', 비버 굴은 'D', 고슴도치 위치는 'S'로 나타낸다.
매 분마다 고슴도치는 인접한 네 칸 중에 하나로 이동할 수 있다. 물은 인접한 네 칸 모두에 퍼진다.
돌은 물과 고슴도치 모두 지날 수 없으며, 물은 비버 굴에 차오를 수 없다.
고슴도치는 물이 있는 곳, 그리고 물이 차오를 예정인 곳으로 이동할 수 없다.
고슴도치가 비버 굴로 이동할 수 있는 최소 시간을 구하자.
R과 C는 최대 50인 자연수이다.

---

문제 접근

BFS를 사용하면 해결할 수 있는 전형적인 문제이다.
다만 고슴고치에 더해 물이라는 요소가 추가되어서 약간 복잡하긴 하다.
이는 다음과 같은 방법으로 해결할 수 있다.

0. 고슴도치보다 물이 먼저 이동하도록 한다.
1. 먼저 물을 퍼뜨린다. 물 주변에 '.'가 있다면 모두 '*'로 변경한다.
2. queue를 이용해서 고슴도치가 주위 빈 칸으로 이동한다.
3. 고슴도치가 비버 굴에 도달하면 끝내고 분을 출력한다.

---

풀이

기본적인 아이디어는 다음과 같다.

1. (정리 예정)

이를 구현한 코드는 다음과 같다.

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

public class Main {
    static int R, C;
    static String[][] map;
    static int answer;
    static boolean[][] visited;
    static int[] originHedge;
    
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    
    public static void getInput() throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	// R과 C 입력 받기
    	String[] firstLine = br.readLine().split(" ");
    	R = Integer.parseInt(firstLine[0]);
    	C = Integer.parseInt(firstLine[1]);
    	
    	// 지도 입력 받기, 고슴도치 초기 위치 찾기
    	map = new String[R][C];
    	for (int i = 0; i < R; i++) {
    		String[] nowLine = br.readLine().split("");
    		for (int j = 0; j < C; j++) {
    			map[i][j] = nowLine[j];
    			if (map[i][j].equals("S")) {
    				originHedge = new int[] {i, j, 0};
    			}
    		}
    	}
    }
    
    public static void waterMove() {
    	Deque<int[]> originWater = new ArrayDeque<int[]>();
    	
    	// 현재 물의 위치를 큐에 저장
    	for (int i = 0; i < R; i++) {
    		for (int j = 0; j < C; j++) {
    			if (map[i][j].equals("*")) {
    				int[] point = {i, j};
    				originWater.add(point);
    			}
    		}
    	}
    	
    	// 물이 이동한 이후의 지도 얻기
    	for (int[] nowWater: originWater) {
    		for (int i = 0; i < 4; i++) {
    			int xdx = nowWater[1] + dx[i];
    			int ydy = nowWater[0] + dy[i];
    			if (xdx >= 0 && xdx < C && ydy >= 0 && ydy < R) {
    				if (map[ydy][xdx].equals(".")) {
    					map[ydy][xdx] = "*";
    				}
    			}
    		}
    	}
    }
    
    public static int hedgeMove() {
    	Deque<int[]> hedgePos = new ArrayDeque<int[]>();
    	
    	hedgePos.add(originHedge);
    	visited[originHedge[0]][originHedge[1]] = true;
    	
    	int flag = -1;
    	
	    while (hedgePos.size() > 0) {
	    	int[] nowHedge = hedgePos.poll();
	    		
	    	// 처음으로 해당 분을 만나면 물 이동
	    	if (nowHedge[2] > flag) {
	    		waterMove();
	    		flag += 1;
	    	}

	    	// 고슴도치 이동
	    	for (int i = 0; i < 4; i++) {
	    		int xdx = nowHedge[1] + dx[i];
	    		int ydy = nowHedge[0] + dy[i];
	    		int minute = nowHedge[2] + 1;
	    		if (xdx >= 0 && xdx < C && ydy >= 0 && ydy < R) {
	    			if (map[ydy][xdx].equals("D")) {
	    				return minute;
	    			}
	    			else if (map[ydy][xdx].equals(".") && !visited[ydy][xdx]) {
	    				int[] movedHedge = new int[] {ydy, xdx, minute};
	    				hedgePos.add(movedHedge);
	    				visited[ydy][xdx] = true;
	    			}
	    		}
	    	}
    	}
    	// 도달하지 못했으면 -1 리턴
    	return -1;
    }
    
    
    public static void main(String[] args) throws IOException {
        getInput();
        
    	// visited 생성
    	visited = new boolean[R][C];
        
        answer = hedgeMove();
        
        if (answer > 0) {
        	System.out.println(answer);
        } else {
        	System.out.println("KAKTUS");
        }

    }
}

---

회고

틀렸던 이유 1
각 초마다 물이 퍼지는 것을 제대로 처리하지 못했다.
flag를 도입해서 이를 해결했다.

틀렸던 이유 2
초기 위치의 방문 여부를 기록하지 않았고, 루프 내에서도 방문 여부를 잘못 기록해서 틀렸다.