[SWEA_4193] 수영대회 결승전 ( 완전 탐색 + 구현 ) (Java)

SW Expert Academy

 

✅ 문제 설명

NxN 크기의 공간이 있다. 이 공간에는 섬과 같은 지나갈 수 없는 장애물과, 주기적으로 사라졌다 나타나는 소용돌이 같은 장애물이 존재한다. (섬 - 1, 소용돌이 = 2, 나머지는 바다 = 0) 이때 소용돌이는 생성되고 2초동안 유지되다가 1초간 잠잠해진다. (0초에 생성된다. 0초,1초까지 유지되고 2초에 사라짐, 3,4초에 생성되고 5초에 사라짐.. 반복 + 한번 통과한 소용돌이 위에는 머물러 있을 수 있다.)

 

이런 조건 하에서 시작점 -> 도착점까지 도달할 수 있는 최단 시간을 찾으면 되는 문제였다. 

 

✅ 접근 방식

우선 시작점-> 도착점까지 최단 시간을 찾는 문제이므로, 최단 경로를 구할 때 자주 쓰이는 bfs를 이용해보자는 생각을 했다. 

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

public static int bfs(int y, int x, int d_y, int d_x) {
        visited[y][x] = 1;
        // int[] 배열을 저장하는 PriorityQueue 선언 (세 번째 요소를 기준으로 정렬)
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[2], b[2]));
        pq.offer(new int[]{y, x, 0});
        int answer = Integer.MAX_VALUE;

        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            y = current[0];
            x = current[1];
            int time = current[2];

            if (y == d_y && x == d_x) {
                answer = Math.min(answer, time);
            }

            for (int i = 0; i < dx.length; i++) { // 상하좌우에 대해서 작업 수행
                int ny = y + dy[i];
                int nx = x + dx[i];

                if (ny < 0 || ny >= N || nx < 0 || nx >= N) {
                    continue;
                }

                if (poolMap[ny][nx] != 1 && visited[ny][nx] == 0) {
                    if (poolMap[ny][nx] == 2) { // 소용돌이
                        visited[ny][nx] = 1;
                        int wait_time = (2 - time % 3);
                        pq.offer(new int[]{ny, nx, time + 1 + wait_time});
                    } else { // 지나갈 수 있는 곳
                        visited[ny][nx] = 1;
                        pq.offer(new int[]{ny, nx, time + 1});
                    }
                }
            }
        }

        if (answer == Integer.MAX_VALUE){ //도착할 수 없다면 -1을 출력
            return -1;
        }
        return answer;
    }

 

 

해당 코드를 자세히 설명해보자면,

public static int bfs(int y, int x, int d_y, int d_x) {
    visited[y][x] = 1;
    // int[] 배열을 저장하는 PriorityQueue 선언 (세 번째 요소를 기준으로 정렬)
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[2], b[2]));
    pq.offer(new int[]{y, x, 0});
    int answer = Integer.MAX_VALUE;

일단 시작점인 (y,x,0)를 큐에 넣어주고 (이때 0은 소요시간) visited[y][x]=1로 방문을 표시했다.

그리고 목적지까지 걸리는 시간을 기록할 answer는 Integer.MAX_VALUE로 초기화해두었다.

 

while (!pq.isEmpty()) {
            int[] current = pq.poll();
            y = current[0];
            x = current[1];
            int time = current[2];

 

그리고 큐가 빌때까지 bfs를 수행해주었다. 우선순위큐에서 하나를 뽑아와서 y,x,time에 값을 지정해주었다.

 

if (y == d_y && x == d_x) {
    answer = Math.min(answer, time);
}

만약 큐에서 뽑아온 y,x가 도착지점이라면 해당 y,x까지 걸린 시간인 time과 현재 answer에 저장되어있는 값과 비교해 더 작은 수를 정답으로 저장해주었다.

 

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

    if (ny < 0 || ny >= N || nx < 0 || nx >= N) {
        continue;
    }

    if (poolMap[ny][nx] != 1 && visited[ny][nx] == 0) {
        if (poolMap[ny][nx] == 2) { // 소용돌이
            visited[ny][nx] = 1;
            int wait_time = (2 - time % 3);
            pq.offer(new int[]{ny, nx, time + 1 + wait_time});
        } else { // 지나갈 수 있는 곳
            visited[ny][nx] = 1;
            pq.offer(new int[]{ny, nx, time + 1});
        }
    }
}

그리고, 가장 기본적인 작업을 해주었다.

큐에서 뽑아온 현재 좌표인 y,x의 위,아래,좌,우로 이동을 하는 작업을 해주었다.

즉, 다음으로 이동할 좌표인 ny, nx를 계산하는 작업을 해주었다.

 

이 부분을 좀 더 자세히 설명해보자면

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

ny, nx를 현재 좌표인 y,x에 각자 dy[i], dx[i]를 더한 값으로 생성해주었고

 

if (ny < 0 || ny >= N || nx < 0 || nx >= N) {
    continue;
}

ny,nx가 맵을 넘어가면 continue를 통해 넘겨주었다.

 

if (poolMap[ny][nx] != 1 && visited[ny][nx] == 0) {
    if (poolMap[ny][nx] == 2) { // 소용돌이
        visited[ny][nx] = 1;
        int wait_time = (2 - time % 3);
        pq.offer(new int[]{ny, nx, time + 1 + wait_time});
    } else { // 지나갈 수 있는 곳
        visited[ny][nx] = 1;
        pq.offer(new int[]{ny, nx, time + 1});
    }
}

범위가 올바른 좌표라면, 해당 좌표가 장애물인 1이 아닌지 그리고 이미 방문한 곳이 아닌지 확인해준다. -> 그래야 이동 가능하기 때문.

위 조건을 통과했다면 이동가능한 좌표로, 소용돌이거나 그냥 바다 라는 것이므로 

소용돌이라면 기다리는 시간을 계산해 큐에 (ny,nx, time+1+wait_time)으로 넣어주고

그냥 바다라면 바로 이동할 수 있으므로 큐에 (ny, nx, time+1)으로 넣어준다.

그리고 visited[ny][nx]=1로 방문했음을 표시해준다.

 

소용돌이를 기다리는 시간을 wait_time = (2 - time % 3); 이와 계산한 이유는 

소용돌이가 존재하는 시간이 2초, 없어지는 시간이 1초로 3초 주기로 생명주기가 있었기 때문에 time%3을 통해 현재 시간이 해당 주기 안으로 계산되도록 하였다. 즉 0,1,2안으로 다 변환되게 하였다.

2,5,7초에 소용돌이가 사라지고 이 시간에 이동할 수 있기 때문에 time%3= 0초일 경우는 2초 더 기다려야하고, time%3=1초일 경우에는 1초 더 기다려야하고 time%3=2초 일 경우에 0초 기다려야하는 걸 발견했다. 따라서 2-time%3이 소용돌이가 없어지길 기다리는 시간으로 정하고 문제를 풀이하였다.

 

이런 식으로 큐에 빌때까지 bfs를 수행해주었다.

 

✅ 코드 설명

이 문제의 핵심 코드인 bfs 안의 코드는 위에서 설명했으므로 이외의 코드만 설명하겠다.

class Solution {
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {-1, 1, 0, 0};
    static int[][] poolMap;
    static int[][] visited;
    static int N;

우선 기본적으로 상하좌우로 이동하기 위한 dx,dy배열과

맵의 정보 (0: 바다, 1: 섬=장애물, 2: 소용돌이)를 표시하기 위한 poolMap 배열

그리고 방문 여부를 기록할 visited 배열, 맵의 크기인 N을 선언해두었다.

 

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int T = sc.nextInt();
    List<Integer> answers = new ArrayList<>();

    for (int t = 0; t < T; t++) {
        N = sc.nextInt();
        poolMap = new int[N][N];
        visited = new int[N][N];

        for (int i = 0; i < N; i++) { // 맵 정보 입력받기
            for (int j = 0; j < N; j++) {
                poolMap[i][j] = sc.nextInt();
            }
        }

메인 함수에서는 맵 정보를 입력받아 poolMap에 값을 입력해주고

 

int A = sc.nextInt();
int B = sc.nextInt();
int C = sc.nextInt();
int D = sc.nextInt();

시작점 y,x좌표인 A,B와 도착점 y,x좌표인 C,D를 입력받아

 

int answer = bfs(A, B, C, D);
    answers.add(answer);
}

bfs함수에 인자로 넘겨 주었고, 답을 받아 answers 배열에 넣어주었다.

 

for (int i = 0; i < answers.size(); i++) {
        System.out.println("#" + (i + 1) + " " + answers.get(i));
    }

    sc.close();
}

모든 테스트 케이스가 마무리되면 기록해두었던 정답들을 모두 출력해준다.

 

✅ 최종 코드

import java.util.*;

class Solution {
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {-1, 1, 0, 0};
    static int[][] poolMap;
    static int[][] visited;
    static int N;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        List<Integer> answers = new ArrayList<>();

        for (int t = 0; t < T; t++) {
            N = sc.nextInt();
            poolMap = new int[N][N];
            visited = new int[N][N];

            for (int i = 0; i < N; i++) { // 맵 정보 입력받기
                for (int j = 0; j < N; j++) {
                    poolMap[i][j] = sc.nextInt();
                }
            }

            int A = sc.nextInt();
            int B = sc.nextInt();
            int C = sc.nextInt();
            int D = sc.nextInt();

            int answer = bfs(A, B, C, D);
            answers.add(answer);
        }

        for (int i = 0; i < answers.size(); i++) {
            System.out.println("#" + (i + 1) + " " + answers.get(i));
        }

        sc.close();
    }

    public static int bfs(int y, int x, int d_y, int d_x) {
        visited[y][x] = 1;
        // int[] 배열을 저장하는 PriorityQueue 선언 (세 번째 요소를 기준으로 정렬)
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[2], b[2]));
        pq.offer(new int[]{y, x, 0});
        int answer = Integer.MAX_VALUE;

        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            y = current[0];
            x = current[1];
            int time = current[2];

            if (y == d_y && x == d_x) {
                answer = Math.min(answer, time);
            }

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

                if (ny < 0 || ny >= N || nx < 0 || nx >= N) {
                    continue;
                }

                if (poolMap[ny][nx] != 1 && visited[ny][nx] == 0) {
                    if (poolMap[ny][nx] == 2) { // 소용돌이
                        visited[ny][nx] = 1;
                        int wait_time = (2 - time % 3);
                        pq.offer(new int[]{ny, nx, time + 1 + wait_time});
                    } else { // 지나갈 수 있는 곳
                        visited[ny][nx] = 1;
                        pq.offer(new int[]{ny, nx, time + 1});
                    }
                }
            }
        }

        if (answer == Integer.MAX_VALUE){ //도착할 수 없다면 -1을 출력
            return -1;
        }
        return answer;
    }
}

// 우선순위 큐 사용 => 15개의 테스트케이스 중 14개가 맞았습니다.

 

✅ 코멘트

- 처음엔 우선 순위큐를 쓰지 않고, 그냥 큐를 써서 문제를 풀었는데 그렇게 하게 되면 소용돌이를 통해 가는 루트가 time이 더 걸림에도 불구하고 단순 거리가 짧다는 이유로 특정 좌표에 먼저 방문하게 되고, 그렇게 되면 이후 time은 더 빠르지만 단순 거리가 길다는 이유로 늦게온 루트의 경우 해당 좌표가 이미 방문 되었으므로 방문하지 못하게 되는 문제가 발생했다.

- 따라서 우선 순위 큐를 사용해 소요시간순으로 오름차순 되게 하여 해당 문제를 해결할 수 있었다!!

 

- 이 문제를 해결했음에도 불구하고 15개의 테스트 케이스 중 14개가 맞았습니다. 라는 문구가 떴다..!

- 뭐가 문제일까 많은 고민을 했으나 알고보니 목적지까지 도달 못하는 케이스가 있었고, 해당 케이스의 경우 -1을 반환해주어야하는데 내가 이 케이스를 처리해두지 않았었다! 이 케이스를 처리하니 성공할 수 있었다.