[백준 java] 3197-백조의 호수

3197번: 백조의 호수

 

1. 백조를 이동킨다 (BFS) 

1-2. 두 백조가 만나면 while true

2. 빙하를 녹인다

 

우선 필드 크기와 필드의 모양을 입력받는다

입력을 마치면 for문으로 두마리 백조의 위치를 swan에 저장하고

만약 물이라면 meltQ에 추가시킨다 (얼음을 녹이기 위해)
( * 주의할점은 백조도 물로 취급하여 meltQ에 넣어줘야한다. (이것때문에 55%에서 계속 실패했다...)

 

move에서는 첫번째 백조만 움직이는 방법으로 두번째 백조가 만날때까지 BFS를 돌렸다.

만약 백조가 얼음이 아닌것을 만났다면 swanQ에 넣어준다

( * 주의할점. 처음에는 물을 만났을때만 swanQ에 넣어줘서 while문을 무한으로 돌려줬다 

 꼭 백조를 만났을때도 처리하자... )

 

private static boolean move() {
    Queue<Node> nextQ = new LinkedList<>();

    while(!swanQ.isEmpty()){
        Node temp = swanQ.remove();
        if( (temp.row == swan.get(2)) && (temp.col == swan.get(3))){
            return true;
        }

        for(int i=0; i<4; i++){
            int nr = temp.row+D[i][0];
            int nc = temp.col+D[i][1];

            if(nr<0||nr>=R||nc<0||nc>=C) continue;
            if(visited[nr][nc]) continue;

            visited[nr][nc]=true;
            if(Board[nr][nc]!='X'){
                swanQ.add(new Node(nr,nc));
            }else if (Board[nr][nc] == 'X') {
                nextQ.add(new Node(nr,nc));
            }
        }
    }
    swanQ = nextQ;
    return false;
}

만약 백조가 얼음을 만났다면 해당 위치를 nextQ에 저장한다

이렇게 안하고 매번 처음부터 백조를 이동시키면 시간초과가 뜬다 (엄청 많이떳다)

그래서 얼음을 만나면 해당 위치들을 저장해 다음날에 움직이면 그만큼 움직임을 줄일 수 있다.

(visited는 초기화시키지 않고 그대로라서 다음 장소만 탐색하기때문에)

swanQ가 빌때까지 while을 돌려서 while문이 끝났다면  swanQ에 아까 저장해둔 nextQ정보를 넘겨주자

 

 

private static void melt() {
    int size = meltQ.size();
    for(int f=0; f<size; f++) {
        Node temp = meltQ.remove();

        for(int i=0; i<4; i++){
            int nr = temp.row+D[i][0];
            int nc = temp.col+D[i][1];
            if(nr<0||nr>=R||nc<0||nc>=C) continue;

            if(Board[nr][nc] == 'X') {
                Board[nr][nc] = '.';
                meltQ.add(new Node(nr,nc));
            }
        }
    }
}

melt 에서는 물을 녹이는데 처음에 담아뒀던 크기만큼만 녹인다.(하루치)

그리고 녹일 얼음을 찾았다면 해당 얼음을 녹이고 ( X -> . 으로 변경)

해당 좌표를 다시 meltQ에 넣는다 (또 다음날 이 크기만큼 녹여줘야해서)

 

---

쉬운 문제인줄 알았는데 엄청난 시간초과가 날 반겨줬다

 

import java.util.*;

public class B3197 {
    static int R,C;
    static ArrayList<Integer> swan = new ArrayList<>();
    static char[][] Board;
    static boolean[][] visited;
    static Queue<Node> swanQ = new LinkedList<>();
    static Queue<Node> meltQ = new LinkedList<>();
    static int[][] D = {{-1,0},{1,0},{0,-1},{0,1}}; // 상하좌우

    static class Node{
        int row,col;
        Node(int r, int c){
            row = r;
            col = c;
        }
    }

    private static boolean move() {
        Queue<Node> nextQ = new LinkedList<>();

        while(!swanQ.isEmpty()){
            Node temp = swanQ.remove();
            if( (temp.row == swan.get(2)) && (temp.col == swan.get(3))){
                return true;
            }

            for(int i=0; i<4; i++){
                int nr = temp.row+D[i][0];
                int nc = temp.col+D[i][1];

                if(nr<0||nr>=R||nc<0||nc>=C) continue;
                if(visited[nr][nc]) continue;

                visited[nr][nc]=true;
                if(Board[nr][nc]!='X'){
                    swanQ.add(new Node(nr,nc));
                }else if (Board[nr][nc] == 'X') {
                    nextQ.add(new Node(nr,nc));
                }
            }
        }
        swanQ = nextQ;
        return false;
    }

    private static void melt() {
        int size = meltQ.size();
        for(int f=0; f<size; f++) {
            Node temp = meltQ.remove();

            for(int i=0; i<4; i++){
                int nr = temp.row+D[i][0];
                int nc = temp.col+D[i][1];
                if(nr<0||nr>=R||nc<0||nc>=C) continue;

                if(Board[nr][nc] == 'X') {
                    Board[nr][nc] = '.';
                    meltQ.add(new Node(nr,nc));
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        R = sc.nextInt();
        C = sc.nextInt();

        Board = new char[R][C];
        visited = new boolean[R][C];
        for(int i=0; i<R; i++){
            String str = sc.next();
            Board[i] = str.toCharArray();
        }

        for(int i=0; i<R; i++){
            for(int j=0; j<C; j++){
                if(Board[i][j]=='L'){
                    swan.add(i);
                    swan.add(j);
                    //백조가 있는곳도 물이기 때문에
                    meltQ.add(new Node(i,j));
                }

                if(Board[i][j]=='.'){
                    meltQ.add(new Node(i,j));
                }
            }
        }
        visited[swan.get(0)][swan.get(1)] = true;
        swanQ.add(new Node(swan.get(0),swan.get(1)));

        int day = 0;
        while (!move()) {
            melt();
            //녹는 상황 보려면
            /*
            for(int i=0; i<R; i++){
                for(int j=0; j<C; j++){
                    System.out.print(Board[i][j]);
                }
                System.out.println("");
            }

            System.out.println(" ");
            System.out.println(" ");

             */
            day++;
        }
        System.out.println(day);
    }
}