[SWEA] 4193: 수영대회 결승전 (JAVA)

문제

SW Expert Academy

 

여담

진짜 바보인가? 왜 자꾸 중요한 조건을 놓쳐서 틀리는걸까 ㅎㅎ.... 풀이 방식 잘 생각해놓고 이렇게 어이없이 틀릴 때마다 답답..

 

제발 문제를 똑바로 다 읽고 정리하고 끝까지 확인하는 습관을 가지자!!!

 

풀이

N의 범위(2 ≤ N ≤ 15)도 크지 않기 때문에 완전탐색 방식으로 문제를 풀었다. (다른 풀이를 찾아보니 BFS 방식으로도 풀 수 있는 듯 하다. 이건 나중에..)

 

가장 고려해야 할 부분은 소용돌이 장애물이다. 소용돌이 장애물은 2초마다 나타나고 1초 사라지는 형식을 띄고 있다.

• 0초&1초: 나타남, 2초: 사라짐, 3초&4초: 나타남, 5초: 사라짐, ...

이를 0초가 아닌 1초부터 시작한다고 가정하면 3의 배수일 때마다 소용돌이 장애물이 사라지는 것이 된다.

• 1초&2초: 나타남, 3초: 사라짐, 4초&5초: 나타남, 6초: 사라짐, ...

 

이를 바탕으로 현재 n초일 때 소용돌이가 사라지기 전까지 기다려야 하는 시간의 식을 세우면 (n / 3 + 1) * 3 - n이다.

• n = 2
  • (2 / 3 + 1) * 3 - 2 = 3 - 2 = 1초 기다려야 함
• n = 4
  • (4 / 3 + 1) * 3 - 4 = 6 - 4 = 2초 기다려야 함

 

따라서 이를 바탕으로 완전 탐색을 수행하면 된다. 완전탐색을 수행하는 로직은 다음과 같다.

• 만약 도착지에 도착했다면, 값을 갱신하고 탐색을 종료하기
  • minDist = Math.min(minDist, dist - 1) (1초부터 시작했으니, 1을 빼고 비교해야 함)
• 만약 현재 minDist 값보다 dist 값이 크다면 탐색을 종료하기
  • 가장 빠른 길을 찾아야 하므로, 현재 찾은 빠른 길보다 길면 의미 없음
• 네 방향으로 이동하기
  • 범위를 벗어나거나 장애물이 있다면 해당 칸으로 이동하지 않기
  • 만약 소용돌이가 나타나는 위치이고, 현재 소용돌이가 있다면 기다리기(위의 식을 통해 얻은 값만큼)
  • 백트래킹을 위해 "방문 처리 → 재귀호출 → 방문 처리 취소"를 수행하기

 

자세한 내용은 코드를 참고하면 된다.

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Solution {
    static int N, A, B, C, D, minDist;
    static int[][] map;
    static boolean[][] visited;
    static final int INF = Integer.MAX_VALUE;
    static int[][] move = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int t = 1; t <= T; t++) {
            N = Integer.parseInt(br.readLine());
            map = new int[N][N];
            visited = new boolean[N][N];
            for (int i = 0; i < N; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine(), " ");
                for (int j = 0; j < N; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            A = Integer.parseInt(st.nextToken());
            B = Integer.parseInt(st.nextToken());
            st = new StringTokenizer(br.readLine(), " ");
            C = Integer.parseInt(st.nextToken());
            D = Integer.parseInt(st.nextToken());

            minDist = INF;
            dfs(1, A, B);
            if (minDist == INF) minDist = -1; // 도착할 수 없다면 -1 출력
            sb.append("#").append(t).append(" ").append(minDist).append("\n");
        }
        System.out.println(sb.toString());
    }

    static void dfs(int dist, int x, int y) {
        if (x == C && y == D) { // 도착지에 도착하면 탐색 종료
            minDist = Math.min(minDist, dist - 1);
            return;
        }
        // 기록된 최소 이동 시간보다 길면 탐색할 필요 없음
        if (minDist < dist) return;
        // 네 방향으로 이동하기
        for (int i = 0; i < 4; i++) {
            int nx = x + move[i][0];
            int ny = y + move[i][1];
            // 범위 벗어남 or 이미 방문 or 장애물이 있는 경우 탐색 X
            if (nx < 0 || ny < 0 || nx >= N || ny >= N || visited[nx][ny] || map[nx][ny] == 1) {
                continue;
            }
            // 문제 이해 잘못했음.. 가려고 하는 곳에 소용돌이가 있으면 없어질 때까지 기다리고 이동해야 함

            visited[nx][ny] = true;
            int time = 1;
            if (map[nx][ny] == 2 && dist % 3 != 0) { // 소용돌이가 사라지지 않았다면 사라질 때까지 기다려야 함
                time += (dist / 3 + 1) * 3 - dist;
            }
            dfs(dist + time, nx, ny);
            visited[nx][ny] = false;
        }
    }
}

---