[Java] SWEA 수영대회 결승전

1. 문제분석

https://swexpertacademy.com/main/code/userProblem/userProblemDetail.do?contestProbId=AWKaG6_6AGQDFARV 

SW Expert Academy

출발점에서 도착점까지 수영해서 가는 것이다. 단 3가지 조건이 존재한다.

0: 움직이기 가능, 1: 장애물(접근 불가), 2: 소용돌이(2초 간격으로 움직이기 가능, 0초..1초..2초(가능))

 

최단경로를 찾는 것이니 BFS를 사용했다. 다만 위와 같은 조건에서 최단거리를 뽑기위해 조건을 준비했다.

1. 거리를 3으로 나눈 나머지가 2라면 소용돌이 통과가능

2. 거리를 3으로 나눈 나머지가 2가 아니면 소용돌이 불가능 -> 그 자리에서 대기.

위의 조건이면 구현하는데 문제가 없을 것이다.

 

문제를 보면 시간마다 움직이는 것이다.

이런 문제는 항상 큐에 있는 데이터를 전부 빼고(반복문) 일일이 델타탐색을 해야한다.

2. 구현

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

class Point {
    int x, y, dist;

    Point(int x, int y, int dist) {
        this.x = x;
        this.y = y;
        this.dist = dist;
    }

    Point clone(int x, int y, int dist) {
        return new Point(x, y, dist);
    }
}

public class Main {

    static int answer;
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {-1, 1, 0, 0};
    static int[][] map;
    static int size;
    static boolean[][] visited;
    static Point endPoint;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        StringTokenizer st;

        for (int c = 1; c <= tc; c++) {
            size = Integer.parseInt(br.readLine());
            map = new int[size][size];
            visited = new boolean[size][size];

            for (int i = 0; i < size; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < size; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            st = new StringTokenizer(br.readLine());
            int y = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            Point p = new Point(x, y, 0);

            st = new StringTokenizer(br.readLine());
            y = Integer.parseInt(st.nextToken());
            x = Integer.parseInt(st.nextToken());
            endPoint = new Point(x, y, 0);

            answer = bfs(p);
            System.out.println("#" + c + " " + answer);
        }
    }

    static int bfs(Point start) {
        Queue<Point> queue = new LinkedList<>();
        queue.offer(start);
        visited[start.y][start.x] = true;

        while (!queue.isEmpty()) {
            int queueSize = queue.size();
            for (int i = 0; i < queueSize; i++) {
                Point p = queue.poll();

                if (p.x == endPoint.x && p.y == endPoint.y) {
                    return p.dist;
                }

                for (int j = 0; j < 4; j++) {
                    int mx = p.x + dx[j];
                    int my = p.y + dy[j];
                    int move = p.dist + 1;

                    if (mx < 0 || my < 0 || mx >= size || my >= size) continue;
                    if (visited[my][mx] || map[my][mx] == 1) continue;
                    if (map[my][mx] == 2) {
                        if (p.dist % 3 != 2) {
                            queue.offer(p.clone(p.x, p.y, p.dist+1));
                        }else{
                            queue.offer(new Point(mx,my,move));
                            visited[my][mx] = true;
                        }
                        continue;
                    }
                    visited[my][mx] = true;
                    queue.offer(new Point(mx, my, move));
                }
            }
        }

        return -1;
    }
}

헷갈렸던 점은 도착점에 왔을 때였다.

필자는 도착점이여도 여러 곳에서 출발한 곳이 전부 와서 갱신을 하는 것을 생각했다.

하지만 암만해도 무한루프를 돌길래 바로 return 해주더니 답이 나왔다.

복잡하게 생각하지말고 시간마다 진행하는 것이니 경로를 찾았으면 바로 return 하는 것이 최단경로가 되는 것이다.

 

또한 Point 클래스에서 깊은 복사하는 코드를 간단하게 구현했다.

암만해도 dist값이 계속 중첩되서 나오길래 깊은 복사 코드를 구현했더니 dist가 정상적으로 나왔다.

3. 마무리

테케가 조금 빈약한 문제같다. 만약 소용돌이를 지나갈 수 있을 때 visited 처리를 안했는데도 통과라니..

이번엔 운이 좋았지만 주의해서 풀어보자