[BOJ] 17143. 낚시왕(시뮬레이션, 구현).java

#. Problem

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

* 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초 동안 일어나는 일을 구현하는 문제다.

1. 낚시왕이 오른쪽으로 한 칸 이동 (가장 오른쪽 칸으로 이동하면 종료)

2. 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡음. 상어를 잡으면 격자판에서 잡은 상어가 사라짐

3. 상어가 이동 

       => 상어가 이동을 마친 후 한 칸에 상어가 두 마리 이상 있을 경우 크기가 가장 큰 상어가 나머지 상어를 모두 잡아먹음

여기서 신경을 써주어야 할 "Point" !!

1. 상어가 이동을 마쳤을 때, 방향을 반대로 바뀐 상태로 있다면 바뀐 방향 정보를 상어가 가지고 있어야 한다.

방향 전환을 편하게 구현하기 위해 상(0), 좌(1), 우(2), 하(3) 순서대로 방향을 설정했는데

이렇게 설정한 이유는, 

상 -> 하, 로 방향을 바꿀 경우 3 - 0(상) = 3(하)

하 -> 상, 로 방향을 바꿀 경우 3 - 3(하) = 0(상)

좌 -> 우, 로 방향을 바꿀 경우 3 - 1(좌) = 2(우)

우 -> 좌, 로 방향을 바꿀 경우 3 - 2(우) = 1(좌)

2. 상어의 정보를 담은 map은 계속 초기화가 되어야 한다.

이전에 사용했던 map 정보를 계속 사용할 경우 아래와 같은 예외 상황이 발생

아직 이동하지 않은 A 상어가 (3, 3)에 있는데, 

B 상어가 (3, 3)으로 이동할 경우 A 상어가 이미 이동해있다고 착각을 해버려서 두 상어는 싸우게 된다.

A 상어는 아직 이동하지도 않았는데..

#. Code

상어의 이동을 매초 한 칸씩 이동해서 실행 시간이 오래 걸린 것 같다.

최대 상어 수 10000

최대 속력 1000

최대 열 100

중간중간 잡히거나 잡아먹힌 상어가 있어서 시간복잡도 계산은 어렵긴 하지만

열 마다 모든 상어가 최대 속력으로 이동하는데 한 칸씩 이동하면 시간이 꾀나 걸릴것 같긴 하다..

이동을 연산으로 한 번에 처리 개선이 필요하다 !

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 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer;   public class BOJ17143 {       static int R, C, M, map[][], king;     static Shark[] sharks;     static int[] dr = {-1, 0, 0, 1}, dc = {0, -1, 1, 0}; // 상, 좌, 우, 하          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()); // 가로         M = Integer.parseInt(st.nextToken()); // 상어의 수         map = new int[R + 1][C + 1];         sharks = new Shark[M + 1];                  for (int i = 1; i <= M; i++) {             st = new StringTokenizer(br.readLine());             int r = Integer.parseInt(st.nextToken());              int c = Integer.parseInt(st.nextToken());              int s = Integer.parseInt(st.nextToken()); // 속력             int d = Integer.parseInt(st.nextToken()); // 이동방향             int z = Integer.parseInt(st.nextToken()); // 크기             // 초기 방향 설정             if(d == 1) d = 0;             else if(d == 2) d = 3;             else if(d == 3) d = 2;             else d = 1;                          map[r][c] = i;             sharks[i] = new Shark(r, c, s, d, z);         }                  System.out.println(process());     }       private static int process() {                  int res = 0;                  // 1. 낚시왕이 오른쪽으로 한 칸 이동         while(king++ < C) {             // 2. 낚시왕이 상어를 잡는다.             res += fishing();                          // 3. 상어가 이동             move();         }                  return res;     }       private static void move() {                  map = new int[R + 1][C + 1];                  for (int i = 1; i <= M; i++) {             // 이미 잡힌 상어는 pass             if(sharks[i] == null) continue;                          Shark now = sharks[i];             int turn = 1, r = now.r, c = now.c;             for (int m = 0; m < now.s; m++) {                 r += turn * dr[now.d];                  c += turn * dc[now.d];                 // 범위를 벗어날 경우                 if(r < 1 || r > R || c < 1 || c > C) {                     // 방향을 반대로 하고                     turn *= -1;                     // 이전 칸으로 이동                     r += (turn * dr[now.d]) * 2;                      c += (turn * dc[now.d]) * 2;                 }             }                          // 상어의 방향이 바뀐 상태라면             if(turn == -1) {                 sharks[i].d = 3 - sharks[i].d;              }                          // 이동한 칸에 다른 상어가 있을 경우             if(map[r][c] > 0) {                 // 현재 상어보다 더 큰 상어일 경우 잡아먹힌다..                 if(sharks[map[r][c]].z > now.z) sharks[i] = null;                 // 현재 상어가 더 클 경우                 else {                     sharks[i].r = r;                     sharks[i].c = c;                     // 해당 칸에 있던 상어를 잡아먹자.                     sharks[map[r][c]] = null;                     map[r][c] = i;                 }             }             // 이동한 칸이 비었을 경우             else {                 sharks[i].r = r;                 sharks[i].c = c;                 map[r][c] = i;             }         }     }       private static int fishing() {           // 낚시왕이 있는 열에 있는 상어 중에서          for (int i = 1; i <= R; i++) {             // 땅과 제일 가까운 상어를 잡자.             if(map[i][king] > 0) {                 int size = sharks[map[i][king]].z;                  // 잡힌 상어의 정보는 삭제                 sharks[map[i][king]] = null;                 map[i][king] = 0;                                  return size;             }         }                  return 0;     }       static class Shark {         // 세로, 가로, 속력, 이동방향, 크기         int r, c, s, d, z;           public Shark(int r, int c, int s, int d, int z) {             this.r = r;             this.c = c;             this.s = s;             this.d = d;             this.z = z;         }              } }   Colored by Color Scripter

cs

#. Code_v2

상어의 이동을 연산으로