백준 2206_벽 부수고 이동하기_JAVA

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

 

시간초과 코드

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

public class Main {
    static int answer = Integer.MAX_VALUE;
    static int N, M;
    static int[][] grid;
    static int[][] newGrid;
    static boolean[][] visited;
    static ArrayList<int[]> arr = new ArrayList<>();
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        grid = new int[N][M];
        visited = new boolean[N][M];

        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            for (int j = 0; j < line.length(); j++) {
                grid[i][j] = Integer.parseInt(String.valueOf(line.charAt(j)));
                if (grid[i][j] == 1) {
                    arr.add(new int[]{i, j});
                }
            }
        }

        for (int i = 0; i < arr.size(); i++) {
            newGrid = new int[N][M];
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < M; k++) {
                    newGrid[j][k] = grid[j][k];
                }
            }
            newGrid[arr.get(i)[0]][arr.get(i)[1]] = 0;

            bfs(0, 0, 1);
        }

        if (answer == Integer.MAX_VALUE) {
            System.out.println(-1);
        } else {
            System.out.println(answer);
        }
    }

    private static void bfs(int x, int y, int c) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{x, y, c});
        visited[x][y] = true;

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int cx = cur[0];
            int cy = cur[1];
            int cc = cur[2];

            if (cx == N - 1 && cy == M - 1) {
                if (answer > cc) {
                    answer = cc;
                    return;
                }
                return;
            }

            for (int i = 0; i < 4; i++) {
                int nx = cx + dx[i];
                int ny = cy + dy[i];
                int nc = cc + 1;
                if (nx >= 0 && ny >= 0 && nx < N && ny < M && !visited[nx][ny] && newGrid[nx][ny] == 0) {
                    queue.add(new int[]{nx, ny, nc});
                    visited[nx][ny] = true;
                }
            }
        }
    }
}

 

풀이가 바로 머리에 떠올랐고 신나서 브루트포스 + BFS로 풀다가 시간 초과가 나버렸다.

너무 당황스러웠다

 

 

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

public class Main {
    static int answer = Integer.MAX_VALUE;
    static int N, M;
    static int[][] grid;
    static int[][] newGrid;
    static boolean[][][] visited;
    static ArrayList<int[]> arr = new ArrayList<>();
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        grid = new int[N][M];
        visited = new boolean[2][N][M]; // 벽을 부쉈으면 1, 아니면 0

        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            for (int j = 0; j < line.length(); j++) {
                grid[i][j] = Integer.parseInt(String.valueOf(line.charAt(j)));
                if (grid[i][j] == 1) {
                    arr.add(new int[]{i, j});
                }
            }
        }

        bfs(0, 0, 0, 1);


        if (answer == Integer.MAX_VALUE) {
            System.out.println(-1);
        } else {
            System.out.println(answer);
        }
    }

    private static void bfs(int x, int y, int b, int c) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{x, y, b, c});
        visited[b][x][y] = true;

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int cx = cur[0];
            int cy = cur[1];
            int cb = cur[2]; // 이걸 진행하면서 벽을 깼는지 안깼는지 확인
            int cc = cur[3]; // 진행 칸 수

            if (cx == N - 1 && cy == M - 1) {
                if (answer > cc) {
                    answer = cc;
                    return;
                }
                return;
            }

            for (int i = 0; i < 4; i++) {
                int nx = cx + dx[i];
                int ny = cy + dy[i];
                int nc = cc + 1;

                if (nx >= 0 && ny >= 0 && nx < N && ny < M) {
                    if (grid[nx][ny] == 1) { // 다음 칸이 벽일 때
                        // 지금까지 오면서 벽을 부수지 않고 왔고
                        // 아직 이 좌표까지 벽을 부수지 않고는 방문하지 않았다면
                        if (cb == 0 && !visited[1][nx][ny]) {
                            visited[cb][nx][ny] = true; // 방문처리
                            queue.add(new int[]{nx, ny, 1, nc});
                        }
                    } else { // 벽이 아닐때
                        if (!visited[cb][nx][ny]) { // 현 좌표를 방문하지 않았으면
                            visited[cb][nx][ny] = true; // 방문처리
                            queue.add(new int[]{nx, ny, cb, nc});
                        }
                    }
                }
            }

        }
    }
}

- 회고

- 떠오르지 않아서 블로그를 검색해서 보았는데 3차원 배열을 쓰는 문제였다

- 진짜 정말 어려웠지만 이해는 되어서 다행이다

- 다음에 다시 한 번 풀어봐야겠다