https://www.acmicpc.net/problem/19236
문제
아기 상어가 성장해 청소년 상어가 되었다.
4×4크기의 공간이 있고, 크기가 1×1인 정사각형 칸으로 나누어져 있다. 공간의 각 칸은 (x, y)와 같이 표현하며, x는 행의 번호, y는 열의 번호이다. 한 칸에는 물고기가 한 마리 존재한다. 각 물고기는 번호와 방향을 가지고 있다. 번호는 1보다 크거나 같고, 16보다 작거나 같은 자연수이며, 두 물고기가 같은 번호를 갖는 경우는 없다. 방향은 8가지 방향(상하좌우, 대각선) 중 하나이다.
오늘은 청소년 상어가 이 공간에 들어가 물고기를 먹으려고 한다. 청소년 상어는 (0, 0)에 있는 물고기를 먹고, (0, 0)에 들어가게 된다. 상어의 방향은 (0, 0)에 있던 물고기의 방향과 같다. 이후 물고기가 이동한다.
물고기는 번호가 작은 물고기부터 순서대로 이동한다. 물고기는 한 칸을 이동할 수 있고, 이동할 수 있는 칸은 빈 칸과 다른 물고기가 있는 칸, 이동할 수 없는 칸은 상어가 있거나, 공간의 경계를 넘는 칸이다. 각 물고기는 방향이 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전시킨다. 만약, 이동할 수 있는 칸이 없으면 이동을 하지 않는다. 그 외의 경우에는 그 칸으로 이동을 한다. 물고기가 다른 물고기가 있는 칸으로 이동할 때는 서로의 위치를 바꾸는 방식으로 이동한다.
물고기의 이동이 모두 끝나면 상어가 이동한다. 상어는 방향에 있는 칸으로 이동할 수 있는데, 한 번에 여러 개의 칸을 이동할 수 있다. 상어가 물고기가 있는 칸으로 이동했다면, 그 칸에 있는 물고기를 먹고, 그 물고기의 방향을 가지게 된다. 이동하는 중에 지나가는 칸에 있는 물고기는 먹지 않는다. 물고기가 없는 칸으로는 이동할 수 없다. 상어가 이동할 수 있는 칸이 없으면 공간에서 벗어나 집으로 간다. 상어가 이동한 후에는 다시 물고기가 이동하며, 이후 이 과정이 계속해서 반복된다.
...
상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 구해보자.
입력
첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 8보다 작거나 같은 자연수를 의미하고, 1부터 순서대로 ↑, ↖, ←, ↙, ↓, ↘, →, ↗ 를 의미한다.
출력
상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 출력한다.
방향을 지정하는 방법
- 방향의 경우, direction 을 x 와 y 로 각각 나누어서 저장하자.
static int[][] directions = { // ↑, ↖, ←, ↙, ↓, ↘, →, ↗
{-1, -1, 0, 1, 1, 1, 0, -1},
{0, -1, -1, -1, 0, 1, 1, 1},
};
static String[] directions_string =
{"↑", "↖", "←", "↙", "↓", "↘", "→", "↗"};
참고로, directions_string 배열은 내가 코딩하면서 직관적으로 논리를 펼칠 수 있게끔 출력하려고 만든거다. (문제에서 필요없다)
이런식으로 방향을 지정해놓으면, 다음과 같이 위치 변경을 이뤄낼 수 있다.
// 기존 Position 인 fishPos
// 이동한 Position 인 chgPos
// 기존 Position 인 fishPos 을 이용하여 특정 direction 으로 이동해보자.
int x = fishPos.x + directions[0][fish.dir];
int y = fishPos.y + directions[1][fish.dir];
Position chgPos = new Position(x, y);
물고기의 입력을 어떻게 저장할까?
먼저, 어떤 상태가 필요할까?
- 본인의 number
- 방향
그 다음으로 어떤 동작이 필요할까?
- 방향의 전환(반시계 방향으로 45도 회전)
- (추후 추가) 객체 간 깊은 복사를 위해서 static clone 메서드를 추가하였다.
물고기의 이동과 관련된 현재 위치는 어떻게 계산하지? (순차대로 이동해야 하므로)
1번 물고기부터 차례대로 어느 위치에 있는지 기록하는 순차 List<Fish> FishPos 가 필요하겠다.- `순차대로` 에 꽂혀서 List 라고 생각했는데, 다시 잘.. 생각해보니, Map<Integer, Position> fishPosMap 으로 저장해서, 특정 Fish 의 특정 num 으로 식별하고, 해당 num 의 Fish 의 Position 값을 가져오는게 나을 것 같아, 변경하였다.
물고기가 잡아먹히면 현재 위치도 사라지고, 존재하지 않는다는 것을 표현해야 한다.
현재 위치를 나타내는 리스트에 위치값을 -1로 변경한다던지의 방법도 있지만, 좀더 직관적이게 boolean list 인 isEaten 를 가져가도록 하자.- 라고 생각했는데.. 이것도 필요없어졌다. Map 으로 물고기의 존재 여부를 가져가게 되면, Map<Integer, Position> fishPosMap 에 없는 물고기는 먹혀 없는 물고기로 판별하면 된다.
// 물고기 객체
class Fish {
int num;
int dir;
public Fish(int num, int dir) {
this.num = num;
this.dir = dir;
}
public static Fish clone(Fish fish) {
return new Fish(fish.num, fish.dir);
}
public void rotate() {
this.dir = (this.dir + 1) % 8;
}
@Override
public String toString() {
return String.format("%02d", num) +"(" + dir +") ";
}
}
이제, 물고기 한마리가 이동하려고 한다고 해보자.
물고기를 회전하려면.. 어떤 상태 정보들이 바뀔까?
- Fish[][] map : 어떤 공간에 어떤 물고기가 있는지 판별하기 위한, 어항 맵
- Map<Integer, Position> fishPosMap : 특정 number 의 물고기가 어느 Position 에 있는지 판별하는 Map 이자, 특정 물고기가 잡아먹히면 이 Map 에서 사라진다.
- Fish fish : 현재 이동하려고 하는 물고기. 현재 물고기의 num(번호) 및 dir(방향) 정보가 담겨있다.
/**
* 이동 가능성이 보장되어 있는 Fish 에 대해서, 이동(swipe) 한다.
* @param map 각 공간에 어떤 특정 물고기가 배치되어 있는지 알 수 있는 2중 array (얕은 복사로 물고기 위치 변경)
* @param fishPosMap 각 물고기들이 num(번호)로 식별되어 살아있는지 확인하는 map (얕은 복사로 물고기의 Position 변경)
* @param fish 현재 이동하려는 물고기 (이동 가능성 보장)
*/
static void swipeFish(Fish[][] map, Map<Integer, Position> fishPosMap, Fish fish) {
Position fishPos = fishPosMap.get(fish.num);
int x = fishPos.x + directions[0][fish.dir];
int y = fishPos.y + directions[1][fish.dir];
Fish newFish = map[x][y] != null ?
new Fish(map[x][y].num, map[x][y].dir) : null;
Position newFishPos = new Position(x, y);
if (newFish == null) {
map[x][y] = Fish.clone(fish);
map[fishPos.x][fishPos.y] = null;
fishPosMap.put(fish.num, newFishPos);
}
else {
map[x][y] = Fish.clone(fish);
map[fishPos.x][fishPos.y] = Fish.clone(newFish);
fishPosMap.put(fish.num, newFishPos);
fishPosMap.put(newFish.num, fishPos);
}
}
기본적으로, Fish[][] map 과 Map<Interger, Position> fishPosMap 은 자료 구조이다. 이러한 자료 구조는 깊은 복사를 하지 않으면 얕은 복사가 되기때문에, 나는 이걸 역 이용할거다.
역 이용해서, 해당 swipeFish 메서드에서 두 객체의 내부 정보를 바꾸면, 이 메서드를 호출한 상위 메서드에서도 파라미터로 넣은 두 객체의 내부 정보가 바뀔 것이다.
-> 이 관련 정보는 Java의 객체 참조 방식과 call by value + reference semantics 를 검색해보자.
이제 상어의 정보는 어떻게 저장할까?
여기부턴 나중에 이뒤 내용부터는 검증이 안됏습니당... .. 고민중
물고기와 같이 Fish 객체로 구성해야할까? 물고기와 비슷하게, 방향의 전환을 할 수도 있는데 ...
상어에게 필요한 상태
- 현재 먹은 물고기들의 총합 number
- 물고기를 먹을 때마다 바뀌는 방향
- 현재 본인의 위치
아니면 위 세가지의 상태를 모두 넣은 Fish 객체를 만들고, 물고기와 상어를 모두 상태관리하는 것이다.
그러면 물고기의 경우, 현재 본인의 위치와 자신의 정보(number, direction) 등도 함께 저장해서 관리 가능하고,
순차리스트를 만들때도 Fish 자체를 저장해놓은 다음에, ArrayList 로 먹힐때마다 해당 Fish 객체를 사라지게 하면 되지 않을까???
그렇게 되면 원래 만드려고 했던 boolean 리스트인 isEaten 을 가져갈 필요도 없어진다.
물고기가 이동하는 것은 구현, 상어가 이동하는것은 DFS
이제 상어가 여러 물고기를 잡아먹을 수 있다는 사실에 주목해보자.
'코딩테스트' 카테고리의 다른 글
| [백준 16234] 인구 이동 (골드4) (1) | 2025.03.06 |
|---|---|
| [백준 7490] 0 만들기 (골드5) (0) | 2025.03.05 |
| [백준 22251] 빌런 호석 (골드5) (0) | 2025.01.26 |
| [백준 2668] 숫자고르기 (골드5) (0) | 2025.01.21 |
| [백준 7682] 틱택토 (골드5) (0) | 2025.01.18 |
