[BOJ] 3709. 레이저빔은 어디로(DFS).java

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

최근까지 풀었던 시뮬레이션 문제 중에서는 그나마 간단한 문제인 것 같다.

동작은 

1. 레이저를 DFS로 쏜다.

2. 레이저가 나가면서 거울이 있는 좌표에 온다면 우측으로 레이저가 반사된다.

거울이 없다면 직진!

3. 레이저가 보드를 벗어나면 종료

* 레이저가 보드를 벗어나지 않을 경우를 예외처리해주는게 이 문제의 핵심(?)인 것 같다.

#. Code

처음 적용한 예외처리는 거울을 N * N 보다 많이 만났을 때 처리해주었다.

시뮬레이션을 해보았을 때 거울을 적어도 N * N 번 만나고 종료가 되었었다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer;   public class BOJ3709 {       static int N, R, resR, resC;     static boolean map[][];     static int[] dr = {-1, 0, 1, 0}, dc = {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 tc = 1; tc <= T; tc++) {             resR = 0;             resC = 0;                          st = new StringTokenizer(br.readLine());                      N = Integer.parseInt(st.nextToken());             R = Integer.parseInt(st.nextToken());             map = new boolean[N + 2][N + 2];               int a = 0, b = 0;             // 거울 배치             for (int i = 0; i < R; i++) {                 st = new StringTokenizer(br.readLine());                   a = Integer.parseInt(st.nextToken());                 b = Integer.parseInt(st.nextToken());                                  map[a][b] = true;              }             // 레이저 배치             st = new StringTokenizer(br.readLine());             a = Integer.parseInt(st.nextToken());             b = Integer.parseInt(st.nextToken());                          int dir = 0;             if(a == 0) dir = 2;             else if(a == N + 1) dir = 0;             else if(b == 0) dir = 1;             else if(b == N + 1) dir = 3;                           process(a, b, dir, 0);                          System.out.println(resR + " " + resC);         }       }       private static boolean process(int r, int c, int d, int cnt) {                           if(cnt > N * N ) return true;                  int rr = r + dr[d];         int cc = c + dc[d];         // 레이저가 보드를 벗어날 경우         if(rr < 1 || rr > N || cc < 1 || cc > N) {             resR = rr;             resC =cc;             return true;         }                  // 거울이 없을 경우         if(!map[rr][cc]) process(rr, cc, d, cnt);         // 거울이 있을 경우 오른쪽으로 각도를 변경         else process(rr, cc, (d + 1) % 4, cnt + 1);                  return false;     }   }   Colored by Color Scripter

cs

#. Code_v2

두 번째 방법은

거울이 있는 좌표을 방문했을 때, 어느 방향으로 왔는지 저장해두었다.

같은 방향으로 다시 그 좌표를 방문했다면 레이저는 보드를 벗어나지 않는 경우이다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer;   public class BOJ3709_v2 {       static int N, R, resR, resC, map[][];     static int[] dr = {-1, 0, 1, 0}, dc = {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 tc = 1; tc <= T; tc++) {             resR = 0;             resC = 0;                          st = new StringTokenizer(br.readLine());                      N = Integer.parseInt(st.nextToken());             R = Integer.parseInt(st.nextToken());             map = new int[N + 2][N + 2];               int a = 0, b = 0;             // 거울 배치             for (int i = 0; i < R; i++) {                 st = new StringTokenizer(br.readLine());                   a = Integer.parseInt(st.nextToken());                 b = Integer.parseInt(st.nextToken());                                  map[a][b] = 4;              }             // 레이저 배치             st = new StringTokenizer(br.readLine());             a = Integer.parseInt(st.nextToken());             b = Integer.parseInt(st.nextToken());                          int dir = 0;             if(a == 0) dir = 2;             else if(a == N + 1) dir = 0;             else if(b == 0) dir = 1;             else if(b == N + 1) dir = 3;                           process(a, b, dir);                          System.out.println(resR + " " + resC);         }       }       private static boolean process(int r, int c, int d) {                  // 다음 좌표         int rr = r + dr[d];         int cc = c + dc[d];         // 레이저가 보드를 벗어날 경우 종료         if(rr < 1 || rr > N || cc < 1 || cc > N) {             resR = rr;             resC =cc;             return true;         }                  // 거울이 없을 경우         if(map[rr][cc] == 0) {             if(process(rr, cc, d)) return true;         }         // 거울이 있을 경우 레이저는 우측으로 반사         else {             int nextDir = (d + 1) % 4;             // 이전에 같은 방향으로 온 적이 있다면 빔이 보드 밖을 벗어나지 않는 상황             if(map[rr][cc] == nextDir) return true;             map[rr][cc] = nextDir;                          if(process(rr, cc, (d + 1) % 4)) return true;;         }                  return false;     }   }   Colored by Color Scripter

cs