알고리즘/백준
[JAVA/DFS] 백준 19236 청소년 상어
waterground
2021. 10. 29. 16:01
1. 문제
https://www.acmicpc.net/problem/19236
19236번: 청소년 상어
첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는
www.acmicpc.net
2. 풀이
- 상어의 위치를 DFS를 이용해 움직인다.
- 상어와 물고기를 각각 객체를 만들어 사용한다.
- 물고기(Fish)는 좌표, 물고기 번호, 방향, 살아있는지 여부를 멤버 변수로 갖는다.
- 상어(Shark)는 좌표, 방향, 먹은 물고기 번호의 합을 멤버 변수로 갖는다.
- 물고기 번호를 입력 받고, 탐색을 시작하기전,
- 물고기를 번호 순서대로 먹기 위해 물고기가 담긴 list를 번호순으로 오름차순 정렬한다
- 상어가 (0,0)로 이동해 (0,0)에 있는 물고기를 먹는다.
- DFS로 물고기를 이동하는데 먼저 모든 살아있는 물고기들을 이동한다(moveFish())
- 반시계방향으로 이동하기 위해 이동 좌표를 담은 배열 dir에 반시계방향으로 값을 넣는다.
- 상어가 해당 방향으로 1칸 이상 이동할 수 있기 때문에 for문을 이용해 최대 3배수까지 움직인다.
- 먹히거나 상어가 있는 자리는 지나지 않는다.
- map[i][j] == 0 : 먹힌 자리
- map[i][j] == -1: 상어가 있는 자리
- 먹을 수 있는 물고기를 먹고, 계속해서 DFS를 진행해 먹을 수 있는 물고기 번호 합의 최댓값을 구한다
3. 코드
import java.util.*;
import java.io.*;
class Main{
// 청소년 상어
static class Fish { // 물고기
int x, y, number, dir;
boolean isAlive; // 상어에게 먹히지 않고 살아있는지
public Fish(int x, int y, int number, int dir, boolean isAlive) {
this.x = x;
this.y = y;
this.number = number;
this.dir = dir;
this.isAlive = isAlive;
}
public Fish() {}
}
static class Shark{ // 상어
int x, y, dir, sum; // 좌표, 방향, 먹은 물고기 번호 합
public Shark(int x, int y, int dir, int sum) {
this.x = x;
this.y = y;
this.dir = dir;
this.sum = sum;
}
}
// 반시계방향
static int[][] dir = {{-1,0},{-1,-1},{0,-1},{1,-1},
{1,0},{1,1},{0,1},{-1,1}};
static int max = 0;
// 주어진 좌표가 map 범위 내인지
public static boolean isInRange(int x, int y) {
return (x >= 0 && x < 4 && y >= 0 && y < 4);
}
public static int[][] copyMap(int[][] map) {
int[][] tmp = new int[4][4];
for(int i = 0; i < 4; i++)
for(int j = 0; j < 4; j++)
tmp[i][j] = map[i][j];
return tmp;
}
public static ArrayList<Fish> copyList(ArrayList<Fish> fishes){
ArrayList<Fish> tmp = new ArrayList<Fish>();
fishes.forEach(e -> tmp.add(new Fish(e.x, e.y, e.number, e.dir, e.isAlive)));
return tmp;
}
// 빈 칸 또는 다른 물고기 있는 칸으로 물고기 이동
public static void moveFish(Fish f, int[][] map, ArrayList<Fish> fishes) {
if(f.isAlive == false) return;
for(int i = 0; i < 8; i++) {
int nDir = (f.dir + i) % 8;
int nX = f.x + dir[nDir][0];
int nY = f.y + dir[nDir][1];
// 상어 있는 자리는 지나지 않음
if(!isInRange(nX, nY) || map[nX][nY] == -1) continue;
map[f.x][f.y] = 0;
if(map[nX][nY] == 0) { // 빈 자리면 바로 이동
f.x = nX;
f.y = nY;
}else { // 빈자리 아니면 다른 물고기와 변경
Fish tmp = fishes.get(map[nX][nY] - 1);
tmp.x = f.x;
tmp.y = f.y;
map[f.x][f.y]= tmp.number;
f.x = nX;
f.y = nY;
}
map[nX][nY] = f.number;
f.dir = nDir;
return;
}
}
// dfs를 통해 상어 이동
public static void dfs(int[][] map, ArrayList<Fish> fishes, Shark shark) {
if(max < shark.sum) {
max = shark.sum;
}
// 모든 살아있는 물고기 이동
fishes.forEach(e -> moveFish(e, map, fishes));
// 4*4이므로 최대 3배수까지 움직일 수 있음
for(int i = 1; i < 4; i++) {
int nX = shark.x + dir[shark.dir][0] * i;
int nY = shark.y + dir[shark.dir][1] * i;
// 먹히거나 상어 있는 자리는 지나지 않음
if(!isInRange(nX, nY) || map[nX][nY] <= 0) continue;
// 물고기 잡아먹고 dfs 계속
int[][] cMap = copyMap(map);
ArrayList<Fish> cFishes = copyList(fishes);
Fish eatenFish = cFishes.get(map[nX][nY] - 1); // 물고기 잡아 먹음
cMap[shark.x][shark.y] = 0;
eatenFish.isAlive = false;
cMap[eatenFish.x][eatenFish.y] = -1; // 새로운 상어 위치
Shark nShark = new Shark(eatenFish.x, eatenFish.y, eatenFish.dir, shark.sum + eatenFish.number);
dfs(cMap, cFishes, nShark);
}
}
public static void main (String[] args) throws java.lang.Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int[][] map = new int[4][4];
ArrayList<Fish> fishes = new ArrayList<>();
for(int i = 0; i < 4; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for(int j = 0; j < 4; j++) {
Fish f = new Fish();
f.number = Integer.parseInt(st.nextToken());
f.dir = Integer.parseInt(st.nextToken()) - 1;
f.x = i;
f.y = j;
f.isAlive = true;
map[i][j] = f.number;
fishes.add(f);
}
}
// 물고기를 번호순으로 오름차순 정렬
Collections.sort(fishes, new Comparator<Fish>() {
@Override
public int compare(Fish f1, Fish f2) {
return f1.number - f2.number;
}
});
// 상어가 (0,0) 위치의 물고기를 먹음
Fish f = fishes.get(map[0][0] - 1);
f.isAlive = false;
map[f.x][f.y] = -1; // 상어 위치
Shark shark = new Shark(0, 0, f.dir, f.number);
dfs(map, fishes, shark);
System.out.println(max);
}
}