백준 6087 레이저 통신(JAVA)

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

6087번: 레이저 통신

 

알고리즘 분류: 그래프 이론, BFS

 

문제 설명

현재 진행하고있는 방향과 다음으로 가야하는 방향을 비교하여, 만약 방향이 다르면 cnt값을 1을 추가하고 방향을 바꿔주고, queue가 아닌 PriorityQueue를 사용하여 cnt가 작은 순으로 queue에 집어 넣어 가장 먼저 C에 도달하는 것이 가장 적은 cnt임의 방법을 생각했다. 여기서 문제가 있었던 것이 분명 visited를 안 한다면 메모리 초과가 나올 것인데,

방문 했던 곳을 또 방문할 수 있는 경우가 존재하여 visited를 어떻게 처리를 할지 고민을 하고 있었다.

고민 끝에 방문 했던 곳의 cnt가 만약 현재까지의 cnt보다 더 크다면 다시 방문할 수 있겠끔하면 되겠다 생각이 났다.

if(visited[nextx][nexty] <= now.cnt) continue;

if(now.vector != -1 && now.vector != i){
     visited[nextx][nexty] = now.cnt + 1;
     queue.add(new XY(nextx,nexty, now.cnt + 1,i));
}
else{
     visited[nextx][nexty] = now.cnt;
     queue.add(new XY(nextx,nexty,now.cnt,i));
}

이렇게 코드를 짰었지만 틀렸다.

여기서 바보같았던 것이 밑에는 now.cnt + 1과 now.cnt 이렇게 두개로 나눠서 했는데 위에선 now.cnt하나로만 처리를 했던 것이 문제였다.

이제 이부분을 

if(now.vector != -1 && now.vector != i){
     if(visited[nextx][nexty] >= now.cnt + 1) {
           visited[nextx][nexty] = now.cnt + 1;
           queue.add(new XY(nextx, nexty, now.cnt + 1, i));
     }
}
else{
       if(visited[nextx][nexty] >= now.cnt) {
           visited[nextx][nexty] = now.cnt;
           queue.add(new XY(nextx, nexty, now.cnt, i));
       }
}

이렇게 고쳐 AC를 받았다.

(수정)

전체 코드

import java.io.*;
import java.util.*;


public class Main {
    static class XY implements Comparable<XY>{
        int x;
        int y;
        int cnt;
        int vector;

        public XY(int x, int y, int cnt, int vector){
            this.x = x;
            this.y = y;
            this.cnt = cnt;
            this.vector = vector;
        }

        @Override
        public int compareTo(XY o) {
            return this.cnt - o.cnt;
        }
    }
    static int next_x[] = {1,-1,0,0};
    static int next_y[] = {0,0,1,-1};
    static int map[][];
    static int n;
    static int m;
    static int visited[][];
    static boolean isCheck[][][];
    static void BFS(XY start){
        PriorityQueue<XY> queue = new PriorityQueue<>();
        queue.add(start);
        visited[start.x][start.y] = 0;
        while (!queue.isEmpty()){
            XY now = queue.poll();
            if (map[now.x][now.y] == 2){
                System.out.println(now.cnt);
                break;
            }

            for(int i = 0;i<4;i++){
                int nextx = now.x + next_x[i];
                int nexty = now.y + next_y[i];

                if(nextx<0 || nextx>=n || nexty<0 || nexty>=m) continue;
                if(map[nextx][nexty] == 1) continue;

                if(now.vector != -1 && now.vector != i){
                    if(visited[nextx][nexty] >= now.cnt + 1) {
                        visited[nextx][nexty] = now.cnt + 1;
                        queue.add(new XY(nextx, nexty, now.cnt + 1, i));
                    }
                }
                else{
                    if(visited[nextx][nexty] >= now.cnt && (now.vector == -1  || !isCheck[nextx][nexty][now.cnt + i])) {
                        visited[nextx][nexty] = now.cnt;
                        isCheck[nextx][nexty][now.cnt + i] = true;
                        queue.add(new XY(nextx, nexty, now.cnt, i));
                    }
                }

            }
        }
    }
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());

        map = new int[n][m];
        visited = new int[n][m];
        isCheck = new boolean[n][m][n * m];
        XY start = null;
        for(int array[] : visited){
            Arrays.fill(array,Integer.MAX_VALUE);
        }
        boolean isCheck = false;
        for(int i = 0;i<n;i++){
            String s = br.readLine();
            for (int j = 0;j<m;j++){
                if(s.charAt(j) == 'C' && !isCheck){
                    isCheck = true;
                    start = new XY(i,j,0,-1);
                    map[i][j] = 0;
                }
                else if(s.charAt(j) == 'C' && isCheck){
                    map[i][j] = 2;
                }

                else if(s.charAt(j) == '*'){
                    map[i][j] = 1;
                }
                else{
                    map[i][j] = 0;
                }
            }
        }

        BFS(start);
    }
}