[SWEA/D3] SWEA 22683 나무 베기(Java)

문제 출처

SW Expert Academy

 

알고리즘 분류

• 시뮬레이션
• 그래프 탐색

 

풀이

중간에 나무를 만날 때마다 나무를 베고 지나간다.

우리는 매 칸을 방문할 때, 나무를 몇 번 더 벨 수 있는지, 그리고 어떤 방향에서 왔는지를 기록해줘야 한다.

그러기 위해, 방문하는 칸의 좌표와 나무를 벨 수 있는 횟수, 방향을 나타내는 4차원 배열을 선언한다.

이제 BFS를 해줘야 한다. 시작 방향은 위쪽이다.

직진을 하는 경우, 다음 칸이 범위 안에 존재해야 한다.

범위 안에 존재하는데 현재 칸이 나무인 경우, 나무를 벨 수 있는 횟수(K)가 1회 이상이라면 나무를 베고 지나간다. 이 때, 나무를 벨 수 있는 횟수가 K - 1이고, 현재 방향인 상태에서 다음 칸에 방문한 적이 없을 경우에만 나무를 베고 다음 칸에 방문할 수 있다.

현재 칸에 나무가 존재하지 않는 경우 나무를 벨 수 있는 횟수가 K이고, 현재 방향인 상태에서 다음 칸에 방문한 적이 없을 경우 다음 칸에 방문 가능하다.

왼쪽이나 오른쪽으로 90도 회전한 경우에는, 회전만 가능하다. 단, 해당 방향으로 이미 현재 칸에 방문한 기록이 존재하면 회전이 불가능하다.

이렇게 4차원 배열에 방문 기록을 하면서 BFS로 목표한 칸까지 도달한 경우의 최소 조작 횟수를 출력하고, 목표한 칸까지 도달할 수 없다면 -1을 출력한다.

 

코드

import java.io.*;
import java.util.*;
 
public class Solution {
     
    private static class Info {
         
        int Y, X, K, C, D;
         
        public Info(int Y, int X, int K, int C, int D) {
            super();
            this.Y = Y;
            this.X = X;
            this.K = K;
            this.C = C;
            this.D = D;
        }
         
    }
     
    private static int T, N, K;
    private static int[][] map = new int[11][11];
    private static boolean[][][][] visited = new boolean[11][11][6][4];
    private static int[] moveY = { -1,0,1,0 };
    private static int[] moveX = { 0,1,0,-1 };
    private static int startY, startX;
    private static StringBuilder sb = new StringBuilder();
     
    private static void init() {
        for (int i = 0; i < 11; i++) {
            for (int j = 0; j < 11; j++) {
                for (int k = 0; k < 6; k++) {
                    for (int d = 0; d < 4; d++) {
                        visited[i][j][k][d] = false;
                    }
                }
            }
        }
    }
     
    private static int bfs() {
        Queue<Info> queue = new LinkedList<>();
        visited[startY][startX][K][0] = true;
        queue.add(new Info(startY, startX, K, 0, 0));
         
        while (!queue.isEmpty()) {
            Info now = queue.poll();
            int nowY = now.Y;
            int nowX = now.X;
            int nowK = now.K;
            int nowC = now.C;
            int nowD = now.D;
             
            if (map[nowY][nowX] == 1) {
                return nowC;
            }
             
            for (int i = 0; i < 4; i++) {
                int nextY = nowY + moveY[i];
                int nextX = nowX + moveX[i];
                 
                // 1. 직진
                if (nowD == i) {
                    if ((nextY < 0) || (nextY >= N) || (nextX < 0) || (nextX >= N)) continue;
                    if (map[nextY][nextX] == -1) {
                        if (nowK > 0) {
                            if (!visited[nextY][nextX][nowK - 1][i]) {
                                visited[nextY][nextX][nowK - 1][i] = true;
                                queue.add(new Info(nextY, nextX, nowK - 1, nowC + 1, i));
                            }
                        }
                    }
                    else {
                        if (!visited[nextY][nextX][nowK][i]) {
                            visited[nextY][nextX][nowK][i] = true;
                            queue.add(new Info(nextY, nextX, nowK, nowC + 1,i));
                        }
                    }
                }
                 
                // 2. 오른쪽으로 90도 회전
                if ((nowD + 1) % 4 == i) {
                    if (!visited[nowY][nowX][nowK][i]) {
                        visited[nowY][nowX][nowK][i] = true;
                        queue.add(new Info(nowY, nowX, nowK, nowC + 1, i));
                    }
                }
                 
                // 3. 왼쪽으로 90도 회
                int nextD = nowD - 1;
                if (nextD < 0) {
                    nextD = 3;
                }
                if (nextD == i) {
                    if (!visited[nowY][nowX][nowK][i]) {
                        visited[nowY][nowX][nowK][i] = true;
                        queue.add(new Info(nowY, nowX, nowK, nowC + 1, i));
                    }
                }
            }
        }
         
        return -1;
    }
     
    private static void settings(int t) {
        sb.append("#" + t + " " + bfs() + "\n");
    }
     
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
         
        T = Integer.parseInt(br.readLine());
        for (int t = 1; t <= T; t++) {
            init();
            String[] inputs = br.readLine().split(" ");
            N = Integer.parseInt(inputs[0]);
            K = Integer.parseInt(inputs[1]);
            for (int i = 0; i < N; i++) {
                inputs = br.readLine().split("");
                for (int j = 0; j < N; j++) {
                    if ("G".equals(inputs[j])) {
                        map[i][j] = 0;
                    } else if ("T".equals(inputs[j])) {
                        map[i][j] = -1; 
                    } else if ("X".equals(inputs[j])) {
                        map[i][j] = 0;
                        startY = i;
                        startX = j;
                    } else if ("Y".equals(inputs[j])) {
                        map[i][j] = 1;
                    }
                }
            }
             
            settings(t);
        }
         
        bw.write(sb.toString());
        br.close();
        bw.close();
    }
 
}