[Java] 백준 6087번 : 레이저 통신

1. 문제

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

6087번: 레이저 통신

 

 

2. 풀이 과정

처음에는 오는 방향에 따라 들어온 방향과 같으면 거울 수를 추가하지 않고, 들어온 방향과 다르면 거울 수를 추가해서 처리했다. PriorityQueue를 사용해서 사용한 거울 수가 작은 경로부터 처리해서 도착지가 나오면 종료했다.

코드는 아래에 [더보기]를 클릭하면 볼 수 있다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static int h, w;
    static boolean visited[][][];
    static char map[][];

    static class Point implements Comparable<Point> {
        int x, y, dir, mirror;

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

        @Override
        public int compareTo(Point o){
            return this.mirror - o.mirror;
        }
    }

    public static void main(String[] args) 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());
        visited = new boolean[h][w][4];
        map = new char[h][w];
        String s;
        int sx = 0, sy = 0;

        for(int i=0; i<h; i++) {
            s = br.readLine();
            for(int j=0; j<w; j++) {
                map[i][j] = s.charAt(j);
                //출발지 & 도착지 저장
                if(map[i][j]=='C') {
                    sx = i;
                    sy = j;
                }
            }
        }

        map[sx][sy] = '.';
        System.out.println(bfs(sx, sy));
    }

    public static int bfs(int sx, int sy) {
        int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
        PriorityQueue<Point> pq = new PriorityQueue<>();
        //좌표x, y, 들어온 방향, 거울 수
        //시작값 넣기
        pq.add(new Point(sx, sy, -1, -1));

        while(!pq.isEmpty()) {
            Point now = pq.poll();
            //도착지면 stop
            if(map[now.x][now.y] == 'C') {
                return now.mirror;
            }

            for(int i=0; i<4; i++) {
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];
                if(nx<0 || nx>=h || ny<0 || ny>=w || map[nx][ny] == '*' || visited[nx][ny][i]){
                    continue;
                }
                visited[nx][ny][i] = true;
                int temp = now.mirror;
                if(now.dir!=i){temp++;}
                pq.add(new Point(nx, ny, i, temp));

            }
        }
        return -1;
    }
}

 

하지만 PriorityQueue는 값이 들어올 때마다 정렬해야하기 때문에, 다음과 같이 개선했다.

그냥 Queue를 써서 조금 더 직관적으로 BFS를 구현했다. 해당 step에 갈 수 있는 경로는 while을 사용해서 한 번에 처리했다.

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

public class Main {
    static int h, w;
    static boolean visited[][][];
    static char map[][];

    public static void main(String[] args) 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());
        visited = new boolean[h][w][4];
        map = new char[h][w];
        String s;
        int sx = 0, sy = 0;

        for(int i=0; i<h; i++) {
            s = br.readLine();
            for(int j=0; j<w; j++) {
                map[i][j] = s.charAt(j);
                if(map[i][j]=='C') {
                    sx = i;
                    sy = j;
                }
            }
        }

        map[sx][sy] = '.';
        System.out.println(bfs(sx, sy));
    }

    public static int bfs(int sx, int sy) {
        int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
        Queue<int[]> q = new LinkedList<>();
        //시작값 넣기
        visited[sx][sy][0] = visited[sx][sy][1] = visited[sx][sy][2] = visited[sx][sy][3] = true;
        q.add(new int[]{sx, sy});

        int result = -1;
        while(!q.isEmpty()) {
            int size = q.size();
            while(size-- > 0){
                int[] now = q.poll();
                //도착지면 stop
                if(map[now[0]][now[1]] == 'C') {
                    return result;
                }

                for(int i=0; i<4; i++) {
                    int nx = now[0];
                    int ny = now[1];
                    while(true){
                        nx += dx[i];
                        ny += dy[i];
                        if(nx<0 || nx>=h || ny<0 || ny>=w || map[nx][ny] == '*' || visited[nx][ny][i]){
                            break;
                        }
                        visited[nx][ny][i] = true;
                        q.add(new int[]{nx, ny});
                    }
                }
            }
            result++;

        }
        return result;
    }
}

 

 

결과