문제
아기 상어가 성장해 청소년 상어가 되었다.
4×4크기의 공간이 있고, 크기가 1×1인 정사각형 칸으로 나누어져 있다. 공간의 각 칸은 (x, y)와 같이 표현하며, x는 행의 번호, y는 열의 번호이다. 한 칸에는 물고기가 한 마리 존재한다. 각 물고기는 번호와 방향을 가지고 있다. 번호는 1보다 크거나 같고, 16보다 작거나 같은 자연수이며, 두 물고기가 같은 번호를 갖는 경우는 없다. 방향은 8가지 방향(상하좌우, 대각선) 중 하나이다.
오늘은 청소년 상어가 이 공간에 들어가 물고기를 먹으려고 한다. 청소년 상어는 (0, 0)에 있는 물고기를 먹고, (0, 0)에 들어가게 된다. 상어의 방향은 (0, 0)에 있던 물고기의 방향과 같다. 이후 물고기가 이동한다.
물고기는 번호가 작은 물고기부터 순서대로 이동한다. 물고기는 한 칸을 이동할 수 있고, 이동할 수 있는 칸은 빈 칸과 다른 물고기가 있는 칸, 이동할 수 없는 칸은 상어가 있거나, 공간의 경계를 넘는 칸이다. 각 물고기는 방향이 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전시킨다. 만약, 이동할 수 있는 칸이 없으면 이동을 하지 않는다. 그 외의 경우에는 그 칸으로 이동을 한다. 물고기가 다른 물고기가 있는 칸으로 이동할 때는 서로의 위치를 바꾸는 방식으로 이동한다.
물고기의 이동이 모두 끝나면 상어가 이동한다. 상어는 방향에 있는 칸으로 이동할 수 있는데, 한 번에 여러 개의 칸을 이동할 수 있다. 상어가 물고기가 있는 칸으로 이동했다면, 그 칸에 있는 물고기를 먹고, 그 물고기의 방향을 가지게 된다. 이동하는 중에 지나가는 칸에 있는 물고기는 먹지 않는다. 물고기가 없는 칸으로는 이동할 수 없다. 상어가 이동할 수 있는 칸이 없으면 공간에서 벗어나 집으로 간다. 상어가 이동한 후에는 다시 물고기가 이동하며, 이후 이 과정이 계속해서 반복된다.
<그림 1>
<그림 1>은 청소년 상어가 공간에 들어가기 전 초기 상태이다. 상어가 공간에 들어가면 (0, 0)에 있는 7번 물고기를 먹고, 상어의 방향은 ↘이 된다. <그림 2>는 상어가 들어간 직후의 상태를 나타낸다.
<그림 2>
이제 물고기가 이동해야 한다. 1번 물고기의 방향은 ↗이다. ↗ 방향에는 칸이 있고, 15번 물고기가 들어있다. 물고기가 있는 칸으로 이동할 때는 그 칸에 있는 물고기와 위치를 서로 바꿔야 한다. 따라서, 1번 물고기가 이동을 마치면 <그림 3>과 같아진다.
<그림 3>
2번 물고기의 방향은 ←인데, 그 방향에는 상어가 있으니 이동할 수 없다. 방향을 45도 반시계 회전을 하면 ↙가 되고, 이 칸에는 3번 물고기가 있다. 물고기가 있는 칸이니 서로 위치를 바꾸고, <그림 4>와 같아지게 된다.
<그림 4>
3번 물고기의 방향은 ↑이고, 존재하지 않는 칸이다. 45도 반시계 회전을 한 방향 ↖도 존재하지 않으니, 다시 회전을 한다. ← 방향에는 상어가 있으니 또 회전을 해야 한다. ↙ 방향에는 2번 물고기가 있으니 서로의 위치를 교환하면 된다. 이런 식으로 모든 물고기가 이동하면 <그림 5>와 같아진다.
<그림 5>
물고기가 모두 이동했으니 이제 상어가 이동할 순서이다. 상어의 방향은 ↘이고, 이동할 수 있는 칸은 12번 물고기가 있는 칸, 15번 물고기가 있는 칸, 8번 물고기가 있는 칸 중에 하나이다. 만약, 8번 물고기가 있는 칸으로 이동하면, <그림 6>과 같아지게 된다.
<그림 6>
상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 구해보자.
입력
첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 8보다 작거나 같은 자연수를 의미하고, 1부터 순서대로 ↑, ↖, ←, ↙, ↓, ↘, →, ↗ 를 의미한다.
출력
상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 출력한다.
풀이
스스로도 의문사항이 시뮬 진짜 좋아한다.. 시뮬 재미져... 시뮬 풀고나면 즐거워.. 노력한 보상 받는기분...
이 문제도
이 세가지로 이루어진 문제이다. 코드만 지금 300줄을 짰는데, 사실 이건 내가 노가다로 시뮬 풀기를 좋아해서...
먼저 전체 풀이 코드를 첨부한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
//↑, ↖, ←, ↙, ↓, ↘, →, ↗
// 1, 2, 3, 4, 5, 6, 7, 8
public class 청소년상어 {
static int sum = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int[][] fish = new int[4][4];
int[][] dir = new int[4][4];
for (int i = 0; i < 4; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < 4; j++) {
fish[i][j] = Integer.parseInt(st.nextToken());
dir[i][j] = Integer.parseInt(st.nextToken());
}
}
int si = 0, sj = 0;
sum = fish[si][sj];
fish[si][sj] = -1;
int sd = dir[si][sj];
dir[si][sj] = 0;
//moveFish(fish, dir);
eatFish(sum, si, sj, sd, fish, dir);
System.out.println(sum);
}
private static void eatFish(int s, int si, int sj, int sd, int[][] fish, int[][] dir) {
fish[si][sj] = -1;
dir[si][sj]= 0;
sum = s>sum?s:sum;
moveFish(fish, dir);
fish[si][sj] = 0;
switch (sd) {
case 1:
for(int i = si-1,j = sj; i>=0;i--) {
if(fish[i][j]>0) {
int [][]tempFish = new int[4][4];
int [][]tempDir = new int[4][4];
System.arraycopy(fish[0],0,tempFish[0],0,4);
System.arraycopy(fish[1],0,tempFish[1],0,4);
System.arraycopy(fish[2],0,tempFish[2],0,4);
System.arraycopy(fish[3],0,tempFish[3],0,4);
System.arraycopy(dir[0],0,tempDir[0],0,4);
System.arraycopy(dir[1],0,tempDir[1],0,4);
System.arraycopy(dir[2],0,tempDir[2],0,4);
System.arraycopy(dir[3],0,tempDir[3],0,4);
eatFish(s+fish[i][j],i,j, dir[i][j], tempFish, tempDir);
}
}
break;
case 2:
for(int i = si-1,j = sj-1;i>=0&& j>=0; i--,j--) {
if(fish[i][j]>0) {
int [][]tempFish = new int[4][4];
int [][]tempDir = new int[4][4];
System.arraycopy(fish[0],0,tempFish[0],0,4);
System.arraycopy(fish[1],0,tempFish[1],0,4);
System.arraycopy(fish[2],0,tempFish[2],0,4);
System.arraycopy(fish[3],0,tempFish[3],0,4);
System.arraycopy(dir[0],0,tempDir[0],0,4);
System.arraycopy(dir[1],0,tempDir[1],0,4);
System.arraycopy(dir[2],0,tempDir[2],0,4);
System.arraycopy(dir[3],0,tempDir[3],0,4);
eatFish(s+fish[i][j],i,j, dir[i][j], tempFish, tempDir);
}
}
break;
case 3:
for(int i = si,j = sj-1;j>=0;j--) {
if(fish[i][j]>0) {
int [][]tempFish = new int[4][4];
int [][]tempDir = new int[4][4];
System.arraycopy(fish[0],0,tempFish[0],0,4);
System.arraycopy(fish[1],0,tempFish[1],0,4);
System.arraycopy(fish[2],0,tempFish[2],0,4);
System.arraycopy(fish[3],0,tempFish[3],0,4);
System.arraycopy(dir[0],0,tempDir[0],0,4);
System.arraycopy(dir[1],0,tempDir[1],0,4);
System.arraycopy(dir[2],0,tempDir[2],0,4);
System.arraycopy(dir[3],0,tempDir[3],0,4);
eatFish(s+fish[i][j],i,j, dir[i][j], tempFish, tempDir);
}
}
break;
case 4:
for(int i = si+1,j = sj-1;i<4 &&j>=0;i++,j--) {
if(fish[i][j]>0) {
int [][]tempFish = new int[4][4];
int [][]tempDir = new int[4][4];
System.arraycopy(fish[0],0,tempFish[0],0,4);
System.arraycopy(fish[1],0,tempFish[1],0,4);
System.arraycopy(fish[2],0,tempFish[2],0,4);
System.arraycopy(fish[3],0,tempFish[3],0,4);
System.arraycopy(dir[0],0,tempDir[0],0,4);
System.arraycopy(dir[1],0,tempDir[1],0,4);
System.arraycopy(dir[2],0,tempDir[2],0,4);
System.arraycopy(dir[3],0,tempDir[3],0,4);
eatFish(s+fish[i][j],i,j, dir[i][j], tempFish, tempDir);
}
}
break;
case 5:
for(int i = si+1,j = sj;i<4;i++) {
if(fish[i][j]>0) {
int [][]tempFish = new int[4][4];
int [][]tempDir = new int[4][4];
System.arraycopy(fish[0],0,tempFish[0],0,4);
System.arraycopy(fish[1],0,tempFish[1],0,4);
System.arraycopy(fish[2],0,tempFish[2],0,4);
System.arraycopy(fish[3],0,tempFish[3],0,4);
System.arraycopy(dir[0],0,tempDir[0],0,4);
System.arraycopy(dir[1],0,tempDir[1],0,4);
System.arraycopy(dir[2],0,tempDir[2],0,4);
System.arraycopy(dir[3],0,tempDir[3],0,4);
eatFish(s+fish[i][j],i,j, dir[i][j], tempFish, tempDir);
}
}
break;
case 6:
for(int i = si+1,j = sj+1;i<4 && j<4;i++,j++) {
if(fish[i][j]>0) {
int [][]tempFish = new int[4][4];
int [][]tempDir = new int[4][4];
System.arraycopy(fish[0],0,tempFish[0],0,4);
System.arraycopy(fish[1],0,tempFish[1],0,4);
System.arraycopy(fish[2],0,tempFish[2],0,4);
System.arraycopy(fish[3],0,tempFish[3],0,4);
System.arraycopy(dir[0],0,tempDir[0],0,4);
System.arraycopy(dir[1],0,tempDir[1],0,4);
System.arraycopy(dir[2],0,tempDir[2],0,4);
System.arraycopy(dir[3],0,tempDir[3],0,4);
eatFish(s+fish[i][j],i,j, dir[i][j], tempFish, tempDir);
}
}
break;
case 7:
for(int i = si,j = sj+1;j<4;j++) {
if(fish[i][j]>0) {
int [][]tempFish = new int[4][4];
int [][]tempDir = new int[4][4];
System.arraycopy(fish[0],0,tempFish[0],0,4);
System.arraycopy(fish[1],0,tempFish[1],0,4);
System.arraycopy(fish[2],0,tempFish[2],0,4);
System.arraycopy(fish[3],0,tempFish[3],0,4);
System.arraycopy(dir[0],0,tempDir[0],0,4);
System.arraycopy(dir[1],0,tempDir[1],0,4);
System.arraycopy(dir[2],0,tempDir[2],0,4);
System.arraycopy(dir[3],0,tempDir[3],0,4);
eatFish(s+fish[i][j],i,j, dir[i][j], tempFish, tempDir);
}
}
break;
case 8:
for(int i = si-1,j = sj+1;i>=0 && j<4;i--,j++) {
if(fish[i][j]>0) {
int [][]tempFish = new int[4][4];
int [][]tempDir = new int[4][4];
System.arraycopy(fish[0],0,tempFish[0],0,4);
System.arraycopy(fish[1],0,tempFish[1],0,4);
System.arraycopy(fish[2],0,tempFish[2],0,4);
System.arraycopy(fish[3],0,tempFish[3],0,4);
System.arraycopy(dir[0],0,tempDir[0],0,4);
System.arraycopy(dir[1],0,tempDir[1],0,4);
System.arraycopy(dir[2],0,tempDir[2],0,4);
System.arraycopy(dir[3],0,tempDir[3],0,4);
eatFish(s+fish[i][j],i,j, dir[i][j], tempFish, tempDir);
}
}
break;
}
}
private static void moveFish(int[][] fish, int[][] dir) {
for (int f = 1; f < 17; f++) {
loop: for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (fish[i][j] == f) {
int d = dir[i][j];
do {
switch (d) {
case 1:
if (i != 0 && fish[i - 1][j] != -1) {
fish[i][j] = fish[i - 1][j];
dir[i][j] = dir[i - 1][j];
fish[i - 1][j] = f;
dir[i - 1][j] = d;
break loop;
} else {
d = 2;
if (d == dir[i][j])
break loop;
}
case 2:
if (i != 0 && j != 0 && fish[i - 1][j - 1] != -1) {
fish[i][j] = fish[i - 1][j - 1];
dir[i][j] = dir[i - 1][j - 1];
fish[i - 1][j - 1] = f;
dir[i - 1][j - 1] = d;
break loop;
} else {
d = 3;
if (d == dir[i][j])
break loop;
}
case 3:
if (j != 0 && fish[i][j - 1] != -1) {
fish[i][j] = fish[i][j - 1];
dir[i][j] = dir[i][j - 1];
fish[i][j - 1] = f;
dir[i][j - 1] = d;
break loop;
} else {
d = 4;
if (d == dir[i][j])
break loop;
}
case 4:
if (i != 3 && j != 0 && fish[i + 1][j - 1] != -1) {
fish[i][j] = fish[i + 1][j - 1];
dir[i][j] = dir[i + 1][j - 1];
fish[i + 1][j - 1] = f;
dir[i + 1][j - 1] = d;
break loop;
} else {
d = 5;
if (d == dir[i][j])
break loop;
}
case 5:
if (i != 3 && fish[i + 1][j] != -1) {
fish[i][j] = fish[i + 1][j];
dir[i][j] = dir[i + 1][j];
fish[i + 1][j] = f;
dir[i + 1][j] = d;
break loop;
} else {
d = 6;
if (d == dir[i][j])
break loop;
}
case 6:
if (i != 3 && j != 3 && fish[i + 1][j + 1] != -1) {
fish[i][j] = fish[i + 1][j + 1];
dir[i][j] = dir[i + 1][j + 1];
fish[i + 1][j + 1] = f;
dir[i + 1][j + 1] = d;
break loop;
} else {
d = 7;
if (d == dir[i][j])
break loop;
}
case 7:
if (j != 3 && fish[i][j + 1] != -1) {
fish[i][j] = fish[i][j + 1];
dir[i][j] = dir[i][j + 1];
fish[i][j + 1] = f;
dir[i][j + 1] = d;
break loop;
} else {
d = 8;
if (d == dir[i][j])
break loop;
}
case 8:
if (i != 0 && j != 3 && fish[i - 1][j + 1] != -1) {
fish[i][j] = fish[i - 1][j + 1];
dir[i][j] = dir[i - 1][j + 1];
fish[i - 1][j + 1] = f;
dir[i - 1][j + 1] = d;
break loop;
} else {
d = 1;
if (d == dir[i][j])
break loop;
}
}
} while (d != dir[i][j]);
break loop;
}
}
}
}
}
}
ㅂㅏ
상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 출력한다.
반복문 안쓰고 이렇게 여러번, swtich와 8줄 쓰기를 반복한 것을 보면 이 코드가 왜 300줄이나 되는지 알수 있게 된다...
먼저
- 4×4크기의 공간
- 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다.
- ai는 물고기의 번호, bi는 방향
- 방향 bi는 8보다 작거나 같은 자연수를 의미하고, 1부터 순서대로 ↑, ↖, ←, ↙, ↓, ↘, →, ↗ 를 의미한다.
를 입력으로 받아 주었다.
그럼 1번 예시를 보면
이렇게 두개의 배열이 생긴다.
이제 차근 차근 문제의 조건을 따라간다.
- 청소년 상어는 (0, 0)에 있는 물고기를 먹고, (0, 0)에 들어가게 된다.
그리고 eatFish함수를 통해서 물고기를 먹는 재귀함수를 실행한다, ( 사실 26,27,28은 중복이라 안써도 된다. )
- 청소년 상어는 (0, 0)에 있는 물고기를 먹고, (0, 0)에 들어가게 된다. 상어의 방향은 (0, 0)에 있던 물고기의 방향과 같다.
- 이후 물고기가 이동한다. -> moveFish
moveFish함수를 살펴보면, 1=>16번까지를 찾으면서 교환이나 역할이 끝나면, loop:를 나오게되는 형식이다.
방향이 변했는데, 기존의 값과 동일하면 이후 break loop를 통해 : 만약, 이동할 수 있는 칸이 없으면 이동을 하지 않는다. 를 수행한다.
if (i=0 & fish[i-1][j]!=-1)을 통해 | 칸, 이동할 수 없는 칸은 상어가 있거나, 공간의 경계를 넘는 칸이다. 조건ㅇ르 판단한다.
case1 -> 2, 3을 지나면서 : 각 물고기는 방향이 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전시킨다.
이렇게 한 턴을 예제 1로 돌게 되면,
로 변하게 된다. 이후 상어가 가장 합이 많은 물고기를 먹도록 완전 탐색을 돌게 된다.
"물고기의 이동이 모두 끝나면 상어가 이동한다."
"상어는 방향에 있는 칸으로 이동할 수 있는데, 한 번에 여러 개의 칸을 이동할 수 있다. " 이 조건 때문에 for문을 통해 갈 수 있는 상어 방향을 모두 탐색해 주었다.
이후의 과정은 반복되면서 동일하게 이동하게 된다.
이 과정을 쭉쭉 반복하면 상어는 먹을 수 없는 경우까지 모두 돌게 되는데,
그러면서 s가 바뀔떄 sum을 최대값으로 업데이트 해준다.
eatFish의 경우 길어보이는데, switch문으로 감싸져 있어 수행은 한번만 되고, 리턴하게 되는데
그 결과
위 마지막 과정을 거치며 출력을 할 수 있게 된다.
생각보다.. 길어서 푸는데.. 한 .. 꽤 걸렷다...
'코딩테스트 연습 > 백준' 카테고리의 다른 글
| [ 백준 / 17779번 ] Gold IV - 게리맨더링 2 ( java ) (0) | 2020.10.02 |
|---|---|
| [ 백준 / 17822번 ] Gold III - 원판 돌리기 ( java ) (2) | 2020.09.25 |
| [ 백준 / 15685번 ] Gold IV - 드래곤 커브 ( java ) (0) | 2020.09.17 |
| [ 백준 / 17140 ] 이차원 배열과 연산 - Java (0) | 2020.08.21 |
| [ 백준 / 16235 ] 나무재테크 : java (0) | 2020.08.16 |
