SWEA 4193 - 수영대회 결승전 [Java]

문제

SW Expert Academy

풀이

문제 제목에는 완전 탐색이 언급되어 있지만 BFS로 풀었다.

import java.util.*;

public class Solution {
    private static final Scanner sc = new Scanner(System.in);
    private static final int[] dx = {1, 0, -1, 0};
    private static final int[] dy = {0, 1, 0, -1};

    public static void main(String[] args) {
        int T = sc.nextInt();
        for (int tc = 1; tc <= T; tc++) {
            System.out.println("#" + tc + " " + solution());
        }
        sc.close();
    }

    private static int solution() {
        int N = sc.nextInt();
        int[][] arr = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                arr[i][j] = sc.nextInt();
            }
        }
        int A = sc.nextInt();
        int B = sc.nextInt();
        int C = sc.nextInt();
        int D = sc.nextInt();

        int answer = -1;
        Queue<Integer[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[N][N];
        queue.add(new Integer[]{A, B, 0});
        visited[A][B] = true;

        while(!queue.isEmpty()) {
            Integer[] cur = queue.poll();
            int x = cur[0], y = cur[1], t = cur[2];
            if (x == C && y == D) {
                answer = t;
                break;
            }
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (0 <= nx && nx < N && 0 <= ny && ny < N) {
                    if ((arr[nx][ny] == 0 || (arr[nx][ny] == 2 && t % 3 == 2)) && !visited[nx][ny]) {
                        visited[nx][ny] = true;
                        queue.add(new Integer[]{nx, ny, t+1});
                    }
                }
            }
            if (t % 3 != 2) {
                queue.add(new Integer[]{x, y, t+1});
            }
        }

        return answer;
    }
}

 

일반적인 BFS 풀이와 차이점을 꼽자면 다음과 같다.

• t % 3 == 2마다 소용돌이가 사라지므로 해당 조건에서는 2로 이동할 수 있음
• t % 3 != 2에서는 소용돌이가 사라질 때까지 대기하는 것이 최단 시간이 될 수 있으므로 visited[x][y] = true 여부와 관계 없이 queue에 해당 위치를 추가