[JAVA] 백준2151 거울 설치

문제 링크

---

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

2151번: 거울 설치

 

접근 및 시도 (생각의 흐름)

---

거울을 두 종류의 대각선 방향으로 설치 할 수 있다는 것 까지는 잘 생각했다.

/ 또는 \ 방향으로 거울을 설치하는 것이다.

 

그런데 생각이 여기서 더이상 발전하지 못했다.

단순하게 생각해서

90도로 반사된다고만 생각하면 되는데

더 복잡하게 생각했다.

즉 거울을 만나면 인접한 오른쪽, 아래쪽, 왼쪽, 위쪽 중에 하나로 반사되서 나간다고 단순하게 생각하면 되는 문제다.

본인은 순간 여러 방향으로 반사되서 나가지 않을까? 라고 복잡하게 생각하다가 막히게 됐었다.

 

사용 알고리즘

---

- BFS

- BFS로 인접한 there 노드들을 확인하되

   거울 설치 가능할 경우(!)

       : 90도 꺾인 인접 노드를 there 노드로 설정

         Queue에 push

   거울이 아닐 경우(아무것도 없을 경우)

       : here와 동일 방향으로 there 노드를 설정

         Queue에 push



 

풀이

---

이렇게 좌표 기반으로 2차원배열의 BFS 문제의 경우

Queue에서 poll된 노드를 now 정점으로 삼고

위, 오른쪽, 아래, 왼쪽의 인접 노드들을 조회하면서

문제를 푸는 경우가 많다.

 

 

 

거울 설치는 단순히 좌표 정보만을 가지고 문제를 풀 수 없다.

빛이 진행하는 방향을 고려해야 하기 때문이다.

따라서 빛의 진행방향을 고려한 3채원 배열이 필요하다.

 

 

 

방향은 아래와 같이 정의하고

0 : 오른쪽

1 : 아래쪽

2 : 왼쪽

3 : 위쪽

 

 

now가 (1, 3) 위치에서 아래 방향(1) 으로 빛이 진행하고 있다고 생각해 보자.

! 을 (2, 3)에서 만나면 거울을 설치 할 수 있다.

이때,

/ 거울을 설치하면 방향이 1 -> 2 (아래쪽 -> 왼쪽)

\ 거울을 설치하면 방향이 1 -> 0 (아래쪽 -> 오른쪽)

으로 바뀐다.

 

즉 there의 정보는 (2, 3) 이라는 위치 뿐만 아니라

방향 값도 알고 있어야 하고

 there 까지 오기까지 설치한 거울 개수를 이 배열에 저장해놔야 한다.

 

 

 

 

 

총평

---

언제 3차원 배열을 써야 하는지,

1차원 배열만으로 안될 땐 2차원을

2차원 배열만으로 안될 땐 3차원배열을 떠올려야 하겠다.

 

소스코드

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


public class Main {
    static int T;
    static int[] a;
    static boolean[] visited;
    static int[] dy = new int[]{0, -1, 0, 1};
    static int[] dx = new int[]{1, 0, -1, 0};

    static int NSize = 51;
    static int[][][] check = new int[NSize][NSize][4];
    static char[][] input = new char[NSize][NSize];
    static int N;
    static int startY, startX, endY, endX;
    static int min = Integer.MAX_VALUE;

    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(bf.readLine());

        N = Integer.parseInt(st.nextToken());
        for (int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(bf.readLine());
            String a = st.nextToken();
            input[i] = a.toCharArray();
        }

        //init check array.
        for (int i = 0 ; i < NSize ; i++) {
            for (int j = 0 ; j < NSize ; j++) {
                for (int k = 0 ; k < 4 ; k++) {
                    check[i][j][k] = Integer.MAX_VALUE;
                }
            }
        }

        boolean flag = false;
        for (int i = 0 ; i < N ; i++) {
            for (int j = 0 ; j < N ; j++) {
                if (input[i][j] == '#' && !flag) {
                    input[i][j] = '.';
                    startY = i;
                    startX = j;
                    flag = true;
                } else if (input[i][j] == '#' && flag) {
                    input[i][j] = '.';
                    endY = i;
                    endX = j;
                }
            }
        }

        bfs();
        System.out.println(min);
    }

    static void bfs() {
        Queue<Data> q = new LinkedList<>();

        for (int dir = 0 ; dir < 4 ; dir++) {
            q.add(new Data(startY, startX, dir, 0));
        }

        while(!q.isEmpty()) {
            Data current = q.poll();

            if (current.y == endY && current.x == endX) {
                if (min > current.count) min = current.count;
            }
            int thereY = current.y + dy[current.dir];
            //ex) current.dir방향이 '아래'였으면 1,0만큼 좌표가 움직여야 함.
            //    이 만큼 인접 정점으로 움직인 결과가 there임
            int thereX = current.x + dx[current.dir];
            int thereDir = current.dir;
            int thereCount = current.count;

            if (!isValid(thereY, thereX)) continue;

            if (input[thereY][thereX] == '!') {
                int dir = thereDir; // "/ 대각선"
                if (dir == 0) dir = 3;
                else if (dir == 1) dir = 2;
                else if (dir == 2) dir = 1;
                else if (dir == 3) dir = 0;
                if (check[thereY][thereX][dir] > thereCount + 1) {
                    check[thereY][thereX][dir] = thereCount + 1;
                    q.add(new Data(thereY, thereX, dir, thereCount + 1));

                }

                dir = thereDir;// "\ 대각선"
                if (dir == 0) dir = 1;
                else if (dir == 1) dir = 0;
                else if (dir == 2) dir = 3;
                else if (dir == 3) dir = 2;
                if (check[thereY][thereX][dir] > thereCount + 1) {
                    check[thereY][thereX][dir] = thereCount + 1;
                    q.add(new Data(thereY, thereX, dir, thereCount + 1));
                }
            }
                
            if (check[thereY][thereX][thereDir] > thereCount) {
                check[thereY][thereX][thereDir] = thereCount;
                q.add(new Data(thereY, thereX, thereDir, thereCount));
            }
        }
    }

    static class Data {
        int y, x, dir, count;

        Data(int y, int x, int dir, int count) {
            this.y = y;
            this.x = x;
            this.dir = dir;
            this.count = count;
        }
    }

    static boolean isValid(int y, int x) {
        if ((y >= 0 && y < N && x >= 0 && x < N) && input[y][x] != '*') return true;
        else return false;
    }
}