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

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

SW Expert Academy

---

문제 해석

삼성이는 수영대회 결승전에 진출했으며, 이번 대회는 N x N 크기의 제한된 바다 공간에서 열린다. 이 경기장은 섬과 같이 지나갈 수 없는 장애물(1로 표시)과 특정 주기로 사라졌다 나타나는 소용돌이(2로 표시)가 포함되어 있다. 소용돌이는 0초, 1초에 생성되고 2초에 사라진다가 3초, 4초에 다시 생성되는 패턴을 가진다. 이 문제에서는 삼성이가 가장 빠른 길을 찾아 결승점에 도달할 수 있는 시간을 계산하는 것이 목표다.

풀이 과정

경로 찾기와 시간 계산을 요구하는 BFS(너비 우선 탐색)를 이용해 해결할 수 있다. 경로 탐색을 위해 PriorityQueue를 사용하여 시간이 가장 적게 걸리는 경로를 우선적으로 탐색한다. 다음과 같은 단계로 문제를 해결한다:

1. 초기 위치에서 시작하여 우선 순위 큐에 추가한다.
2. 주변의 상, 하, 좌, 우 방향으로 가능한 이동 경로를 탐색한다.
3. 각 이동할 때마다 현재 시간을 고려하여 소용돌이가 있는 칸을 통과할 수 있는지 확인한다. 소용돌이가 있을 경우, 해당 시간에 통과 가능 여부를 판단하고, 통과 불가능 시 다음 가능 시간까지 기다려야 한다.
4. 결승점에 도달할 경우 그 시간을 반환하고, 모든 가능한 경로를 탐색했음에도 결승점에 도달하지 못하면 -1을 반환한다.

코드

package edu.ssafy.im.SWEA.D4.No4193;

import java.io.*;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Solution {
    private static int N; // 맵의 크기를 나타내는 N
    private static int[][] map; // 맵 정보를 저장하는 2차원 배열
    private static Point start, end; // 시작점과 종점을 나타내는 Point 객체
    private static boolean[][] v; // 방문 여부를 체크하는 2차원 배열
    private final static int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // 상하좌우 이동을 위한 방향 배열

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine()); // 테스트 케이스의 수 T
        for (int TC = 1; TC <= T; TC++) { // 각 테스트 케이스에 대해
            N = Integer.parseInt(br.readLine()); // 맵의 크기 N 입력
            map = new int[N][N]; // 맵 초기화
            for (int i = 0; i < N; i++) { // 맵 정보 입력
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < N; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            st = new StringTokenizer(br.readLine()); // 시작점 정보 입력
            start = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            st = new StringTokenizer(br.readLine()); // 종점 정보 입력
            end = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            sb.append("#").append(TC).append(" ").append(sol()).append("\n"); // 결과 문자열 생성
        }
        bw.write(sb.toString()); // 결과 문자열 출력
        bw.flush();
        bw.close();
    }

    private static int sol() {
        Queue<Point> pq = new PriorityQueue<>(); // 우선순위 큐를 사용하여 경로 탐색
        pq.offer(start); // 시작점을 큐에 추가

        v = new boolean[N][N]; // 방문 배열 초기화
        v[start.x][start.y] = true; // 시작점 방문 표시

        while (!pq.isEmpty()) { // 큐가 비어있지 않은 동안
            Point p = pq.poll(); // 우선순위가 가장 높은 요소(최소 시간)를 가져온다
            for (int[] d : direction) { // 모든 방향에 대해
                int nx = p.x + d[0]; // 새로운 x 좌표
                int ny = p.y + d[1]; // 새로운 y 좌표

                if (nx == end.x && ny == end.y) return p.c + 1; // 종점에 도달한 경우
                if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue; // 맵 범위를 벗어난 경우
                if (v[nx][ny] || map[nx][ny] == 1) continue; // 이미 방문했거나, 장애물이 있는 경우

                if (map[nx][ny] == 2 && p.c % 3 != 2) pq.offer(new Point(nx, ny, p.c + ((p.c % 3) == 0 ? 3 : 2))); // 소용돌이가 있고, 통과가 불가능한 시간인 경우
                else pq.offer(new Point(nx, ny, p.c + 1)); // 통과가 가능한 경우
                v[nx][ny] = true; // 방문 표시
            }
        }

        return -1; // 경로를 찾지 못한 경우
    }

    static class Point implements Comparable<Point> { // Point 클래스와 비교 기능 구현
        int x, y, c;

        public Point(int x, int y, int c) { // 생성자
            this.x = x;
            this.y = y;
            this.c = c;
        }

        public Point(int x, int y) { // 종점 생성자
            this.x = x;
            this.y = y;
        }

        @Override
        public int compareTo(Point o) { // 우선순위 큐를 위한 비교 메서드 구현
            return this.c - o.c; // 시간이 적은 순으로 정렬
        }
    }
}

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 각 노드(셀)에 대해 최대 4방향을 탐색하므로 O(N^2)이 된다. PriorityQueue를 사용하므로, 요소 삽입과 삭제에 대한 로그 시간 복잡도가 추가되어 O(N^2 log N)이 될 수 있다.

느낀점

완전 탐색과 구현을 함께 요구하는 복합적인 문제로, 다양한 상황에서의 조건 판단 능력을 키울 수 있는 좋은 기회였다. PriorityQueue를 사용하여 효율적인 경로 탐색을 구현하는 방법을 배울 수 있었다.