[분류]

  • 그리디

[문제링크]

[요구사항]

  • C를 연결하기 위해 설치해야 하는 거울 개수의 최솟값을 출력한다.

[풀이]

  1. 최단 경로를 구하는 것이 아니라 거울 설치 수가 최소가 되는 것을 구하는 것이 포인트이다.

  2. 가는 길에 거치는 장소마다 visited를 지금까지 설치한 거울갯수로 저장해서 그것보다 크면 큐에 넣지 않는 식으로 진행한다.

  3. 큐가 empty가 되면 결과를 출력한다.

[코드]

//baekjoon_6087_레이저통신
import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.Buffer;
import java.util.*;

public class Main {
    static int n, m;
    static char[][] map;
    static int[][] visited;
    static int res = 987654321;
    static int dx[] = {0, -1, 0, 1};
    static int dy[] = {1, 0, -1, 0};
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        int startX=0, startY=0, endX=0, endY=0;
        boolean flag = false;
        m = Integer.parseInt(s[0]);
        n = Integer.parseInt(s[1]);

        map = new char[n][m];
        visited = new int[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++)
                visited[i][j]=987654321;
        }

        for(int i=0;i<n;i++){
            String line = br.readLine();
            for(int j=0;j<m;j++){
                map[i][j] = line.charAt(j);

                if(map[i][j] == 'C'){
                    if(!flag){
                        startX = i;
                        startY = j;
                        flag = true;
                    }else{
                        endX = i;
                        endY = j;
                    }
                }
            }
        }//정보받기

        Queue<Point> q = new LinkedList<>();

        visited[startX][startY]=0;
        for(int i=0;i<4;i++){
            int nx = startX+dx[i];
            int ny = startY+dy[i];

            if(!isBorder(nx, ny) && map[nx][ny]!='*'){
                q.add(new Point(nx, ny, i, 0));
                visited[nx][ny] = 0;
            }
        }

        while(!q.isEmpty()){
            Point p = q.poll();

            if(p.x==endX && p.y==endY){
                if(res>p.mirror)
                    res = p.mirror;
                continue;
            }

            int nx = p.x+dx[p.dir];
            int ny = p.y+dy[p.dir];
            if(!isBorder(nx, ny) && visited[nx][ny]>=p.mirror && map[nx][ny]!='*'){
                visited[nx][ny]=p.mirror;
                q.add(new Point(nx, ny, p.dir, p.mirror));
            }

            int ndir = (p.dir +1)%4;
            nx = p.x+dx[ndir];
            ny = p.y+dy[ndir];
            int nmirror = p.mirror+1;
            if(!isBorder(nx, ny) && visited[nx][ny]>=nmirror && map[nx][ny]!='*'){
                visited[nx][ny]=nmirror;
                q.add(new Point(nx, ny, ndir, nmirror));
            }

            ndir = (p.dir + 3)%4;
            nx = p.x+dx[ndir];
            ny = p.y+dy[ndir];
            nmirror = p.mirror+1;
            if(!isBorder(nx, ny) && visited[nx][ny]>=nmirror && map[nx][ny]!='*'){
                visited[nx][ny]=nmirror;
                q.add(new Point(nx, ny, ndir, nmirror));
            }

        }
        System.out.println(res);
    }

    private static boolean isBorder(int x, int y){
        if(x<0 || y<0 || x>n-1 || y>m-1) return true;
        return false;
    }

    private static class Point{
        int x, y, dir, mirror;

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



[통과여부]

image

[느낀점]

조건을 확인하는데 점마다에서 모두 거울 갯수를 생각해준다는 것이 어려웠다.