-
[BOJ - JAVA] 23290 - 마법사 상어와 복제 (삼성전자 기출, DFS, 시뮬레이션, 구현) 본문
# 주소
https://www.acmicpc.net/problem/23290
23290번: 마법사 상어와 복제
첫째 줄에 물고기의 수 M, 상어가 마법을 연습한 횟수 S가 주어진다. 둘째 줄부터 M개의 줄에는 물고기의 정보 fx, fy, d가 주어진다. (fx, fy)는 물고기의 위치를 의미하고, d는 방향을 의미한다. 방향
www.acmicpc.net
# 문제
# 문제 해설 및 코드 리뷰
import java.util.*;
class Shark{
int x;
int y;
int d;
Shark(int x, int y, int d){
this.x = x;
this.y = y;
this.d = d;
}
}
class Main{
static int m, s, sx, sy;
static int[][] arr = new int[4][4];
static int[][] dir = {{0, -1}, {-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}};
static int[][] dd = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
static List<Shark>[][] list = new List[4][4];
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
m = scan.nextInt();
s = scan.nextInt();
for(int i = 0; i < 4; i++)
for(int j = 0; j < 4; j++)
list[i][j] = new ArrayList<Shark>();
int id = 0;
for(int i = 0; i < m; i++) {
int x = scan.nextInt() - 1;
int y = scan.nextInt() - 1;
int d = scan.nextInt() - 1;
list[x][y].add(new Shark(x, y, d));
}
sx = scan.nextInt() - 1;
sy = scan.nextInt() - 1;
arr[sx][sy] = -1;
scan.close();
while(s--> 0) {
List<Shark>[][] temp = new List[4][4];
List<Shark>[][] clone = new List[4][4];
for(int i = 0; i < 4; i++)
for(int j = 0; j < 4; j++) {
clone[i][j] = new ArrayList<Shark>();
clone[i][j].addAll(list[i][j]);
}
for(int i = 0; i < 4; i++)
for(int j = 0; j < 4; j++)
temp[i][j] = new ArrayList<Shark>();
for(int i = 0; i < 4; i++) {
for(int j = 0; j < 4; j++) {
for(Shark now : list[i][j]) {
boolean isOk = false;
int nx = now.x + dir[now.d][0];
int ny = now.y + dir[now.d][1];
if(nx < 0 || ny < 0 || nx >= 4 || ny >= 4 || arr[nx][ny] == 2 || arr[nx][ny] == -1 || arr[nx][ny] == 1) {
int index = 0;
int d = now.d;
while(index < 8) {
int NX = now.x + dir[d][0];
int NY = now.y + dir[d][1];
if(NX < 0 || NY < 0 || NX >= 4 || NY >= 4 || arr[NX][NY] == 2 || arr[NX][NY] == -1 || arr[NX][NY] == 1) {
index++;
if(index == 8) {
isOk = true;
break;
}
d--;
if(d < 0)
d += 8;
}else {
temp[NX][NY].add(new Shark(NX, NY, d));
break;
}
}
}else
temp[nx][ny].add(new Shark(nx, ny, now.d));
if(isOk)
temp[now.x][now.y].add(new Shark(now.x, now.y, now.d));
}
}
}
for(int i = 0; i < 4; i++)
for(int j = 0; j < 4; j++) {
list[i][j] = new ArrayList<Shark>();
list[i][j].addAll(temp[i][j]);
}
String str = "";
int max = 0;
int nx1 = 0; int ny1 = 0; int nx2 = 0; int ny2 = 0; int nx3 = 0; int ny3 = 0;
for(int i = 0; i < 4; i++) {
nx1 = sx + dd[i][0];
ny1 = sy + dd[i][1];
if(nx1 < 0 || ny1 < 0 || nx1 >= 4 || ny1 >= 4) continue;
for(int j = 0; j < 4; j++) {
nx2 = nx1 + dd[j][0];
ny2 = ny1 + dd[j][1];
if(nx2 < 0 || ny2 < 0 || nx2 >= 4 || ny2 >= 4) continue;
for(int z = 0; z < 4; z++) {
nx3 = nx2 + dd[z][0];
ny3 = ny2 + dd[z][1];
if(nx3 < 0 || ny3 < 0 || nx3 >= 4 || ny3 >= 4) continue;
int count = list[nx1][ny1].size() + list[nx2][ny2].size() + list[nx3][ny3].size();
if(max < count) {
max = count;
str = "" + nx1 + ny1 + nx2 + ny2 + nx3 + ny3;
}
}
}
}
for(int i = 0; i < 4; i++)
for(int j = 0; j < 4; j++) {
if(arr[i][j] == 2)
arr[i][j] = 1;
else if(arr[i][j] == 1)
arr[i][j] = 0;
}
if(list[str.charAt(0) -'0'][str.charAt(1) - '0'].size() > 0)
arr[str.charAt(0) - '0'][str.charAt(1) - '0'] = 2;
if(list[str.charAt(2) - '0'][str.charAt(3) - '0'].size() > 0)
arr[str.charAt(2) - '0'][str.charAt(3) - '0'] = 2;
list[str.charAt(0) - '0'][str.charAt(1) - '0'] = new ArrayList<Shark>();
list[str.charAt(2) - '0'][str.charAt(3) - '0'] = new ArrayList<Shark>();
list[str.charAt(4) - '0'][str.charAt(5) - '0'] = new ArrayList<Shark>();
arr[str.charAt(4) - '0'][str.charAt(5) - '0'] = -1;
arr[sx][sy] = 0;
sx = str.charAt(4) - '0';
sy = str.charAt(5) - '0';
for(int i = 0; i < 4; i++)
for(int j = 0; j < 4; j++)
list[i][j].addAll(clone[i][j]);
}
int count = 0;
for(int i = 0; i < 4; i++)
for(int j = 0; j < 4; j++)
count += list[i][j].size();
System.out.println(count);
}
}이런 빡구현 문제는 정말 많이 풀어봐야 느는 것 같습니다.
저는 1솔만에 풀었지만, 테스트 케이스를 맞추기 위해 얼마나 많은 디버그를 했는지 모르겠네요.
어느새 블로그에 코테 리뷰만 계속 올라가고 있는데, 개발 에러를 자꾸 그때그때 고치다보니 블로그에 올릴 엄두가 안나는군요...
문제를 먼저, 어떻게 접근할지 알아보겠습니다.
# 문제 접근법
1. 물고기의 정보를 담기위해 각 인덱스마다 무수히 많은 상어의 정보를 담을 수 있는 list[][]를 사용합니다.
2. 4 x 4의 위치의 경우에 대한 모든 물고기들을 한 턴 이동시킵니다. 단, 물고기들이 얼마가 겹치든 상관없습니다.
3. 물고기는 상어, 물고기 냄새, 경계선 외부로는 못나갑니다.
4. 그 다음 상어가 이동을 하는데, 상어는 되도록이면 많은 물고기를 먹을 수 있는 방향으로 이동해야 합니다.
5. 이를 위해, 상,좌,하,우의 순서대로 가중치를 매기며 많은 물고기를 먹는 것이 1순위가 됩니다.
6. 여기서 주의해야할 점이, 상하상과 같은 방향으로 이동하면 비록 제자리이지만 물고기를 많이 잡아먹을 수가 있다면 가능하며, 이 때 중복해서 물고기를 잡아먹지 않도록 주의해야 합니다. (이 부분 때문에 5,6번 케이스에서 애먹었습니다.)
7. 잡아먹힌 물고기는 모두 쿨타임 2짜리의 가스를 남긴 뒤 제거됩니다. (제거하는 방법으로 모든 물고기를 탐색하는게 아니라, 해당 인덱스에 있는 물고기들을 초기화 합니다 따라서 list[2][2]를 초기화 하려면 list[2][2] = new ArrayList<>(); 이렇게 하면 시간을 절약할 수 있습니다. - list[][]를 쓰는 이유)
8. 상어는 이동하고 1번에서의 물고기 위치를 그대로 복사하여 다시 물고기를 생성합니다. (물고기는 계속해서 생성됩니다)
코드를 보며 이해해봅시다.
static int m, s, sx, sy;
static int[][] arr = new int[4][4];
static int[][] dir = {{0, -1}, {-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}};
static int[][] dd = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
static List<Shark>[][] list = new List[4][4];static 에서 사용할 변수는 다음과 같습니다. 4 x 4 의 어항이기 때문에 경우의 수를 생각하기 쉬웠습니다.
8가지 방향을 기본벡터 방향으로 가지고 있어야 하므로 대각선의 방향도 신경 써주셔야 하며, dir의 인덱스별로 방향은 시계방향입니다.
따라서 문제에서 물고기가 이동할 수 없을 때 반시계방향으로 이동한다고 설명되어 있으므로, dir의 인덱스는 감소하는 로직을 짜야합니다.
Scanner scan = new Scanner(System.in);
m = scan.nextInt();
s = scan.nextInt();
for(int i = 0; i < 4; i++)
for(int j = 0; j < 4; j++)
list[i][j] = new ArrayList<Shark>();
for(int i = 0; i < m; i++) {
int x = scan.nextInt() - 1;
int y = scan.nextInt() - 1;
int d = scan.nextInt() - 1;
list[x][y].add(new Shark(x, y, d));
}
sx = scan.nextInt() - 1;
sy = scan.nextInt() - 1;입력은 다음과 같습니다. x, y 인덱스에 d방향으로 이동할 물고기를 list[x][y]에 삽입합니다.
상어의 위치는 sx, sy에 담습니다.
while(s--> 0) {
List<Shark>[][] temp = new List[4][4];
List<Shark>[][] clone = new List[4][4];
for(int i = 0; i < 4; i++)
for(int j = 0; j < 4; j++) {
temp[i][j] = new ArrayList<Shark>();
clone[i][j] = new ArrayList<Shark>();
clone[i][j].addAll(list[i][j]);
}temp와 clone이 있는데, clone은 복제될 상어의 위치를 임시로 저장할 자료구조입니다.
"A를 임시로 저장하고 나중에 A를 복붙하고 싶은데, A가 데이터가 바뀔 것 같아. 어떡하면 좋을까?"
"B라는 자료구조를 만들고 A -> B를 복붙한 다음 A를 사용하고 A에 B를 다시 복붙하면 되겠네!" 이러한 원리로 다음 로직은 작동합니다.
temp는 list가 데이터가 변경되면서 인덱스가 겹칠 수 있어 사용하는 자료구조인데요.
예를 들어 "list[1][2]의 물고기가 list[3][4]로 이동한다면, 실컷 1행 2열의 물고기는 다 이동시켜놓고 3행 4열의 물고기들을 이동시킬 때 중복해서 이동할 수 있는" 사례가 발생할 수 있어, temp에 이동할 물고기를 모두 담고 다시 list에 옮기는 방식으로 풀었습니다. 더 나은 방법이 있는지는 모르겠다만 아직까지 이 것 때문에 틀린 문제는 없고 염려할 시간복잡도는 아닐 것 같아서 이런 풀이를 고수하고 있습니다. 더 좋은 방법은 알려주세요!
for(int i = 0; i < 4; i++) {
for(int j = 0; j < 4; j++) {
for(Shark now : list[i][j]) {
int nx = now.x + dir[now.d][0];
int ny = now.y + dir[now.d][1];
if(nx < 0 || ny < 0 || nx >= 4 || ny >= 4 || arr[nx][ny] == 2 || arr[nx][ny] == 1 || (sx == nx && sy == ny)) {
int index = 0;
int d = now.d;
while(index < 8) {
int NX = now.x + dir[d][0];
int NY = now.y + dir[d][1];
if(NX < 0 || NY < 0 || NX >= 4 || NY >= 4 || arr[NX][NY] == 2 || arr[NX][NY] == 1 || (sx == NX && sy == NY)) {
index++;
if(index == 8) {
temp[now.x][now.y].add(new Shark(now.x, now.y, now.d));
break;
}
d--;
if(d < 0)
d += 8;
}else {
temp[NX][NY].add(new Shark(NX, NY, d));
break;
}
}
}else
temp[nx][ny].add(new Shark(nx, ny, now.d));
}
}
}4 x 4의 모든 물고기들을 이동시킵니다.
원래의 방향대로 이동할 예정이던 물고기가 방문할 수 없어지면 while문으로 반시계방향 회전시켜 이동합니다.
만약 아무 곳으로도 이동할 수 없을 경우에 제자리에 있어야 하므로 temp에 원래의 인덱스, 방향을 삽입합니다.
이동이 가능하다면 새로운 인덱스와 방향을 list에 삽입합니다.
for(int i = 0; i < 4; i++)
for(int j = 0; j < 4; j++) {
list[i][j] = new ArrayList<Shark>();
list[i][j].addAll(temp[i][j]);
}이후 list를 초기화 하고 temp를 삽입합니다.
String str = "";
int max = Integer.MIN_VALUE;
int nx1 = 0; int ny1 = 0; int nx2 = 0; int ny2 = 0; int nx3 = 0; int ny3 = 0;
for(int i = 0; i < 4; i++) {
nx1 = sx + dd[i][0];
ny1 = sy + dd[i][1];
if(nx1 < 0 || ny1 < 0 || nx1 >= 4 || ny1 >= 4) continue;
for(int j = 0; j < 4; j++) {
nx2 = nx1 + dd[j][0];
ny2 = ny1 + dd[j][1];
if(nx2 < 0 || ny2 < 0 || nx2 >= 4 || ny2 >= 4) continue;
for(int z = 0; z < 4; z++) {
nx3 = nx2 + dd[z][0];
ny3 = ny2 + dd[z][1];
if(nx3 < 0 || ny3 < 0 || nx3 >= 4 || ny3 >= 4) continue;
int count = 0;
if(nx1 == nx3 && ny1 == ny3)
count = list[nx1][ny1].size() + list[nx2][ny2].size();
else
count = list[nx1][ny1].size() + list[nx2][ny2].size() + list[nx3][ny3].size();
if(max < count) {
max = count;
str = "" + nx1 + ny1 + nx2 + ny2 + nx3 + ny3;
}
}
}
}이후 상어가 연속해서 3번 이동하기 위한 인덱스를 nx1, ny1, nx2, ny2, nx3, ny3라고 순서대로 지정한 뒤 인덱스가 정해졌을 경우, 예상되는 물고기의 피사냥 수를 구해야 합니다.
이 때 반드시 주의해야할 점이 nx1과 nx3, ny1과 ny3이 같을 경우 즉, 처음 이동과 세번 째 이동이 같을 경우에는 count 수는 1, 2번째 이동만 더하고 아닐 경우엔 1, 2, 3번째 이동을 모두 더한다는 점이 특별한데요.
같은 위치에 또 재방문한다는 것은 물고기가 이미 제거되어 있는 상태이기 때문에 중복해서 제거하는 일은 없어야 하므로 주의하셔야 겠습니다.
구한 count값은 max와 비교하여 최댓값을 갱신한 후 str에 담습니다.
for(int i = 0; i < 4; i++)
for(int j = 0; j < 4; j++) {
if(arr[i][j] == 2)
arr[i][j] = 1;
else if(arr[i][j] == 1)
arr[i][j] = 0;
}
if(list[str.charAt(0) - '0'][str.charAt(1) - '0'].size() > 0)
arr[str.charAt(0) - '0'][str.charAt(1) - '0'] = 2;
if(list[str.charAt(2) - '0'][str.charAt(3) - '0'].size() > 0)
arr[str.charAt(2) - '0'][str.charAt(3) - '0'] = 2;
if(list[str.charAt(4) - '0'][str.charAt(5) - '0'].size() > 0)
arr[str.charAt(4) - '0'][str.charAt(5) - '0'] = 2;
list[str.charAt(0) - '0'][str.charAt(1) - '0'] = new ArrayList<Shark>();
list[str.charAt(2) - '0'][str.charAt(3) - '0'] = new ArrayList<Shark>();
list[str.charAt(4) - '0'][str.charAt(5) - '0'] = new ArrayList<Shark>();
sx = str.charAt(4) - '0';
sy = str.charAt(5) - '0';
for(int i = 0; i < 4; i++)
for(int j = 0; j < 4; j++)
list[i][j].addAll(clone[i][j]);이후엔 상어가 지나간 자리 모두엔 희생된 물고기의 가스 표식인 2를 남겨야 합니다.
이 때 또 주의하셔야할 점이 하나 있는데, 세 번째 위치인 상어가 현재 있는 위치에서도 물고기가 사냥될 때도 마찬가지로 물고기 가스를 남깁니다.
또한 물고기가 제거된 모든 인덱스에는 물고기가 한 마리도 없어야 겠습니다. 그러므로 list[][]들을 모두 초기화 합니다.
이것이 List<Shark> list를 쓰지 않고 List<Shark>[][]list를 쓰는 이유입니다. 인덱스별로 관리하기 굉장히 편합니다.
마지막으로 5번 조건에 따라 list에 아까 복사해두었던 clone을 붙여넣기 하고 s번 이 로직들을 총 반복합니다.
이후 list각 인덱스의 물고기를 모두 더하여 출력하면 그것이 정답이 되겠습니다.
감사합니다.
'백준 문제 풀이' 카테고리의 다른 글
| [BOJ - JAVA] 7579 - 앱 (DP, 배낭 문제) (0) | 2023.01.18 |
|---|---|
| [BOJ - JAVA] 17404 - RGB 거리 2 (다익스트라, DP) (1) | 2023.01.01 |
| [BOJ - JAVA] 16985 - Maaaaaaaaaze (구현, 그래프, 완전탐색, BFS) (1) | 2022.12.16 |
| [BOJ - JAVA] 12852 - 1로 만들기 2 (DP, 그래프) (0) | 2022.12.05 |
| [BOJ - JAVA] 16933 - 벽 부수고 이동하기 3 (BFS, 그래프) (0) | 2022.11.23 |
