BOJ) 백조의 호수

백조의 호수

3197번: 백조의 호수

 

풀이

 

처음 코테를 준비할 때 풀다가 실패한 문제였다. 그게 벌써 1년은 더 지난 것 같다.

1년간 매일같이 코테 연습을 하지는 않았지만, 실력이 많이 늘었을 거란 생각에 다시 도전했다.

하지만, 처참히 깨졌다... 

 

처음으로 짰던 코드는, 가지치기 없이 BFS를 날마다 돌리면서 답을 찾는 것이었다.

6%에서 시간초과가 떴고, 시간 초과를 회피할 오랫동안 생각하다가 떠오르지 않아서 여러 블로그를 참고했다.

Union-Find로 문제를 해결한 분들도 계셨고, BFS와 BinarySearch를 이용해 푸신 분들도 계셨다.

 

하지만, 두 코드 모두 유사한 문제에서 내가 접근할 수 있는 방법은 아닐 것 같다는 생각이 들었다.

결국 BFS로만 문제를 푸는 방법을 찾다가, 내가 고민했던 흔적이랑 최대한 비슷한 글들을 참고했다.

 

Visit 부분을 한번만 초기화하고 백조가 움직이는 LinkedList를 바꾸는 방법으로 코드를 수정했다.

처음 백조를 시작으로, 매 회마다 백조에서 움직일 수 있는 위치를 담아가면서 날짜와 연관되게 설정했다.

 

이 부분을 토대로 자잘한 부분들을 신경써주니까, 바로 통과가 되었다.

사실, 이 로직도 스쳐지나갔던 여러 고민 중 하나였다.

할까 말까 고민하기보다 우선 해보는 것도 나쁘지는 않은 것 같다.

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;

public class SwanLake_3197 {
    final static char SWAN = 'L', ICE = 'X', WATER = '.';
    final static int[] dx = {0,1,0,-1}, dy = {1,0,-1,0};
    final static int directions = 4;
    static int visit[][];
    static LinkedList<WaterPos> swanList;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String sizeStr = br.readLine();
        int y= Integer.parseInt(sizeStr.split(" ")[0]);
        char[][] map = new char[y][];

        for(int i=0; i<y; i++) {
            map[i] = br.readLine().toCharArray();
        }

        System.out.println(solution(map));

        br.close();
    }

    private static int solution(char[][] map) {
        int answer =0;
        int maxX = map[0].length;
        int maxY = map.length;

        visit = new int[maxY][maxX];
        LinkedList<WaterPos> waterList = new LinkedList<>();
        swanList = new LinkedList<>();
        WaterPos[] swans = new WaterPos[2];

        int idx=0;
        for(int y=0; y<maxY; y++) {
            for(int x=0; x<maxX; x++) {
                if(map[y][x] ==WATER || map[y][x] == SWAN) {
                    WaterPos pos = new WaterPos(x,y);
                    waterList.offer(pos);
                    if(map[y][x] == SWAN) {
                        swans[idx++] = pos;
                    }
                }
            }
        }
        swanList.offer(swans[0]);
        visit[swans[0].y][swans[0].x] =1;

        while(!isMeetSwans(swans,map)) {
            int size = waterList.size();
            for(int i=0; i<size; i++) {
                WaterPos pos = waterList.poll();
                for(int j=0; j<directions; j++) {
                    int ny = pos.y + dy[j];
                    int nx = pos.x + dx[j];

                    if(isInArea(nx,ny,maxX,maxY)) {
                        if(map[ny][nx] == ICE) {
                            map[ny][nx] = WATER;
                            waterList.offer(new WaterPos(nx,ny));
                        }
                    }
                }
            }
            answer++;
        }

        return answer;
    }

    private static boolean isMeetSwans(WaterPos[] swans, char[][] map) {
        boolean result = false;

        LinkedList<WaterPos> moveList = new LinkedList<>();
        int maxX = map[0].length;
        int maxY = map.length;

        while(!swanList.isEmpty()) {
            WaterPos pos = swanList.poll();
            if(pos.x == swans[1].x && pos.y == swans[1].y) {
                result = true;
                break;
            }
            for(int i=0; i<directions; i++) {
                int ny = pos.y + dy[i];
                int nx = pos.x + dx[i];
                if(isInArea(nx,ny,maxX,maxY)) {
                    if(visit[ny][nx] ==0) {
                        if(map[ny][nx] == ICE) {
                            moveList.offer(new WaterPos(nx,ny));
                        } else {
                            swanList.offer(new WaterPos(nx,ny));
                        }
                        visit[ny][nx] = 1;
                    }
                }
            }
        }

        if(visit[swans[1].y][swans[1].x] ==1) {
            result = true;
        }
        swanList = moveList;

        return result;
    }

    private static boolean isInArea(int x, int y, int maxX, int maxY) {
        return x>=0 && x<maxX && y>=0 && y<maxY ? true : false;
    }
}

class WaterPos {
    int x;
    int y;

    public WaterPos(int x, int y) {
        this.x = x;
        this.y =y;
    }
}