[JAVA] 백준 - 레이저 통신 6087 (BFS) (테스트케이스 제공)

www.acmicpc.net/problem/6087

6087번: 레이저 통신

 

시작점 부터 도착점 까지 BFS 로 최소 개수의 거울 수를 업데이트한다.

처음에는 DFS로 쉽게 풀 수있을 거 같았지만 100 * 100 배열을 돌리니까 stackoverflow 가 발생했다.

BFS 로 최소 거울 수 를 업데이트  해야한다.

 

# 풀이

 

1. 클래스 정의

    static class Pair{
        int x,y,dir,mirror;

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

 

습관적으로 이름을 Pair 라고 명명해버렸다.

 

x,y 는 현재 위치한 좌표이며 dir 은 현재 좌표에서 방향을 나타내고, mirror 는 x,y 까지 오기 위해 사용한 거울의 숫자를 나타낸다.

 

2. BFS 핵심 로직

 

1) 현재 좌표에서 4가지 방향(상,하,좌,우) 중 유효한 좌표로 이동한 좌표를 구한다.

2) 해당 좌표를 방문한 적이 없다면 방문하고 거울 수를 저장한 다음 bfs 큐에 넣는다.

2-1) 만약 해당 좌표를 방문한적이 있지만 해당 좌표까지 가지고 있던 거울수 보다 작거나 같으면 거울 수를 저장하고 bfs 큐에 넣는다.

 

 

3. 테스트 케이스

ex)

2 5
C.
..
..
*.
C.

answer) 2

 

만약 3이 나온다면 2-1) 에서 작거나 같으면 BFS 큐에 넣었는 지 확인해본다.

 

 

# 전체 코드

import java.util.LinkedList;
import java.util.*;

class Main{
    static int n,m;
    static char[][] map;
    static int[] start = new int[2];
    static int[] end = new int[2];
    static int[][] ch;

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


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        m = sc.nextInt();
        n = sc.nextInt();
        map = new char[n][m];
        ch = new int[n][m];
        for(int i=0;i<n;i++) Arrays.fill(ch[i],-1);

        boolean ok = false;
        for(int i=0;i<n;i++){
            char[] temp = sc.next().toCharArray();
            for(int j=0;j<m;j++){
                map[i][j] = temp[j];
                if(!ok && map[i][j] == 'C'){
                    start[0] = i;
                    start[1] = j;
                    ok = true;
                    ch[i][j] = 0;
                }
                if(ok && map[i][j]=='C'){
                    end[0] = i;
                    end[1] = j;
                }
            }
        }

        Queue<Pair> q = new LinkedList<>();
        for(int i=0;i<4;i++) q.add(new Pair(start[0],start[1],i,0 ));
        while(!q.isEmpty()){
            Pair p = q.poll();

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

                if(nx<0 || nx>=n || ny<0 || ny>=m) continue;
                if(map[nx][ny]=='.' || map[nx][ny]=='C'){
                    int nextMirror = p.dir!=i?p.mirror+1:p.mirror;
                    if((ch[nx][ny] == -1 ) ||
                            (ch[nx][ny] !=-1 && ch[nx][ny] >= nextMirror)){
                        ch[nx][ny] = nextMirror;
                        q.add(new Pair(nx,ny,i,nextMirror));
                    }
                }
            }
        }
        System.out.println(ch[end[0]][end[1]]);

    }

    static class Pair{
        int x,y,dir,mirror;

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



}