[백준] 6087: 레이저 통신 JAVA

접근

푸는데 정말 오래걸린 문제였다..ㅠㅠ 다른 블로그의 솔루션들과 아무리 비교해봐도 똑같은데 자꾸 메모리 초과가 나는 것이다. 그래서 혹시나하고 솔루션 코드를 돌려봤는데.. 똑같이 메모리 초과가 났다. 알고보니 불과 3일전(!)에 데이터가 추가되면서, 4142개 중 1475개의 기존 정답 코드가 메모리 초과가 되었더라😂

그래서 이 블로그의 솔루션 코드를 참고하여 통과할 수 있었다. 기존에는 2차원 배열에 해당 위치에 올 수 있는 거울의 최소 개수를 저장했었다. 그런데 통과한 코드에는 3차원 배열을 선언하여 방향까지 함께 고려해줘야 했다. 아마 추가된 데이터에서 같은 칸, 방향에 여러번 방문하는 경우가 있지 않을까 짐작해본다. 그런데 이상하게 내 코드에서는 현재 방향과 정반대의 경우 넘어가는 조건 Math.abs(now.dir - i) == 2 을 추가하면 틀리게 나온다.. 이유는 아직 모르겠지만 알게된다면 포스팅을 수정하러 오겠다. 

 

반례 모음은 이쪽

 

코드

메모리 초과 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BJ6087 {
    static class Pos implements Comparable<Pos> {
        int x, y, mirrorCnt, dir;

        public Pos(int x, int y, int mirrorCnt, int dir) {
            this.x = x;
            this.y = y;
            this.mirrorCnt = mirrorCnt; // [x][y]에 도달하기 위해 필요한 거울의 개수
            this.dir = dir;
        }

        @Override
        public int compareTo(Pos o) {
            return this.mirrorCnt - o.mirrorCnt;
        }
    }

    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int INF = 100*100+1;
    static int w, h;

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

        // 입력값 저장
        w = Integer.parseInt(st.nextToken());
        h = Integer.parseInt(st.nextToken());

        char[][] map = new char[h][w];
        int[][] minCnt = new int[h][w];
        Pos from = null, to = null;

        for (int i = 0; i < h; i++){
            map[i] = br.readLine().toCharArray();

            for (int j = 0; j < w; j++) {
                if(map[i][j] == 'C'){ // 시작 및 도착 위치
                    if(from == null) from = new Pos(i, j, -1, -1);
                    else to = new Pos(i, j, -1, -1);
                }
            }
        }

        // 결과 출력
        System.out.println(bfs(from, to, map, minCnt));
    }

    private static int bfs(Pos from, Pos to, char[][] map, int[][] minCnt) {
        PriorityQueue<Pos> pq = new PriorityQueue<>();

        for (int i = 0; i < map.length; i++)
            Arrays.fill(minCnt[i], INF);

        // 시작지점 처리
        pq.add(from);
        minCnt[from.x][from.y] = 0;

        // bfs
        while(!pq.isEmpty()){
            Pos cur = pq.poll();

            // 도착지점 도달
            if(cur.x == to.x && cur.y == to.y)
                return cur.mirrorCnt;

            // 거울 개수가 갱신되지 않는 경우 넘어감
            if(minCnt[cur.x][cur.y] < cur.mirrorCnt) continue;

            for (int d = 0; d < 4; d++) {
                int nx = cur.x + dx[d];
                int ny = cur.y + dy[d];

                // 범위를 벗어나거나 벽이면 넘어감
                if(!inBound(nx, ny, w, h) || map[nx][ny] == '*') continue;

                Pos next = new Pos(nx, ny, cur.mirrorCnt, d);
                if(d != cur.dir) next.mirrorCnt++;

                // 거울 개수가 갱신되지 않는 경우 넘어감
                if(minCnt[nx][ny] < next.mirrorCnt) continue;

                minCnt[nx][ny] = next.mirrorCnt;
                pq.add(next);
            }
        }

        return -1;
    }

    private static boolean inBound(int x, int y, int w, int h) {
        return !(x < 0 || y < 0 || x >= h || y >= w);
    }
}

 

정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BJ6087 {
    static class Pos implements Comparable<Pos> {
        int x, y, mirrorCnt, dir;

        public Pos(int x, int y, int mirrorCnt, int dir) {
            this.x = x;
            this.y = y;
            this.mirrorCnt = mirrorCnt; // [x][y]에 도달하기 위해 필요한 거울의 개수
            this.dir = dir;
        }

        @Override
        public int compareTo(Pos o) {
            return this.mirrorCnt - o.mirrorCnt;
        }
    }

    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int INF = 100*100+1;
    static int w, h;

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

        // 입력값 저장
        w = Integer.parseInt(st.nextToken());
        h = Integer.parseInt(st.nextToken());

        char[][] map = new char[h][w];
        int[][][] visited = new int[4][h][w];
        Pos from = null, to = null;

        for (int i = 0; i < h; i++){
            map[i] = br.readLine().toCharArray();

            for (int j = 0; j < w; j++) {
                if(map[i][j] == 'C'){ // 시작 및 도착 위치
                    if(from == null) from = new Pos(i, j, -1, -1);
                    else to = new Pos(i, j, -1, -1);
                }
            }
        }

        // 결과 출력
        System.out.println(bfs(from, to, map, visited));
    }

    private static int bfs(Pos from, Pos to, char[][] map, int[][][] visited) {
        PriorityQueue<Pos> pq = new PriorityQueue<>();

        for (int d = 0; d < 4; d++) {
            for (int i = 0; i < h; i++)
                Arrays.fill(visited[d][i], INF);
        }

        // 시작지점 처리
        pq.add(from);

        // bfs
        while(!pq.isEmpty()){
            Pos cur = pq.poll();

            // 도착지점 도달
            if(cur.x == to.x && cur.y == to.y)
                return cur.mirrorCnt;

            for (int d = 0; d < 4; d++) {
                int nx = cur.x + dx[d];
                int ny = cur.y + dy[d];

                // 범위를 벗어나거나 벽이면 넘어감
                if(!inBound(nx, ny, w, h) || map[nx][ny] == '*') continue;

                Pos next = new Pos(nx, ny, cur.mirrorCnt, d);
                if(d != cur.dir) next.mirrorCnt++;

                if(visited[d][nx][ny] > next.mirrorCnt) {
                    visited[d][nx][ny] = next.mirrorCnt;
                    pq.add(next);
                }
            }
        }

        return -1;
    }

    private static boolean inBound(int x, int y, int w, int h) {
        return !(x < 0 || y < 0 || x >= h || y >= w);
    }
}