본문 바로가기
Algorithms/백준

[백준_23290]마법사 상어와 복제 with Java

by jeomn 2022. 1. 5.

백준(BOJ) 삼성 SW 역량 테스트 기출 문제 문제집: 마법사 상어와 복제(골드 1)

문제 출처: https://www.acmicpc.net/problem/23290

 

1. 알고리즘

상어 이동이 어려웠다....3중 for문으로 해결했는데, DFS같이 재귀로 풀었으면 더 코드가 복잡하지 않았을 것같다...!

  • 구현 / 브루트포스
  • ArrayList 이차원 배열로 격자판, Deque 이차원 배열로 냄새 표현
  • (물고기 복사 > 물고기 이동 > 상어 이동 > 냄새 없애기 > 복사 완료) 반복
    1
    2
    3
    4
    5
    6
    7
    for(int s=0; s<S; s++) {
        copyFish();
        moveFish();
        moveShark(s);
        removeSmell(s);
        completeCopy();
    }
    		 cs

     

  • 물고기 복사
    • 전체 격자(4*4)돌면서 격자에 있는 물고기 리스트 fishList에 복사
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      private static void copyFish() {
          fishList.clear();
          for(int r=0; r<4; r++) {
              for(int c=0; c<4; c++) {
                  for(int d:grid[r][c]) {
                      fishList.add(new Fish(r, c, d));
                  }
              }
          }
      }
      		 cs

       

  • 물고기 이동
    • 전체 격자(4*4)돌면서 8가지 방향을 탐색, 탐색 중 이동가능한 칸을 찾으면 이동
      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
      private static void moveFish() {
          ArrayList<Integer>[][] tempGrid = new ArrayList[4][4];
          for(int r=0; r<4; r++) {
                 for(int c=0; c<4; c++) {
                     tempGrid[r][c] = new ArrayList<Integer>();
                 }
             }
          
          for(int r=0; r<4; r++) {
              for(int c=0; c<4; c++) {
                  for(int d:grid[r][c]) {
                      int nr = r, nc = c;
                      
                      boolean isMoved = false; 
                      for(int i=0; i<8; i++) {
                          int nd = ((d-i)+8)%8;
                          nr = r+dx[nd];
                          nc = c+dy[nd];
                          
                          if(nr<0 || nr>=4 || nc<0 || nc>=4) continue;
                          if(smell[nr][nc].size()!=0) continue;
                          if(nr==shark.r && nc==shark.c) continue;
                          
                          tempGrid[nr][nc].add(nd);
                          isMoved = true;
                          break;
                      }
                      if(!isMoved) tempGrid[r][c].add(d);
                  }
              }
          }
          grid = tempGrid;        
      }
      		 cs

       

  • 상어 이동
    • 연속해서 3칸 이동 > 전체 경우의 수는 4방향*3칸 > 3중 for문
    • 이동 좌표 계산 후, 범위 체크
    • 첫번째 이동의 경우, 3번째 이동이 동일한 칸이 될 수 있으므로 물고기 카운팅을 위해 visited방문 처리
    • 마지막 이동에서 없앤 물고기 개수 비교
    • 가장 큰 경우로 상어 이동, 냄새 추가
      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
      private static void moveShark(int time) {
          int move = 0, maxMove=0;
          int fishNum = 0, maxFishNum = 0;
          int nr = shark.r, nc = shark.c;
          boolean isThree = false;
          
          boolean[][] visited;
          for(int i=1; i<5; i++) {
              visited = new boolean[4][4];
              
              nr+=dx[sd[i]];
              nc+=dy[sd[i]];
              if(nr<0 || nr>=4 || nc<0 || nc>=4) {
                  nr = shark.r;
                  nc = shark.c;
                  continue;
              }
              
              move = i;
              visited[nr][nc] = true;
              fishNum = grid[nr][nc].size();
              for(int j=1; j<5; j++) {
                  nr+=dx[sd[j]];
                  nc+=dy[sd[j]];
                  if(nr<0 || nr>=4 || nc<0 || nc>=4) {
                      nr-=dx[sd[j]];
                      nc-=dy[sd[j]];
                      continue;
                  }
                  
                  move = (move*10)+j;
                  if(!visited[nr][nc]) fishNum += grid[nr][nc].size();
                  for(int k=1; k<5; k++) {
                      nr+=dx[sd[k]];
                      nc+=dy[sd[k]];
                      if(nr<0 || nr>=4 || nc<0 || nc>=4) {
                          nr-=dx[sd[k]];
                          nc-=dy[sd[k]];
                          continue;
                      }
                      
                      if(!visited[nr][nc]) fishNum += grid[nr][nc].size();
                      int finalFishNum = fishNum;
                      if(!visited[nr][nc]) fishNum -= grid[nr][nc].size();
                      
                      nr-=dx[sd[k]];
                      nc-=dy[sd[k]];
                      
                      if(isThree && maxFishNum >= finalFishNum) continue;
                      move = (move*10)+k;
                      maxMove = move;
                      maxFishNum = finalFishNum;
                      isThree = true;
                      move /= 10;
                  }
                  
                  if(!visited[nr][nc]) fishNum -= grid[nr][nc].size();
                  visited[nr][nc] = false;
                  nr-=dx[sd[j]];
                  nc-=dy[sd[j]];
                  move /= 10;
              }
              
              visited[nr][nc] = false;
              nr = shark.r;
              nc = shark.c;
          }
          
          nr = shark.r;
          nc = shark.c;
          int idx=2;
          while(idx>=0) {
              int base = (int)Math.pow(10, idx--);
              int m = maxMove/base;
              maxMove %= base;
              
              nr+=dx[sd[m]];
              nc+=dy[sd[m]];
              
              if(grid[nr][nc].size()==0) continue;
              smell[nr][nc].add(time+2);
              grid[nr][nc].clear();
          }
          shark.r = nr;
          shark.c = nc;        
      }
      		 cs

       

  • 냄새 없애기
    • 전체 격자(4*4) 돌면서 현재 time과 냄새 칸의 냄새 비교
    • deque에 add로 붙여줬기 때문에, 자동으로 정렬되어 있음. 만약 사라지지 않는 냄새 확인 시 addFirst로 다시 맨 앞칸에 넣고 stop
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      private static void removeSmell(int time) {
          for(int r=0; r<4; r++) {
              for(int c=0; c<4; c++) {
                  while(!smell[r][c].isEmpty()) {
                      int s = smell[r][c].poll();
                      if(time-s < 0) {
                          smell[r][c].addFirst(s);
                          break;
                      }
                  }
              }
          }
      }
      		 cs

       

  • 복사 완료
    • 복사했던 fishList에 있는 Fish를 격자에 추가
      1
      2
      3
      4
      5
      private static void completeCopy() {
          for(Fish f:fishList) {
              grid[f.r][f.c].add(f.d);
          }
      }
      		 cs

       

  • 전체 격자(4*4)돌면서 물고기 개수 카운팅, 출력
    1
    2
    3
    4
    5
    6
    7
    8
    9
    private static int countFish() {
        int count = 0;
        for(int r=0; r<4; r++) {
            for(int c=0; c<4; c++) {
                count+=grid[r][c].size();
            }
        }
        return count;
    }
    		 cs

 

2. 유의 사항

 

3. 어려웠던 점, 해결 방법

  • 상어 이동 탐색 중 첫번째로 갔던 칸의 경우, 세번째 이동에서도 갈 수 있지만 물고기는 카운팅되지 않아야 한다는 부분이 코드로 구현할 때 문제가 있었음
    • visited 방문 처리로, 이미 방문했던 칸이면 물고기 개수 카운팅을 제외시킴

 

4. 소스 코드

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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;
 
public class Main {
    
    static int M, S;
    static Fish shark;
    static ArrayList<Integer>[][] grid;
    static Deque<Integer>[][] smell;
    static ArrayList<Fish> fishList;
    static int[] dx = {0, -1, -1, -1, 0, 1, 1, 1};
    static int[] dy = {-1, -1, 0, 1, 1, 1, 0, -1};
    static int[] sd = {-1, 2, 0, 6, 4};
    static class Fish{
        int r, c, d;
        Fish(int r, int c, int d){
            this.r = r;
            this.c = c;
            this.d = d;
        }
    }
    
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        M = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());
        
        grid = new ArrayList[4][4];
        smell = new LinkedList[4][4];
        for(int r=0; r<4; r++) {
            for(int c=0; c<4; c++) {
                grid[r][c] = new ArrayList<Integer>();
                smell[r][c] = new LinkedList<Integer>();
            }
        }
        
        for(int m=0; m<M; m++) {
            st = new StringTokenizer(br.readLine());
            int fx = Integer.parseInt(st.nextToken())-1;
            int fy = Integer.parseInt(st.nextToken())-1;
            int s = Integer.parseInt(st.nextToken())-1;
            
            grid[fx][fy].add(s);
        }
        
        st = new StringTokenizer(br.readLine());
        int sx = Integer.parseInt(st.nextToken())-1;
        int sy = Integer.parseInt(st.nextToken())-1;
        shark = new Fish(sx, sy, -1);
        
        fishList = new ArrayList<Fish>();
        for(int s=0; s<S; s++) {
            copyFish();
            moveFish();
            moveShark(s);
            removeSmell(s);
            completeCopy();
        }
        
        int result = countFish();
        System.out.println(result);
    }
 
    private static void copyFish() {
        fishList.clear();
        for(int r=0; r<4; r++) {
            for(int c=0; c<4; c++) {
                for(int d:grid[r][c]) {
                    fishList.add(new Fish(r, c, d));
                }
            }
        }
        
    }
 
    private static void moveFish() {
        ArrayList<Integer>[][] tempGrid = new ArrayList[4][4];
        for(int r=0; r<4; r++) {
            for(int c=0; c<4; c++) {
                tempGrid[r][c] = new ArrayList<Integer>();
            }
        }
        
        for(int r=0; r<4; r++) {
            for(int c=0; c<4; c++) {
                for(int d:grid[r][c]) {
                    int nr = r, nc = c;
                    
                    boolean isMoved = false; 
                    for(int i=0; i<8; i++) {
                        int nd = ((d-i)+8)%8;
                        nr = r+dx[nd];
                        nc = c+dy[nd];
                        
                        if(nr<0 || nr>=4 || nc<0 || nc>=4) continue;
                        if(smell[nr][nc].size()!=0) continue;
                        if(nr==shark.r && nc==shark.c) continue;
                        
                        tempGrid[nr][nc].add(nd);
                        isMoved = true;
                        break;
                    }
                    if(!isMoved) tempGrid[r][c].add(d);
                }
            }
        }
        grid = tempGrid;        
    }
 
    private static void moveShark(int time) {
        int move = 0, maxMove=0;
        int fishNum = 0, maxFishNum = 0;
        int nr = shark.r, nc = shark.c;
        boolean isThree = false;
        
        boolean[][] visited;
        for(int i=1; i<5; i++) {
            visited = new boolean[4][4];
            
            nr+=dx[sd[i]];
            nc+=dy[sd[i]];
            if(nr<0 || nr>=4 || nc<0 || nc>=4) {
                nr = shark.r;
                nc = shark.c;
                continue;
            }
            
            move = i;
            visited[nr][nc] = true;
            fishNum = grid[nr][nc].size();
            for(int j=1; j<5; j++) {
                nr+=dx[sd[j]];
                nc+=dy[sd[j]];
                if(nr<0 || nr>=4 || nc<0 || nc>=4) {
                    nr-=dx[sd[j]];
                    nc-=dy[sd[j]];
                    continue;
                }
                
                move = (move*10)+j;
                if(!visited[nr][nc]) fishNum += grid[nr][nc].size();
                for(int k=1; k<5; k++) {
                    nr+=dx[sd[k]];
                    nc+=dy[sd[k]];
                    if(nr<0 || nr>=4 || nc<0 || nc>=4) {
                        nr-=dx[sd[k]];
                        nc-=dy[sd[k]];
                        continue;
                    }
                    
                    if(!visited[nr][nc]) fishNum += grid[nr][nc].size();
                    int finalFishNum = fishNum;
                    if(!visited[nr][nc]) fishNum -= grid[nr][nc].size();
                    
                    nr-=dx[sd[k]];
                    nc-=dy[sd[k]];
                    
                    if(isThree && maxFishNum >= finalFishNum) continue;
                    move = (move*10)+k;
                    maxMove = move;
                    maxFishNum = finalFishNum;
                    isThree = true;
                    move /= 10;
                }
                
                if(!visited[nr][nc]) fishNum -= grid[nr][nc].size();
                visited[nr][nc] = false;
                nr-=dx[sd[j]];
                nc-=dy[sd[j]];
                move /= 10;
            }
            
            visited[nr][nc] = false;
            nr = shark.r;
            nc = shark.c;
        }
        
        nr = shark.r;
        nc = shark.c;
        int idx=2;
        while(idx>=0) {
            int base = (int)Math.pow(10, idx--);
            int m = maxMove/base;
            maxMove %= base;
            
            nr+=dx[sd[m]];
            nc+=dy[sd[m]];
            
            if(grid[nr][nc].size()==0) continue;
            smell[nr][nc].add(time+2);
            grid[nr][nc].clear();
        }
        shark.r = nr;
        shark.c = nc;        
    }
 
    private static void removeSmell(int time) {
        for(int r=0; r<4; r++) {
            for(int c=0; c<4; c++) {
                while(!smell[r][c].isEmpty()) {
                    int s = smell[r][c].poll();
                    if(time-s < 0) {
                        smell[r][c].addFirst(s);
                        break;
                    }
                }
            }
        }
    }
 
    private static void completeCopy() {
        for(Fish f:fishList) {
            grid[f.r][f.c].add(f.d);
        }
    }
    
    private static int countFish() {
        int count = 0;
        for(int r=0; r<4; r++) {
            for(int c=0; c<4; c++) {
                count+=grid[r][c].size();
            }
        }
        return count;
    }
}
 cs

 

5. 고민

  • 재귀로 풀어야 한다는 생각을 하기는 했는데...감이 잘 안와서 그냥 3중 for문을 사용했던 것같다...재귀도 연습해야지
저작자표시 비영리 변경금지

'Algorithms > 백준' 카테고리의 다른 글

[백준_23291] 어항 정리 with Java  (0) 2022.01.04
[백준_1463]1로 만들기 with Python, Java  (0) 2021.10.12
[백준_16236]아기 상어 with Python, Java  (0) 2021.08.26
[백준_4358]생태학 with Java  (0) 2021.08.04
[백준_12904]A와 B with Python  (0) 2021.06.30

관련글

댓글

티스토리툴바