[SWEA | Java] 4193번 수영대회 결승전 (완전 탐색 + 구현)

문제

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

SW Expert Academy

티어

소요 시간

21분

분류

bfs

코드

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

public class Solution {

    static public class Location {
        int y, x;
        int time;

        public Location(int y, int x, int time) {
            this.y = y;
            this.x = x;
            this.time = time;
        }
    }

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

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

        int t = Integer.parseInt(br.readLine());
        for (int test = 1; test <= t; test++) {
            int n = Integer.parseInt(br.readLine());
            int[][] 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(), " ");
            int a = Integer.parseInt(st.nextToken()), b = Integer.parseInt(st.nextToken());
            st = new StringTokenizer(br.readLine(), " ");
            int c = Integer.parseInt(st.nextToken()), d = Integer.parseInt(st.nextToken());

            System.out.println("#" + test + " " + move(n, a, b, c, d, map));
        }
    }

    private static int move(int n, int a, int b, int c, int d, int[][] map) {
        LinkedList<Location> queue = new LinkedList<>();
        queue.add(new Location(a, b, 0));
        boolean[][] visited = new boolean[n][n];

        while (!queue.isEmpty()) {
            Location poll = queue.poll();
            int y = poll.y;
            int x = poll.x;
            int time = poll.time;

            if (y == c && x == d) return time;

            for (int i = 0; i < 4; i++) {
                int nextY = y + dy[i];
                int nextX = x + dx[i];

                if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < n && !visited[nextY][nextX]) {
                    if (map[nextY][nextX] == 1) continue;
                    else if (map[nextY][nextX] == 2) {
                        if (time % 3 == 2) {
                            visited[nextY][nextX] = true;
                            queue.add(new Location(nextY, nextX, time + 1));
                        }
                        else {
                            visited[y][x] = true;
                            queue.add(new Location(y, x, time + 1));
                        }
                    }
                    else {
                        visited[nextY][nextX] = true;
                        queue.add(new Location(nextY, nextX, time + 1));
                    }
                }
            }
        }
        return -1;
    }
}

코드 설명

방문처리가 평소 bfs를 풀던 습관과 달라 생각할 부분이 있었다.

평소에는 nextX, nextY를 구하고 계산하기 전에 방문 검사를 했고, 방문을 하지 않았던 것이 확인되면 바로 방문처리를 했다.

그렇게 할 경우 소용돌이에 의해 멈춰서 있는 부분에서 검증이 제대로 되지 않게 된다. 

-> 이미 소용돌이에 의해 멈춰있는 곳은 방문이 처리가 되어 queue에 넣어도 방문했다고 하여 걸리게 됨

 

따라서 nextX, nextY를 방문 검사를 하고 해당 자리는 방문 검사를 하지 않는 방법을 사용했다.