[BOJ6087] 레이저 통신 (다익스트라, BFS)

 

 

---

문제 링크 

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

6087번: 레이저 통신

 

문제 풀이 

- 다익스트라 알고리즘, bfs 수행하면서 방향 전환시 같은 방향이 아닌 경우 거울을 하나씩 추가한다

- 두 점을 이으면서 거울의 최소값을 구하면 되는 아주 Simple한 문제인 줄 알았으나 .. 중복 방문 처리에 대한 예외 케이스가 있었다

 

 

아래 예외 케이스를 참고하도록 하자

https://www.acmicpc.net/board/view/109356

글 읽기 - 데이터를 추가해 주세요.

 

7개월 전에 정답이 절반으로 줄어들었다니 .. (충격)

 

 

다익스트라 알고리즘에서 이전 거울보다 같거나 작은 경우(이하)에 우선 순위 큐로 추가하도록 하였다. (뻔한 더 적은 비용일때 큐에 추가하는 조건식 부분이다)

if(windows[dx][dy] >= window) {
	//..
}

 

아래 예외 케이스를 돌리게 되면 사용한 거울의 개수가 동일한데 같은 칸을 방문하게 될 경우 큐에 계속해서 중복 데이터가 삽입이 되어 메모리 초과 발생하게 된다.

 

예로 (1, 2) 에서 겹치게 되면서 같은 정보 2개가 쌓이고, 이후 동쪽(오른쪽) 방향으로 이동시 또 객체가 중복으로 우선 순위 큐 쌓인다

 

 

해결1) 

- 결국 같은 좌표에 동일한 거울 수로 중복 방문 경우를 방지하기 위해 Set을 사용하여 풀이하였다

- equals와 hashCode 정의도 필요

다른 사람 풀이를 찾아보니 3차원 배열로 방향에 대한 정보 추가해서 중복 방문 방지하였다
방향을 배열로 만들 생각을 못하다니 .. (반성)
메모리적인 측면에서도 더 나은것으로 보인다 

int[행][열][방향] => 4byte * 100 * 100 * 5 = 20kb

 

해결2) 

방향 정보를 추가한 3차원 배열로 중복 방문 처리 하도록 하여 재풀이 (개인적으로 다익스트라 기본 풀이 형식 같아서 더 깔끔한 듯 함)

 

제출 코드 

1) HashSet 사용하여 중복 방문 처리 하는 경우

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

public class Main {
    
    static int W, H;
    static char[][] board;

    static Point[] points = new Point[2]; // 0 : 시작, 1 : 종료

    static int[][] dir = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    // 레이저로 연결해야 하는 칸 정보 (2개)
    static class Point {
        int x;
        int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static class Info implements Comparable<Info> {
        int x;
        int y;

        int dir; // 이전 방향

        int window; // 사용한 거울 개수

        public Info(int x, int y, int dir, int window) {
            this.x = x;
            this.y = y;
            this.dir = dir;
            this.window = window;
        }

        @Override
        public int compareTo(Info info) {
            return window - info.window;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Info info = (Info) o;
            return x == info.x && y == info.y && dir == info.dir && window == info.window;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y, dir, window);
        }
    }

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        W = Integer.parseInt(st.nextToken()); // 열 (y축)
        H = Integer.parseInt(st.nextToken()); // 행 (x축)

        int idx = 0;
        board = new char[H][W];
        for(int i = 0; i < H; i++) {
            String line = br.readLine();
            for(int j = 0; j < W; j++) {
                if(line.charAt(j) == 'C') { //
                    points[idx++] = new Point(i, j);
                }

                board[i][j] = line.charAt(j);
            }
        }
    }

    static void dijkstra(int startX, int startY) {
        Queue<Info> que = new PriorityQueue<>();
        que.add(new Info(startX, startY,-1, 0)); // 초기 방향은 -1

        int[][] windows = new int[H][W];
        for(int i = 0; i < H; i++) Arrays.fill(windows[i], Integer.MAX_VALUE);

        windows[startX][startY] = -1;

        Set<Info> unique = new HashSet<>();
        unique.add(new Info(startX, startY,-1, 0));

        while(!que.isEmpty()) {
            Info cur = que.poll();

            if(points[1].x == cur.x && points[1].y == cur.y) { // 종료
                System.out.println(cur.window);
                return;
            }

            for(int i = 0; i < 4; i++) {
                int dx = cur.x + dir[i][0];
                int dy = cur.y + dir[i][1];

                if(dx < 0 || dy < 0 || dx >= H || dy >= W) continue;
                if(board[dx][dy] == '*') continue; // * : 벽

                int window = cur.window;
                if(cur.dir != -1 && cur.dir != i) window += 1;

                if(windows[dx][dy] >= window) {
                    Info next = new Info(dx, dy, i, window);
                    if(unique.contains(next)) continue;

                    windows[dx][dy] = window;
                    que.add(new Info(dx, dy, i, window));
                    unique.add(next);
                }
            }
        }
    }

    static void pro() {
        dijkstra(points[0].x, points[0].y);
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
    
}

 

 

2) 방향 정보 추가한 3차원 배열 사용하여 중복 방문 처리할 경우

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

public class Main {
    
   static int W, H;

    static String[] fieldMap;

    static Point[] points = new Point[2];

    static class Point {
        int x;
        int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static class Info implements Comparable<Info> {
        int x;
        int y;
        int dir; // 이전 방향
        int mirror; // 거울 수

        public Info(int x, int y, int dir, int mirror) {
            this.x = x;
            this.y = y;
            this.dir = dir;
            this.mirror = mirror;
        }

        @Override
        public int compareTo(Info o) {
            return mirror - o.mirror; // ascending, 오름차순
        }
    }


    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        W = Integer.parseInt(st.nextToken()); // 가로 (열)
        H = Integer.parseInt(st.nextToken()); // 세로 (행)

        int idx = 0;
        fieldMap = new String[H];
        for(int i = 0; i < H; i++) {
            st = new StringTokenizer(br.readLine());

            String line = st.nextToken();
            fieldMap[i] = line;

            for(int j = 0; j < W; j++) {
                if(line.charAt(j) == 'C') {
                    points[idx++] = new Point(i, j);
                }
            }
        }

    }

    static int[][] dir = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    static void dijkstra(int startX, int startY) {
        Queue<Info> que = new PriorityQueue<>();
        que.add(new Info(startX, startY, -1, 0)); // 초기 방향 -1

        int[][][] mirrorCnt = new int[H][W][5]; // 3차원 배열로 방향 정보 추가
        for(int i = 0; i < H; i++) {
            for(int j = 0; j < W; j++) {
                Arrays.fill(mirrorCnt[i][j], Integer.MAX_VALUE);
            }
        }

        while(!que.isEmpty()) {
            Info cur = que.poll();

            if(cur.x == points[1].x && cur.y == points[1].y) {
                System.out.println(cur.mirror);
                return;
            }

            for(int i = 0; i < 4; i++) {
                int dx = cur.x + dir[i][0];
                int dy = cur.y + dir[i][1];

                if(dx < 0 || dy < 0 || dx >= H || dy >= W) continue;
                if(fieldMap[dx].charAt(dy) == '*') continue;

                int mirror = cur.mirror;
                // 초기 방향(-1)아니고, 이전 방향과 다음 방향이 다르면 거울 추가
                if(cur.dir != -1 && cur.dir != i) mirror += 1;

                if(mirrorCnt[dx][dy][i] > mirror) { // 거울 수가 더 적은 경우에만
                    mirrorCnt[dx][dy][i] = mirror;
                    que.add(new Info(dx, dy, i, mirror));
                }
            }
        }
    }

    static void pro() {
        dijkstra(points[0].x, points[0].y);
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
    
}