문제 링크
19236번: 청소년 상어
첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는
www.acmicpc.net
문제 개요
BOJ 19236번 (자바) 청소년 상어 - 시뮬레이션 / DFS / 백트래킹
4 ×4 크기의 공간이 있고, 크기가 1 ×1인 정사각형 칸으로 나누어져 있다. 공간의 각 칸은 (x, y)와 같이 표현하며, x는 행의 번호, y는 열의 번호이다. 한 칸에는 물고기가 한 마리 존재한다. 각 물고기는 번호와 방향을 가지고 있다. 번호는 1보다 크거나 같고, 16보다 작거나 같은 자연수이며, 두 물고기가 같은 번호를 갖는 경우는 없다. 방향은 8가지 방향(상하좌우, 대각선) 중 하나이다.
오늘은 청소년 상어가 이 공간에 들어가 물고기를 먹으려고 한다. 청소년 상어는 (0, 0)에 있는 물고기를 먹고, (0, 0)에 들어가게 된다. 상어의 방향은 (0, 0)에 있던 물고기의 방향과 같다. 이후 물고기가 이동한다.
물고기는 번호가 작은 물고기부터 순서대로 이동한다. 물고기는 한 칸을 이동할 수 있고, 이동할 수 있는 칸은 빈 칸과 다른 물고기가 있는 칸, 이동할 수 없는 칸은 상어가 있거나, 공간의 경계를 넘는 칸이다. 각 물고기는 방향이 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전시킨다. 만약, 이동할 수 있는 칸이 없으면 이동을 하지 않는다. 그 외의 경우에는 그 칸으로 이동을 한다. 물고기가 다른 물고기가 있는 칸으로 이동할 때는 서로의 위치를 바꾸는 방식으로 이동한다.
물고기의 이동이 모두 끝나면 상어가 이동한다. 상어는 방향에 있는 칸으로 이동할 수 있는데, 한 번에 여러 개의 칸을 이동할 수 있다. 상어가 물고기가 있는 칸으로 이동했다면, 그 칸에 있는 물고기를 먹고, 그 물고기의 방향을 가지게 된다. 이동하는 중에 지나가는 칸에 있는 물고기는 먹지 않는다. 물고기가 없는 칸으로는 이동할 수 없다. 상어가 이동할 수 있는 칸이 없으면 공간에서 벗어나 집으로 간다. 상어가 이동한 후에는 다시 물고기가 이동하며, 이후 이 과정이 계속해서 반복된다.
문제를 정말 정말 꼼꼼히 읽어보고, 나름의 정리를 해야지 구현하기 수월하다!
로직
우선 물고기의 크기와 방향을 저장할 3차원 배열 하나(map), 사이즈 별로 물고기의 정보를 저장할 2차원 배열 하나(fish)를 생성한 후, 입력에 따라 값을 적절히 넣어주자. map [y][x][0]는 y, x위치의 물고기 크기 정보이고 map [y][x][1]은
Step 01. 이 문제는 DFS로 백트래킹을 해야 한다. DFS에 진입하기 전에 상어의 위치를 (0,0)으로 설정하고, 해당 위치의 물고기의 크기만큼 더해준다. map [0][0][0]와 map [0][0][1], fish [map [0][0][0]][0]와 fish [map [0][0][0]][1]을 -1로 초기화 해주자.
Step 02. 전체 물고기의 위치를 변경한다. 크기 1 ~ 16까지 반복. 해당 물고기가 없거나 상어와 위치가 같다면 다음 크기의 물고기로 넘어간다. 빈 곳이면 그냥 이동. 물고기가 있는 곳이면 서로 위치를 바꾸어 준다. map과 fish로 정보를 관리하고 있으므로, 자리를 바꾸고 난 다음 map과 fish의 정보가 섞이지 않게 조심해야 한다. 물고기의 방향은 반시계 방향으로 바뀌는데, 단순히 인덱스를 +1 해주는 것으로 방향 전환을 할 수 있다.
Step 03. 위치가 변경된 map과 fish를 복사해서 원본을 남겨둔다.
Step 04. 상어의 위치를 변경해준다. 이때 상어의 방향 모든 곳을 갈 수 있으므로, 백트래킹을 해야한다. 우선 상어의 위치를 정하고, 해당 위치의 물고기를 먹어주고, map과 fish 정보를 변경한다. 그리고 다시 Step02부터 반복. 더 이상 갈 곳이 없어서 return을 하게 되면 상어의 위치를 시작 위치로 되돌려주고, map과 fish의 정보를 원본으로 돌려준다.
Step 05. 더 이상 먹을 물고기가 없다면 최댓값을 갱신해준다.
로직
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static class Shark { // 상어 정보
int y, x, dir;
int eat = 0;
public Shark() {
super();
}
public Shark(int y, int x, int eat, int dir) {
this.y = y;
this.x = x;
this.eat = eat;
this.dir = dir;
}
}
private static int MAX;
private static int[] dy = { 0, -1, -1, 0, 1, 1, 1, 0, -1 };
private static int[] dx = { 0, 0, -1, -1, -1, 0, 1, 1, 1 };
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int[][][] map = new int[4][4][2]; // 물고기의 크기와 방향 저장
int[][] fish = new int[17][2]; // 사이즈 별로 물고기의 위치 정보를 담아야한다.
Shark shark = new Shark();
for (int i = 0; i < 4; i++) {
StringTokenizer stt = new StringTokenizer(br.readLine());
for (int j = 0; j < 4; j++) {
int size = Integer.parseInt(stt.nextToken());
int move = Integer.parseInt(stt.nextToken());
fish[size][0] = i;
fish[size][1] = j;
map[i][j][0] = size;
map[i][j][1] = move;
}
} // input end
MAX = Integer.MIN_VALUE;
// 상어를 0,0에 위치시키고 맵 변경
shark = new Shark(0, 0, map[0][0][0], map[0][0][1]);
fish[map[0][0][0]][0] = -1;
fish[map[0][0][0]][1] = -1;
map[0][0][0] = -1;
map[0][0][1] = -1;
// 상어정보, 물고기정보, 지도정보
process(shark, fish, map);
System.out.println(MAX);
}
private static void process(Shark shark, int[][] fish, int[][][] map) {
// step 02. 전체 물고기 위치 변경
for (int i = 1; i < 17; i++) {
int cur_y = fish[i][0];
int cur_x = fish[i][1];
if (cur_y == -1) // 물고기 없는 경우 pass
continue;
if (cur_y == shark.y && cur_x == shark.x) // 상어 위치인 경우 pass
continue;
int dir = map[cur_y][cur_x][1];
int cnt = 0;
while (cnt < 8) { // 한바퀴 반복하면 제자리
int next_y = cur_y + dy[dir];
int next_x = cur_x + dx[dir];
// 범위 체크, 상어체크
if (rangeCheck(next_y, next_x) || (next_y == shark.y && next_x == shark.x)) {
dir += 1;
if (dir > 8) // 8 이상이면 다시 1부터 시작
dir = 1;
cnt++;
continue;
}
// 이동 가능. 해당 위치에 물고기가 있다면 위치 교체, 빈곳이면 그냥 이동
if (map[next_y][next_x][0] == -1) {
map[next_y][next_x][0] = map[cur_y][cur_x][0];
map[next_y][next_x][1] = dir;
map[cur_y][cur_x][0] = -1;
map[cur_y][cur_x][1] = -1;
// 크기 i인 물고기 위치 변경
fish[i][0] = next_y;
fish[i][1] = next_x;
} else { // 물고기가 있는 경우
// 이동할 위치의 물고기 정보
int next_fish_size = map[next_y][next_x][0];
int next_fish_pos = map[next_y][next_x][1];
// 교환
map[next_y][next_x][0] = map[cur_y][cur_x][0];
map[next_y][next_x][1] = dir;
map[cur_y][cur_x][0] = next_fish_size;
map[cur_y][cur_x][1] = next_fish_pos;
fish[next_fish_size][0] = cur_y;
fish[next_fish_size][1] = cur_x;
fish[i][0] = next_y;
fish[i][1] = next_x;
}
break;
}
} // 물고기 위치 변경 end
// step 03. 지도 복사, 물고기 정보 복사
int[][][] tmp_map = new int[4][4][2];
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
for (int k = 0; k < 2; k++) {
tmp_map[i][j][k] = map[i][j][k];
}
}
}
int[][] tmp_fish = new int[17][2];
for(int i = 1; i < 17; i++) {
for(int j = 0; j < 2; j++) {
tmp_fish[i][j] = fish[i][j];
}
}
// step 04. 현재 지도로 process dfs
int cur_shark_y = shark.y;
int cur_shark_x = shark.x;
int cur_shark_dir = shark.dir;
int cur_shar_eat = shark.eat;
int next_y = cur_shark_y;
int next_x = cur_shark_x;
while (true) {
next_y += dy[cur_shark_dir];
next_x += dx[cur_shark_dir];
// Step 05. 더이상 물고기를 먹을 수 없다
if (rangeCheck(next_y, next_x)) {
MAX = MAX > cur_shar_eat ? MAX : cur_shar_eat;
break;
}
// 먹을 물고기가 있다
if (map[next_y][next_x][0] != -1) {
int next_fish_size = map[next_y][next_x][0];
int next_fish_dir = map[next_y][next_x][1];
shark.y = next_y;
shark.x = next_x;
shark.eat += next_fish_size;
shark.dir = next_fish_dir;
map[next_y][next_x][0] = -1;
map[next_y][next_x][1] = -1;
fish[next_fish_size][0] = -1;
fish[next_fish_size][1] = -1;
process(shark, fish, map);
shark.y = cur_shark_y;
shark.x = cur_shark_x;
shark.eat -= next_fish_size;
shark.dir = cur_shark_dir;
fish[next_fish_size][0] = next_y;
fish[next_fish_size][1] = next_x;
init_map(tmp_map, map);
init_fish(tmp_fish, fish);
} else
continue;
}
}
// 물고기 정보 초기화
private static void init_fish(int[][] tmp_fish, int[][] fish) {
for(int i = 1; i < 17; i++) {
for(int j = 0; j < 2; j++) {
fish[i][j] = tmp_fish[i][j];
}
}
}
// 지도 정보 초기화
private static void init_map(int[][][] tmp_map, int[][][] map) {
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
for (int k = 0; k < 2; k++) {
map[i][j][k] = tmp_map[i][j][k];
}
}
}
}
// 범위체크
private static boolean rangeCheck(int next_y, int next_x) {
return next_y >= 4 || next_y < 0 || next_x >= 4 || next_x < 0;
}
}
'문제풀이 > 백준 문제풀이' 카테고리의 다른 글
| [ 알고리즘 ] 코딩 - 백준 20057 - 마법사 상어와 토네이도.java (0) | 2021.04.16 |
|---|---|
| [ 알고리즘 ] 코딩 - 백준 19237 - 어른상어.java (0) | 2021.04.16 |
| [ 알고리즘 ] 코딩 - 백준 20055번 - 컨베이어 벨트 위의 로봇.java (0) | 2021.04.14 |
| [ 알고리즘 ] 코딩 - 백준 2473 - 세용액.java (0) | 2021.04.08 |
| [ 알고리즘 ] 코딩 - 백준 2470 - 두 용액.java (0) | 2021.04.08 |
