🔰 문제
💡 접근방식
구현 + 백트래킹 문제
여태까지 푼 마법사 상어 시리즈들과 비슷하게 객체의 ArrayList와 2차원 ArrayList 배열 2개를 이용하여 푸는 문제였다.
드문드문 풀어서인진 모르겠지만, 여태까지 풀었던 문제들 중 제일 실수를 많이 한 문제인 것 같다. 사소하게 신경 써줘야 할 부분들이 많았다.
- 물고기 복제 마법 시전
list의 내용을 다른 ArrayList에 복사 - 물고기 한 칸씩 이동
list 안의 x, y 좌표들 이동
상어 있는 칸, 물고기 냄새 있는 칸, 격자 범위 벗어나는 칸은 이동 X
이동 X일 경우 45도 반시계. 이동할 수 있는 칸 없으면 이동 X
while문을 이용하여 nx, ny 갱신. 갈 수 있는 곳이면 while문 탈출하고, 못 가는 곳이면 현재 방향 - 1 해줌(반시계 45도). 만약 8바퀴 돌아서 원래 방향으로 돌아오면 갈 수 있는 곳 없는 것이기에 while문 탈출. - 상어 3연속 이동 (물고기 제일 많이 먹는 칸으로 이동, 사전순으로 앞서는 경우)
백트래킹으로 구현.
이때 사전순 구현은 1~4까지의 중복순열을 만드는 방식으로 구현. - 2번 전 연습의 물고기 냄새 사라짐
smell이라는 2차원 배열을 만들어 상어가 지나간 자리에 3 저장하고, 상어가 마법 연습할 때마다 1씩 감소시키기 - 1번에서 시전한 복제 마법 완료. 1번의 위치, 방향 그대로 유지
1에서 copy해둔 ArrayList값을 map에 배치하기
💦 풀면서 실수, 놓친 점
이 문제는 드문드문 풀어서인지 사소한 실수가 많았다 ㅜㅜ
너무 많아서 다 쓰기가 부끄럽다... ㅋㅋㅋ
리스트 복사할 때 클래스 얕은 복사
마법사 상어가 1번에서 복제 마법을 시전하면 5번이 되어서야 적용된다. 그러므로 1번에서의 물고기들 상태를 저장해둘 필요가 있어서 배열 복사를 다음과 같이 하였다.
private static ArrayList<Fish> copy(ArrayList<Fish> list) {
ArrayList<Fish> tmp = new ArrayList<Fish>();
for (int i = 0; i < list.size(); i++) {
Fish cur = list.get(i);
tmp.add(cur);
}
return tmp;
}이렇게 하면 얕은 복사가 되어 만약 tmp 리스트에서 객체의 변경이 일어날 경우 원본 리스트에서도 함께 일어난다. 그렇기에 클래스에 Cloneable을 implements해줘야 한다.
static class Fish implements Cloneable {
int x;
int y;
int d;
public Fish(int x, int y, int d) {
this.x = x;
this.y = y;
this.d = d;
}
@Override
protected Fish clone() throws CloneNotSupportedException {
// TODO Auto-generated method stub
return (Fish) super.clone();
}
}
클래스에 cloneable을 implements하고 clone() 메소드를 오버라이딩한 뒤 이전에 구현한 copy 메소드를 다음과 같이 변경해준다.
private static ArrayList<Fish> copy(ArrayList<Fish> list) throws CloneNotSupportedException {
ArrayList<Fish> tmp = new ArrayList<Fish>();
for (int i = 0; i < list.size(); i++) {
Fish cur = list.get(i);
tmp.add(cur.clone());
}
return tmp;
}이동할 수 있는 칸 없으면 이동X
물고기 이동을 구현할 때 이동할 수 있는 방향이 나올 때까지 while문을 돌렸다. 그러다 보니 이동할 수 없는 경우, 무한루프에 빠지는 상황이 벌어졌다. 😱😱
그리하여 while문을 8번 돌리면 탈출하게 하였다.
처음에 코드 설계를 할 때 이런거까지 세세하게 짰어야 했는데...
백트래킹 구현
백트래킹 문제를 구현할 때 중복순열로 구현해야 하는데 실수로 순열로 구현해버려서 고생했다. 역시나 문제를 잘 읽고 설계를 잘하자 ㅎㅎ
물고기 냄새 위치
물고기 냄새를 남길 때 상어가 이동한 위치 중 물고기가 있는 자리에만 냄새를 남겨야 하는데 상어가 지나간 모든 자리에 남겨버렸다.
그래서 코드가 제대로 동작 안 했다.
초기화 실수
백트래킹할 때마다 해당 방향으로 가면 얻을 수 있는 fish의 개수를 세야 하는데 이거를 전역변수로만 초기화 하고 그 뒤론 안 해서 마법사 상어가 다음 마법을 시전할 때 문제가 생겼다. 당연하지만 초기화도 항상 신경쓰자!!!
좌표 실수
해당 문제는 좌표가 (1,1)~(4,4) 이다. 하지만 나는 구현할 때 (0,0)부터 하는 걸 편해하였기에 물고기의 위치를 입력받을 땐 r,c에 -1씩 해주었다. 하지만 상어 위치를 입력받을 때 안 해줬다.. 이런 좌표 실수도 조심하자.
상어 이동 - 상상하
보통 4방 탐색을 할 때 상, 상, 하 와 같이 이미 갔던 곳을 또 가는 경우는 거의 없다. 하지만 이 문제는 상, 상, 하와 같이 갔던 곳을 또 가는 경우도 있다! 하지만 주의해야 할 점이 갈 수는 있지만 물고기 수를 또 세면 안된다는 것이다.
그래서 평소 4방 탐색때 처럼 boolean visited 배열을 만들었다.
🕑 소요시간
2시간 30분
💻 풀이
import java.io.*;
import java.util.*;
// BOJ / G1 / 마법사 상어와 복제 / 50분 +
// https://www.acmicpc.net/problem/23290
public class Main_23290 {
static class Fish implements Cloneable {
int x;
int y;
int d;
public Fish(int x, int y, int d) {
this.x = x;
this.y = y;
this.d = d;
}
@Override
protected Fish clone() throws CloneNotSupportedException { // 클래스 복제
return (Fish) super.clone();
}
}
static int M, S;
static int fdx[] = { 0, 0, -1, -1, -1, 0, 1, 1, 1 }; // 물고기 이동
static int fdy[] = { 0, -1, -1, 0, 1, 1, 1, 0, -1 };
static int dx[] = { 0, -1, 0, 1, 0 }; // 상어 이동
static int dy[] = { 0, 0, -1, 0, 1 };
static ArrayList<Fish> map[][];
static ArrayList<Fish> list;
static int smell[][]; // 물고기 냄새
static int sx, sy; // 상어 위치
static int res; // 격자에 있는 물고기 수(정답)
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()); // 마법 시행 횟수
// 물고기 냄새
smell = new int[4][4];
// map 생성
map = new ArrayList[4][4];
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++)
map[i][j] = new ArrayList<Fish>();
}
list = new ArrayList<Fish>();
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int r = Integer.parseInt(st.nextToken()) - 1;
int c = Integer.parseInt(st.nextToken()) - 1;
int d = Integer.parseInt(st.nextToken());
list.add(new Fish(r, c, d));
}
// 상어 위치 입력
st = new StringTokenizer(br.readLine());
sx = Integer.parseInt(st.nextToken()) - 1;
sy = Integer.parseInt(st.nextToken()) - 1;
simulation();
System.out.println(res);
}
private static void simulation() throws CloneNotSupportedException {
for (int time = 0; time < S; time++) {
// 1. 물고기 복제 마법
ArrayList<Fish> copy = copy(list);
// 2. 물고기 이동
for (int i = 0; i < list.size(); i++) {
Fish cur = list.get(i);
cur = moveFish(cur);
}
// 2-1. 물고기 이동한 후 map에 배치
setMap();
// 3. 상어 연속 이동(백트래킹)
fishNum = Integer.MIN_VALUE; // 해당 방향으로 갈 때 먹는 물고기 수 초기화
sharkBacktracking(0); // 가장 많이 먹고, 사전순으로 적은 방향 찾기 by 중복순열
sharkMove();
// 4. 물고기 냄새 격자에서 사라짐
smellRemove();
// 5. 복제마법 map에 처리
setCopyMap(copy);
// 6. map에 있는 내용 list에 담기(물고기 개수도 세기)
reset();
}
}
private static void sharkMove() { // sharkBacktracking에서 얻은 최종 방향으로 이동하며 물고기 개수 줄이기 + 물고기 냄새 남기기
for (int i = 0; i < 3; i++) {
sx += dx[shkMove[i]];
sy += dy[shkMove[i]];
if (map[sx][sy].size() > 0) {
smell[sx][sy] = 3;
map[sx][sy].clear();
}
}
}
private static void reset() { // 다음 턴을 위해 map의 정보를 list에 저장하고, map 리셋
list.clear(); // 기존 list 클리어
int cnt = 0; // 물고기 개수
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
for (int k = 0; k < map[i][j].size(); k++) {
Fish cur = map[i][j].get(k);
list.add(cur);
cnt++;
}
map[i][j].clear();
}
}
res = cnt; // 정답 갱신
}
private static void setCopyMap(ArrayList<Fish> copy) { // 1번에서 시전한 복제마법 map에 적용시키기
for (int i = 0; i < copy.size(); i++) {
Fish cur = copy.get(i);
map[cur.x][cur.y].add(cur);
}
}
private static void smellRemove() { // 물고기 냄새 지우기
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (smell[i][j] > 0) // 냄새가 남아있을 경우
smell[i][j]--;
}
}
}
static int result[] = new int[3]; // 상어 이동 방향(임시)
static int shkMove[] = new int[3]; // 상어 이동 방향(최종)
static int fishNum = Integer.MIN_VALUE;
private static void sharkBacktracking(int idx) { // 상어 이동방향 정하기 by 중복순열
if (idx == 3) {
int fnum = checkFish(); // 해당 방향으로 상어가 이동했을 때 물고기 수
if(fnum==-1) // 못 가는 지역
return;
if (fishNum < fnum) {
fishNum = fnum;
for (int i = 0; i < 3; i++) {
shkMove[i] = result[i];
}
}
return;
}
for (int i = 1; i <= 4; i++) { // 1~4까지 중복순열
result[idx] = i;
sharkBacktracking(idx + 1);
}
}
private static int checkFish() { // sharkBacktracking에서 정한 방향으로 갔을 때 먹는 물고기 수
boolean visited[][] = new boolean[4][4];
int cnt = 0; // 물고기 수
int nx = sx, ny = sy;
for (int i = 0; i < 3; i++) {
nx += dx[result[i]];
ny += dy[result[i]];
if (nx < 0 || nx >= 4 || ny < 0 || ny >= 4) {
cnt = 0;
cnt = -1; // 범위 벗어남
break;
}
if (visited[nx][ny]) // 이미 방문한 지역이면 물고기 수 책정 x
continue;
cnt += map[nx][ny].size();
visited[nx][ny] = true;
}
return cnt;
}
private static void setMap() {
for (int i = 0; i < list.size(); i++) {
Fish cur = list.get(i);
map[cur.x][cur.y].add(cur);
}
}
private static Fish moveFish(Fish cur) {
int nx = 0, ny = 0;
int cnt = 0;
while (true) {
nx = cur.x + fdx[cur.d];
ny = cur.y + fdy[cur.d];
if (nx >= 0 && nx < 4 && ny >= 0 && ny < 4 && // 격자 안이고, 물고기 냄새 x이고, 상어 위치 아니면
smell[nx][ny] == 0 && !(nx == sx && ny == sy))
break;
cur.d = cur.d - 1; // 반시계 45도 회전
if (cur.d <= 0)
cur.d = 8;
cnt++;
if (cnt == 8) // 8바퀴 다 돌았을 경우 -> 갈 곳 x
break;
}
if (cnt < 8) {
cur.x = nx;
cur.y = ny;
}
return cur;
}
private static ArrayList<Fish> copy(ArrayList<Fish> list) throws CloneNotSupportedException { // 리스트 복사
ArrayList<Fish> tmp = new ArrayList<Fish>();
for (int i = 0; i < list.size(); i++) {
Fish cur = list.get(i);
tmp.add(cur.clone());
}
return tmp;
}
}
🌟 비슷한 유형의 문제들
❗ 풀어보면 좋은 문제들
참고
