[BOJ] 6087.레이저 통신(BFS).java

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

 

처음에는 우선순위큐를 사용해서 BFS로 풀었는데

더 효율적으로 풀 수 있는 방법이 없을까 하고 여러 코드를 참고하다가

BFS + DP로 해결한 코드를 참고해서 DP로도 다시 짜보았다.

#. Code_PQ

우선순위큐를 사용한 방법은

거울을 사용한 갯수가 적은 좌표부터 먼저 확인을 하는 방법이다.

그렇게 되면 레이저로 연결되어야 하는 다른 좌표로 도달했을 때,

거울 개수의 최솟값이 된다.

하지만, 레이저가 왔던 길을 돌아가지 않도록 방문 처리를 해주어야 하는데,

방향별로 visited 처리를 해주어서 3차원 visited 배열을 사용하였다.

그리고 4방 탐색을 하는데 

지금 가고 있는 방향과 같은 방향이면 그냥 pq에 넣어주고,

방향이 꺽여서 거울을 놓아야 하는 상황으면 pq에 사용 거울 갯수 + 1 로 넣어준다.

여기서 참고해야 할 점은,

visite 처리를 queue에서 뺄 때 해주어야 하는데

`더 많은 거울을 사용한 경우`와 `더 적은 거울을 사용한 경우`가 같은 방향으로 나아갈 때,

`더 많은 거울을 사용한 경우`가 먼저 다음 좌표를 방문해서 visite 처리를 해버리면,

`더 적은 거울을 사용한 경우`는 최적의 해가 될 수 있음에도 이미 visite 처리가 되어버린 좌표에 방문할 수 없게 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class BOJ6087 {
 
    static int W, H;
    static char map[][];
    static int[] dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
    static class State implements Comparable<State> {
        int x, y;
        int dir; // 동,서,남,북
        int cnt;
        
        public State(int x, int y, int dir, int cnt) {
            super();
            this.x = x;
            this.y = y;
            this.dir = dir;
            this.cnt = cnt;
        }
 
        @Override
        public int compareTo(State o) {
            return Integer.compare(this.cnt, o.cnt);
        }
    }
    
    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());
        map = new char[H][W];
        // 시작 레이저 확인 여부
        boolean isStart = false;
        State start = null, end = 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(!isStart) {
                        start = new State(i, j, 0, 0);
                        isStart = true;
                    }
                    else end = new State(i, j, 0, 0);
                }
            }
        }
        
        System.out.println(go(start, end));
    }
 
    private static int go(State start, State end) {
 
        PriorityQueue<State> pQ = new PriorityQueue<>();
        // 방향별 visit 확인
        boolean[][][] visited = new boolean[4][H][W];
 
        // 시작점으로부터 4방향을 pq에 먼저 넣어주자
        for (int d = 0; d < 4; d++) {
            int xx = start.x + dx[d];
            int yy = start.y + dy[d];
            // 범위를 벗어날 경우
            if(xx < 0 || yy < 0 || xx >= H || yy >= W) continue;
            // 벽일 경우
            if(map[xx][yy] == '*') continue;
            pQ.add(new State(xx, yy, d, 0));
        }
        
        while(!pQ.isEmpty()) {
            
            State now = pQ.poll();
            // 도착 지점에 도달
            if(now.x == end.x && now.y == end.y) 
                return now.cnt;
            // 이미 방문한 지점이면 pass
            if(visited[now.dir][now.x][now.y]) continue;
            // 방문하지 않았던 곳이라면 visite 처리
            visited[now.dir][now.x][now.y] = true;
            
            // 4방 탐색
            for (int d = 0; d < 4; d++) {
                int xx = now.x + dx[d];
                int yy = now.y + dy[d];
                // 범위를 벗어날 경우
                if(xx < 0 || yy < 0 || xx >= H || yy >= W) continue;
                // 벽일 경우
                if(map[xx][yy] == '*') continue;
                
                // 지금 가고 있는 방향과 같은 방향일 경우
                if(now.dir == d) pQ.add(new State(xx, yy, d, now.cnt));
                // 다른 방향일 경우(방향이 꺽일 때)
                else pQ.add(new State(xx, yy, d, now.cnt + 1));
            } 
        }
    
        return 0;
    }
 
}
 

#. Code_BFS+DP

다음은 BFS + DP 로 해결한 방법이다.

4방 탐색을 하는 과정에서 범위를 벗어나거나, 벽이 나올 때까지 

초기 좌표로부터 정말 레이저를 쏘는 것처럼 직진한다.

직진하는 과정에서 방문하지 않은 좌표라면

해당 좌표까지 사용한 거울의 갯수를 저장해주고 Queue에 넣어준다.

이렇게 되면 모든 방향으로 뻗어나갈 것이다.

[., ., ., ., ., ., .]

[., ., ., ., ., ., C]

[., ., ., ., ., ., *]

[*, *, *, *, *, ., *]

[., ., ., ., *, ., .]

[., ., ., ., *, ., .]

[., C, ., ., *, ., .]

[., ., ., ., ., ., .]

[2, 2, 2, 2, 2, 2, 1]

[1, 1, 1, 1, 1, 1, 2]

[2, 2, 2, 2, 2, 2, 0]

[0, 0, 0, 0, 0, 2, 0]

[0, 4, 4, 4, 0, 2, 3]

[0, 4, 4, 4, 0, 2, 3]

[0, 4, 4, 4, 0, 2, 3]

[3, 3, 3, 3, 3, 2, 3]

그러다가 도착점을 만나면 return 해주자.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer;   public class BOJ6087_v2 {       static int W, H;     static char map[][];     static int[][] dist;     static int[] dx = { 0, 0, 1, -1 }, dy = { 1, -1, 0, 0 };       static class State {         int x, y;           public State(int x, int y) {             this.x = x;             this.y = y;         }     }       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());         map = new char[H][W];         // 시작 레이저 확인 여부         boolean isStart = false;         State start = null, end = 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 (!isStart) {                         start = new State(i, j);                         isStart = true;                     } else                         end = new State(i, j);                 }             }         }           go(start, end);         System.out.println(dist[end.x][end.y] - 1);     }       private static void go(State start, State end) {           Queue<State> q = new LinkedList<>();         dist = new int[H][W];         // 시작점부터 출발         q.add(start);           while (!q.isEmpty()) {             State now = q.poll();             if(dist[end.x][end.y] != 0) return;             // 4방 탐색             for (int d = 0; d < 4; d++) {                 int xx = now.x + dx[d];                 int yy = now.y + dy[d];                 // 범위를 벗어나지 않고, 벽이 나올 때까지 이동                 while (xx >= 0 && yy >= 0 && xx < H && yy < W && map[xx][yy] != '*') {                     if (dist[xx][yy] == 0) {                         dist[xx][yy] = dist[now.x][now.y] + 1;                         q.add(new State(xx, yy));                     }                     xx += dx[d];                     yy += dy[d];                 }             }         }                  return;     } }   Colored by Color Scripter

cs