정올[1082] - 화염에서 탈출

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=362&sca=3040

JUNGOL | 화염에서탈출(SLIKAR) > 문제은행

문제 해석

재우의 위치는 'S'로 표시
불은 '*' 로 표시
바위는 'X'로 표시
문제의 재우와 불은 (상,하,좌,우)로만 이동하게 된다.
이동시간과 불의 이동경로를 int 값으로 입력받을 수 있는 visit 2차원 배열을 만들었다.
재우와 불은 동시에 퍼지고 테스트케이스마다 불은 여러군데 있을 수 있기 때문에
전체 배열을 탐색하면서 Queue에 넣는 작업을 했다.

전체 코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main_1082_화염에서탈출 {
    static int R, C, endR, endC;
    static char map[][];
    static int visit[][];
    static int dir[][] = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

    public static void main(String[] args) throws Exception {
        System.setIn(new FileInputStream("res/bfs/1082.txt"));
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(in.readLine().trim());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        map = new char[R][C];
        visit = new int[R][C];
        for (int i = 0; i < R; i++) {
            map[i] = in.readLine().trim().toCharArray();
        }

        LinkedList<int[]> queue = new LinkedList<>();
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {

                if (map[i][j] == '*') {
                    visit[i][j] = -1;
                    queue.add(new int[] { i, j });
                }
                if (map[i][j] == 'D') {
                    endR = i;
                    endC = j;
                }
            }
        }
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (map[i][j] == 'S') {
                    visit[i][j] = 1;
                    queue.add(new int[] { i, j });
                }
            }
        }

        while (!queue.isEmpty()) {
            int cur[] = queue.poll();
            char a = map[cur[0]][cur[1]];
            if (a == 'S') {
                for (int i = 0; i < 4; i++) {
                    int nr = cur[0] + dir[i][0];
                    int nc = cur[1] + dir[i][1];
                    if (nr >= 0 && nc >= 0 && nr < R && nc < C && (map[nr][nc] == '.' || map[nr][nc] == 'D')
                            && visit[nr][nc] == 0) {
                        visit[nr][nc] = visit[cur[0]][cur[1]] + 1;
                        map[nr][nc] = 'S';
                        queue.add(new int[] { nr, nc });
                    }
                }
            } else if (a == '*') {
                for (int i = 0; i < 4; i++) {
                    int nr = cur[0] + dir[i][0];
                    int nc = cur[1] + dir[i][1];
                    if (nr >= 0 && nc >= 0 && nr < R && nc < C && map[nr][nc] == '.' && visit[nr][nc] == 0) {
                        visit[nr][nc] = -1;
                        map[nr][nc] = '*';
                        queue.add(new int[] { nr, nc });
                    }
                }
            }
        }
        int answer=0;
        if (visit[endR][endC] == 0) {
            answer = -1;
        } else 
            answer = visit[endR][endC] - 1;


        if (answer == (-1)) {
            System.out.println("impossible");
        } else
            System.out.println(answer);

    }

}

느낀점

좀 더 쉽게 풀 수 있었던 거 같은데 아직 초보라 이게 최선인 듯 하다 ㅠㅠ
나중에 더 익숙해지면 다시 풀어봐야지
제출할 때 패키지명을 안지워서 런타임에러가 떴다... 10분간 고생했다ㅜㅜㅜ