[백준/골드5] 19950. 3차원 막대기 연결하기

문제

---

문제

3차원 좌표계에서 시작점과 끝점을 다양한 길이의 막대기로 연결하려고 한다.

막대기는 서로 간에 겹쳐질 수 있으며 시작점부터 시작하여 막대기를 하나씩 연결하여 끝점까지 연결한다.

안 쓰는 막대기 없이 주어진 막대기를 전부 사용해서 시작점부터 끝점까지 정확히 이을 수 있는지 확인하자.

막대기의 양끝은 항상 시작점, 끝점 혹은 다른 막대기의 끝과 이어져 있어야 하며 시작점 혹은 끝점에 두 개 이상의 막대기의 끝이 연결돼 있을 수 없다.

막대기의 두께는 무시할 수 있을 만큼 작아서 서로 겹쳐져 있는 것도 가능하다.

입력

첫 줄에 좌표계의 시작점(X1, Y1, Z1)과 끝점(X2, Y2, Z2)이 주어진다.

둘째 줄에 막대기의 개수 N이 주어진다.

셋째 줄부터 N개의 막대기의 길이를 의미하는 정수 K가 주어진다.

출력

시작점에서 끝점까지 막대기들을 사용해서 연결할 수 있으면 "YES", 불가능하면 "NO" 를 출력한다.

풀이

---

접근 방식

• 처음에 오류를 범했던 게 대각선으로 연결하는 것을 아예 생각을 안했었다.
• 조건 1
  • 모든 막대기 길이의 합이 시작점과 끝점의 길이보다 같거나 커야 한다.
  • 막대 총길이보다 더 길다면 어떻게든 대각선으로 연결하면 가능하다.

• 조건 2
  • (가장 긴 막대기의 길이)에서 (나머지 막대 길이의 합)을 빼면, 시작점과 끝점 사이 길이보다 작아야 한다.
  • 아래는 안되는 예시. 빨간색이 가장 긴 막대이고 파란색이 나머지 막대인 경우..

코드

---

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

//[골드1] 온풍기 안녕!
public class baekjoon_23289 {
    //1. 모든 온풍기에서 바람 나옴
    // 2. 온도가 조절됨
    // 3. 온도가 1 이상인 가장 바깥쪽 칸의 온도가 1씩 감소
    // 4. 초콜릿 하나 먹음
    // 5. 모든 칸의 온도가 K이상이 되었는지 검사, 모든칸의 온도가 K이상이면 테스트 중단. 아니면 1부터 다시 시작
    static int R, C, K;
    static int[][] map;
    static ArrayList<Heater> heaters;
    static ArrayList<Loc> checkList;
    static boolean[][][] walls;
    static int[][] visited;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken()); // 온도

        map = new int[R][C]; // 온도를 저장할 곳
        heaters = new ArrayList<>();
        checkList = new ArrayList<>();
        walls = new boolean[R][C][2]; // 0이면 가로 벽 , 1이면 세로 벽

        int choco = 0;

        for (int i = 0; i < R; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < C; j++) {
                int d = Integer.parseInt(st.nextToken());
                if (d == 0) continue;
                else if (d == 5) checkList.add(new Loc(i, j));
                else heaters.add(new Heater(i, j, d));
            }
        }

        int W = Integer.parseInt(br.readLine()); // 벽의 개수
        for (int i = 0; i < W; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken()) - 1;
            int y = Integer.parseInt(st.nextToken()) - 1;
            int w = Integer.parseInt(st.nextToken());

            if (w == 0) { // 가로 벽
                walls[x - 1][y][w] = true;
            } else { // 세로 벽
                walls[x][y][w] = true;
            }
        }

        while (true) {
            for (int k = 0; k < heaters.size(); k++) {
                Heater heater = heaters.get(k);
                int x = heater.x;
                int y = heater.y;
                int d = heater.d;
                visited = new int[R][C];
                switch (d) {
                    case 1:
                        if (y + 1 < C) {
                            visited[x][y + 1] = 5;
                            windAround(x, y + 1, d, 4);
                        }
                        break;
                    case 2:
                        if (y - 1 >= 0) {
                            visited[x][y - 1] += 5;
                            windAround(x, y - 1, d, 4);
                        }
                        break;
                    case 3:
                        if (x - 1 >= 0) {
                            visited[x - 1][y] += 5;
                            windAround(x - 1, y, d, 4);
                        }
                        break;
                    case 4:
                        if (x + 1 < R) {
                            visited[x + 1][y] += 5;
                            windAround(x + 1, y, d, 4);
                        }
                        break;
                    default:
                        break;
                }
                for (int i = 0; i < R; i++) {
                    for (int j = 0; j < C; j++) {
                        map[i][j] += visited[i][j];
                    }
                }
            }

//            for (int i = 0; i < R; i++) {
//                for (int j = 0; j < C; j++) {
//                    System.out.print(map[i][j] + " ");
//                }
//                System.out.println();
//            }

            // 온도 조절
            int[][] temp = new int[R][C];
            for (int i = 0; i < R; i++) {
                for (int j = 0; j < C; j++) {
                    for (int d = 0; d < 4; d++) {
                        int nx = i + dx[d];
                        int ny = j + dy[d];
                        if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue;

                        switch (d) {
                            case 0: // 상
                                if (walls[nx][ny][0]) break;
                                temp[i][j] += (-map[i][j] + map[nx][ny]) / 4;
                                break;
                            case 1: // 하
                                if (walls[i][j][0]) break;
                                temp[i][j] += (-map[i][j] + map[nx][ny]) / 4;
                                break;
                            case 2: // 좌
                                if (walls[nx][ny][1]) break;
                                temp[i][j] += (-map[i][j] + map[nx][ny]) / 4;
                                break;
                            case 3: // 우
                                if (walls[i][j][1]) break;
                                temp[i][j] += (-map[i][j] + map[nx][ny]) / 4;
                                break;
                        }
                    }
                }
            }

            for (int i = 0; i < R; i++) {
                for (int j = 0; j < C; j++) {
                    map[i][j] += temp[i][j];
                }
            }

//            System.out.println("온도 조절 후");
//            for (int i = 0; i < R; i++) {
//                for (int j = 0; j < C; j++) {
//                    System.out.print(map[i][j] + " ");
//                }
//                System.out.println();
//            }

            // 온도감소
            for (int j = 0; j <= C - 2; j++) {
                if (map[0][j] != 0) map[0][j]--;
            }
            for (int j = C - 1; j >= 1; j--) {
                if (map[R - 1][j] != 0) map[R - 1][j]--;
            }
            for (int i = 0; i <= R - 2; i++) {
                if (map[i][C - 1] != 0) map[i][C - 1]--;
            }
            for (int i = R - 1; i >= 1; i--) {
                if (map[i][0] != 0) map[i][0]--;
            }

//            System.out.println("온도 감소 후");
//            for (int i = 0; i < R; i++) {
//                for (int j = 0; j < C; j++) {
//                    System.out.print(map[i][j] + " ");
//                }
//                System.out.println();
//            }

            choco++;

            boolean flag = true;
            for (Loc check : checkList) {
                if (map[check.x][check.y] < K) {
                    flag = false;
                    break;
                }
            }

            if (flag) break;

            if (choco == 100){
                choco ++;
                break;
            }
        }

        System.out.print(choco);

    }

    private static void windAround(int x, int y, int d, int step) {
        if (step == 0) return;

        boolean[][] v = new boolean[R][C];
        switch (d) {
            case 1:
                if (y + 1 < C) {
                    if (x - 1 < 0) {
                    } else if (!walls[x - 1][y][1] && !walls[x - 1][y][0]) {
                        visited[x - 1][y + 1] = step;
                        v[x - 1][y + 1] = true;
                    }

                    if (!walls[x][y][1]) {
                        visited[x][y + 1] = step;
                        v[x][y + 1] = true;
                    }

                    if (x + 1 >= R) {
                    } else if (!walls[x][y][0] && !walls[x + 1][y][1]) {
                        visited[x + 1][y + 1] = step;
                        v[x + 1][y + 1] = true;
                    }

                    for (int i = -1; i <= 1; i++) {
                        if (x + i < 0 || x + i >= R || !v[x + i][y - 1]) continue;
                        windAround(x + i, y + 1, d, step - 1);
                    }
                }
                break;
            case 2:
                if (y - 1 >= 0) {
                    if (x - 1 < 0) {
                    } else if (!walls[x - 1][y - 1][1] && !walls[x - 1][y][0]) {
                        visited[x - 1][y - 1] = step;
                        v[x - 1][y - 1] = true;
                    }

                    if (!walls[x][y - 1][1]) {
                        visited[x][y - 1] = step;
                        v[x][y - 1] = true;
                    }

                    if (x + 1 >= R) {
                    } else if (!walls[x + 1][y - 1][1] && !walls[x][y][0]) {
                        visited[x + 1][y - 1] = step;
                        v[x + 1][y - 1] = true;
                    }

                    for (int i = -1; i <= 1; i++) {
                        if (x + i < 0 || x + i >= R || !v[x + i][y - 1]) continue;
                        windAround(x + i, y - 1, d, step - 1);
                    }
                }
                break;
            case 3:
                if (x - 1 >= 0) {
                    if (y - 1 < 0) {
                    } else if (!walls[x - 1][y - 1][0] && !walls[x][y - 1][1]) {
                        visited[x - 1][y - 1] = step;
                        v[x - 1][y - 1] = true;
                    }

                    if (!walls[x - 1][y][0]) {
                        visited[x - 1][y] = step;
                        v[x - 1][y] = true;
                    }

                    if (y + 1 >= C) {
                    } else if (!walls[x - 1][y + 1][0] && !walls[x][y][1]) {
                        visited[x - 1][y + 1] = step;
                        v[x - 1][y + 1] = true;
                    }

                    for (int i = -1; i <= 1; i++) {
                        if (y + i < 0 || y + i >= R || !v[x - 1][y + i]) continue;
                        windAround(x - 1, y + i, d, step - 1);
                    }
                }
                break;
            case 4:
                if (x + 1 < R) {
                    if (y - 1 < 0) {
                    } else if (!walls[x][y - 1][1] && !walls[x][y - 1][0]) {
                        visited[x + 1][y - 1] = step;
                        v[x + 1][y - 1] = true;
                    }

                    if (!walls[x][y][0]) {
                        visited[x + 1][y] = step;
                        v[x + 1][y] = true;
                    }

                    if (y + 1 >= C) {
                    } else if (!walls[x][y][1] && !walls[x][y + 1][0]) {
                        visited[x + 1][y + 1] = step;
                        v[x + 1][y + 1] = true;
                    }

                    for (int i = -1; i <= 1; i++) {
                        if (y + i < 0 || y + i >= R || !v[x + 1][y + i]) continue;
                        windAround(x + 1, y + i, d, step - 1);
                    }
                }
                break;
            default:
                break;
        }

    }

    private static class Heater {
        int x;
        int y;
        int d;

        public Heater(int x, int y, int d) {
            this.x = x;
            this.y = y;
            this.d = d;
        }
    }

    private static class Loc {
        int x;
        int y;

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

 

 

https://www.acmicpc.net/problem/19950

19950번: 3차원 막대기 연결하기