[Java] SWEA 탈주범 검거

1. 문제분석

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq 

SW Expert Academy

7가지의 파이프 모양을 가진 관에 탈주범이 들어갔다.

1시간에 1칸씩 움직일수 있고 주어진 시간이 지났을 때 탈주범이 어디에 있는지 경우의 수를 구하는 문제다.

 

보자마자 문제에서 BFS하라고 나타내고 있다. 또한 시간마다 어떤 상태인지 알아보는 것이니 모든 큐를 빼고 넣는 방식으로 구현했다.

여기서 볼 점은 파이프를 어떻게 관리하는 하는지다.

필자는 파이프를 종류별로 switch를 했는데 너무 별로였다. 딱 알고리즘 풀다가 이게 맞나? 싶을정도로.

 

검색해본 결과 다음과 같은 방법을 사용했다.

상하좌우를 인덱스 0, 1, 2, 3이라고 했을 때 각 파이프의 뚫린 곳을 1, 아닌 곳을 0으로 두자

    // 상하좌우
    static int[][] dirs = {
            {0, 0, 0, 0},
            {1, 1, 1, 1},
            {1, 1, 0, 0},
            {0, 0, 1, 1},
            {1, 0, 0, 1},
            {0, 1, 0, 1},
            {0, 1, 1, 0},
            {1, 0, 1, 0},
    };

    // 상하좌우
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {-1, 1, 0, 0};

다음과 같이 구현한 상태다

 

또한, 현재 내가 위로 올라갈려면 위의 파이프는 아래가 뚤려 있어야 한다.

예를 들어보자.

만약 이 파이프에서 시작해서 상하좌우를 움직인다고 하자.

그렇다면 왼쪽으로 간다고 할 때 어떤 파이프만 올 수 있을까?

4번과 5번 1번만 올 수 있다. 즉, 오른쪽이 뚫린 것만 가능한 것이다.

 

반면에 오른쪽으로 간다고 할 때는 어떤 파이프만 올 수 있을까?

6번, 7번, 1번만 올 수 있다. 즉, 왼쪽이 뚫린 것만 가능하다.

 

인덱스로 보자면 0 -> 1, 1 -> 0, 2 -> 3, 3 -> 2가 나와야 가능한 것이다.(위로 올라갈려면 아래가 뚫려야 함)

필자는 2로 나눠서 홀수면 1을 빼주고 짝수면 1을 더해줘서 구했다.

2. 구현

import java.util.*;
import java.io.*;


class Point {
    int x, y;

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

public class Solution {

    static int answer;
    static int width, height, m_width, m_height, time;
    static int[][] map;
    static boolean[][] visited;

    // 상하좌우
    static int[][] dirs = {
            {0, 0, 0, 0},
            {1, 1, 1, 1},
            {1, 1, 0, 0},
            {0, 0, 1, 1},
            {1, 0, 0, 1},
            {0, 1, 0, 1},
            {0, 1, 1, 0},
            {1, 0, 1, 0},
    };

    // 상하좌우
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {-1, 1, 0, 0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        for (int c = 1; c <= tc; c++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            height = Integer.parseInt(st.nextToken());
            width = Integer.parseInt(st.nextToken());
            m_height = Integer.parseInt(st.nextToken());
            m_width = Integer.parseInt(st.nextToken());
            time = Integer.parseInt(st.nextToken());

            map = new int[height][width];
            visited = new boolean[height][width];
            answer = 1;

            for (int i = 0; i < height; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < width; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            bfs();
            System.out.println("#" + c + " " + answer);
        }
    }

    static void bfs() {
        Queue<Point> queue = new LinkedList<>();
        queue.offer(new Point(m_width, m_height));
        visited[m_height][m_width] = true;

        for (int t = 1; t < time; t++) {
            int size = queue.size();
            // 시간 기준이니 모든 큐를 다 빼고 다시 넣고!
            for (int i = 0; i < size; i++) {
                Point p = queue.poll();
                int[] dir = dirs[map[p.y][p.x]];
                for (int j = 0; j < 4; j++) {
                    // 상하좌우로 돌아간다.
                    if (dir[j] == 0) continue;
                    int mx = p.x + dx[j];
                    int my = p.y + dy[j];

                    // 내꺼랑 연결이 가능한지? -> 상이면 하로 연결, 좌면 우로 연결
                    int pos = j % 2 == 0 ? j + 1 : j -1;

                    if (check(mx, my) && dirs[map[my][mx]][pos] == 1) {
                        visited[my][mx] = true;
                        queue.offer(new Point(mx, my));
                        answer++;
                    }
                }
            }
        }
    }

    static boolean check(int x, int y) {
        if (x < 0 || x >= width || y < 0 || y >= height) return false;
        if (visited[y][x] || map[y][x] == 0) return false;
        return true;
    }
}

check를 통해 인덱스와 방문여부, 0인지를 확인했다.

기존 BFS에서 시뮬레이션이 추가된 문제로 조금 더 생각해보면 풀 수 있을 것이다.

3. 마무리

BFS 응용까지는 알았다. 풀 수도 있는데 내 코드가 너무 더럽다..

그래서 아니 파이프 관리를 어떻게 깔끔하게 하지 하고 봤는데 저런.. 방법이 있더라..

아직 멀었나보다..