[백준 6087] 레이저 통신 -JAVA //le_effort//

개념적인 접근은 빠르게 잘했는데 반례를 찾지 못해 엄청 오랫동안 삽질한 문제이다.

방향이 바뀐다고 하는 것은 일반적인 bfs를 하면서 전 단계의 방향과 다르면 cnt를 +1 해주고

우선순위 큐로 cnt가 낮은걸 먼저 빼면 해결될 줄 알았다.

 

visited처리는  visited[x][y][방향] 3차원으로 뒀는데 내 풀이에는 3차원으로 하면 오답이 나왔다

물론 3차원으로도 풀 수 있는데 여태까지 코딩한게 아까워서 기존 풀이에서 해결하고 싶었다. 

 

 

4 3
C . . *
.  * . *
... C

이 경우

정답은 1이 나와야 한다

하지만 기존의 내 코드는 2가 나왔다

 

 

인덱스는 [0][0]부터 시작한다 하고

아래 방향으로 진행한다 쳤을 때 

내 생각엔 

[1][0]  [2][0] 은 방향이 아래, 거울 설치는 0

[1][1] [2][2]는 방향은 오른쪽 거울 설치는 1 --------POINT A

[2][3] 또한 오른쪽 방향에 거울설치는 1이 나와야 했지만 [2][3] 오른쪽 방향은 2가 나왔다

 

왜 그럴까 백준 슬랙에 질문을 해 본 결과

아무리 우선순위 큐로 cnt(거울 설치 횟수)가 낮은 순으로 뽑는 다고 해도

 

오른쪽 방향으로

[0][1] [0][2]  방향 오른쪽 거울 설치 0

[1] [2] [2][2] 방향 아래 거울 설치 1          ------------ POINT B

 

POINT A와 POINT B를 보자

[2][2]가 두 개 있다.

1. 현재 진행방향이 오른쪽인 것도 설치 횟수가 1 

2. 현재 진행방향이 아래쪽인 것도  설치 횟수가 1

 

[2][2]가 두 개 나올 수 있는 게 어떻게 가능하냐면  visited를 3차원으로 [x좌표][y좌표][방향]으로 뒀기 때문이다

[2][2][오른쪽]    [2][2][아래쪽] 이렇게 있다

하지만 목표인 C의 위치는 [2][3]인 것인데

우선순위 큐로 거울 횟수가 적은 것을 뽑는다 해도 [2][2][오른쪽] [2][2][아래쪽] 은 둘 다 1로 동일하다

 

운이 좋게 [2][2][오른쪽]인 것이 나올 수도 있지만 [2][2][아래쪽]이 나올 경우

[2][2] -> [2][3]으로 가기 위해선 [2][3][오른쪽]이 돼야 하므로

[2][2][아래쪽] -> [2][3][오른쪽] visited 처리 + 기존 방향이 다르니 +1 해서 2가 나오게 된다

 

뒤늦게 나온 [2][2][오른쪽]이  [2][3][오른쪽]을 방문하려고 해도 이미 위에서 방문처리돼서 방문을 못하게 된다.

 

그래서 나는 visited배열을 4차원으로 두고 해결했다. 

[x좌표][y좌표][현재 진행위치][이전 진행위치] 이렇게 함으로써 해결은 했지만  결코 효율적인 코드라고 할 수 없을 거 같다.

 

나중에 다시 한번 풀어봐야겠다.

초창기에 방향을 존재하지 않는 5로 두고 (존재하는 방향 = 0,1,2,3 = 오른쪽, 왼쪽, 아래, 위)

cnt를 -1로 둔 이유는

처음 시작하는 방향은 상하좌우 어디로 가든 거울을 설치했다고 보지 않기 때문에

기존 방향과 지금 가려는 방향이 다르면 +1을 해주는 코드가 있는데(56번째 줄)

 

처음 시작 방향 할 때 거울 횟수를 0으로 맞추기 위함이다.

 

 

import java.io.*;
import java.util.*;
public class Main {
    static int w,h;
    static Character map [][];
    static boolean visited[][][][];
    static int dx[] = {0,0,1,-1};
    static int min = Integer.MAX_VALUE;
    static int dy[] = {1,-1,0,0};
    static PriorityQueue<Node>q = new PriorityQueue<>();
    static ArrayList<Node>[]list;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String [] t = br.readLine().split(" ");
        w = Integer.parseInt(t[0]);
        h = Integer.parseInt(t[1]);
        map =  new Character[h][w];
        visited = new boolean[h][w][4][6];
        
        list = new ArrayList[2];
        
        for(int i=0; i<2; i++) {
            list[i] = new ArrayList<>();
        }
        int idx=0;    
        for(int i=0; i<h; i++) {
            String str = br.readLine();
            for(int j=0; j<w; j++) {
                map[i][j] = str.charAt(j);
                if(map[i][j]=='C') {
                    list[idx++].add(new Node(i,j,-1,5));
                }
            }
        }
        q.add(new Node(list[0].get(0).x,list[0].get(0).y,-1,5));
        bfs();
    }
    public static void bfs() {
        while(!q.isEmpty()) {
            Node a=  q.poll();
            if(a.x ==list[1].get(0).x && a.y == list[1].get(0).y) {
                System.out.println(a.cnt);
                break;
            }
            for(int i=0; i<4; i++) {
                int nx = a.x+dx[i];
                int ny = a.y+dy[i];
                if(nx>=0 && ny>=0 && nx<h && ny<w) {
                    if(!visited[nx][ny][i][a.d] && map[nx][ny]!='*') {
                        if(a.d == i) {
                            q.add(new Node(nx,ny,a.cnt,a.d));
                            visited[nx][ny][i][a.d] = true;
                        }
                        else {
                            q.add(new Node(nx,ny,a.cnt+1,i));
                            visited[nx][ny][i][a.d] = true;
                        }
                    }
                }
            }
        }
    }
}
class Node implements Comparable<Node>{
    int x,y,cnt,d;
    Node(int x ,int y, int cnt, int d){
        this.x=x;
        this.y=y;
        this.cnt = cnt;
        this.d=d;
    }
    public int compareTo(Node o) {
        return this.cnt-o.cnt;
    }
}