[백준 19236] 청소년 상어 (JAVA)
백준(BOJ) 19236 청소년 상어
난이도
221219 기준 골드 2
사용 알고리즘
구현
백트래킹
문제 링크
https://www.acmicpc.net/problem/19236
19236번: 청소년 상어
첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는
www.acmicpc.net
풀이 과정
1. 문제 읽기(중요한 부분 굵은 표시)
4×4크기의 공간이 있고, 크기가 1×1인 정사각형 칸으로 나누어져 있다. 공간의 각 칸은 (x, y)와 같이 표현하며, x는 행의 번호, y는 열의 번호이다. 한 칸에는 물고기가 한 마리 존재한다. 각 물고기는 번호와 방향을 가지고 있다. 번호는 1보다 크거나 같고, 16보다 작거나 같은 자연수이며, 두 물고기가 같은 번호를 갖는 경우는 없다. 방향은 8가지 방향(상하좌우, 대각선) 중 하나이다.
오늘은 청소년 상어가 이 공간에 들어가 물고기를 먹으려고 한다. 청소년 상어는 (0, 0)에 있는 물고기를 먹고, (0, 0)에 들어가게 된다. 상어의 방향은 (0, 0)에 있던 물고기의 방향과 같다. 이후 물고기가 이동한다.
물고기는 번호가 작은 물고기부터 순서대로 이동한다. 물고기는 한 칸을 이동할 수 있고, 이동할 수 있는 칸은 빈 칸과 다른 물고기가 있는 칸, 이동할 수 없는 칸은 상어가 있거나, 공간의 경계를 넘는 칸이다. 각 물고기는 방향이 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전시킨다. 만약, 이동할 수 있는 칸이 없으면 이동을 하지 않는다. 그 외의 경우에는 그 칸으로 이동을 한다. 물고기가 다른 물고기가 있는 칸으로 이동할 때는 서로의 위치를 바꾸는 방식으로 이동한다.
물고기의 이동이 모두 끝나면 상어가 이동한다. 상어는 방향에 있는 칸으로 이동할 수 있는데, 한 번에 여러 개의 칸을 이동할 수 있다. 상어가 물고기가 있는 칸으로 이동했다면, 그 칸에 있는 물고기를 먹고, 그 물고기의 방향을 가지게 된다. 이동하는 중에 지나가는 칸에 있는 물고기는 먹지 않는다. 물고기가 없는 칸으로는 이동할 수 없다. 상어가 이동할 수 있는 칸이 없으면 공간에서 벗어나 집으로 간다. 상어가 이동한 후에는 다시 물고기가 이동하며, 이후 이 과정이 계속해서 반복된다.
상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 구해보자.
입력
첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 8보다 작거나 같은 자연수를 의미하고, 1부터 순서대로 ↑, ↖, ←, ↙, ↓, ↘, →, ↗ 를 의미한다.
출력
상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 출력한다.
2. 어떤 알고리즘을 사용할 것인가
우리가 구해야 할 것은 상어가 먹는 물고기 번호의 합이 최대가 되는 값입니다. 물고기의 이동이 사실상 무작위 이동과 가깝기 때문에 물고기의 이동으로 예측하기는 쉽지 않습니다. 따라서 상어의 이동을 전부 탐색하는 것이 시간초과가 나지 않는다면 답을 찾는 가장 편하고 정확한 방법이 될 수 있습니다.
공간의 크기가 4X4입니다. 따라서 상어가 매 이동마다 최대로 움직일 수 있는 경우의 수는 경계선 끝에서 끝까지 이동하는 4가지 경우이고 0~4개의 경우가 될 수도 있습니다. 16개의 물고기를 전부 먹는다 치면 단순히 생각하는 최악의 경우는 4의 16승 = 4,294,967,296으로 시간초과가 날 수 있지만 문제를 읽어보면 상어가 더 이상 이동할 수 없는 경우 그 이후의 경우의 수는 볼 필요가 없기에 백트래킹을 적절히 해주면 1억번의 연산 안에 들어 올 가능성이 큽니다.
3. 풀이 구상
상어 클래스와 물고기 클래스를 만들어서 구현할 것입니다.
상어 클래스는 필드 값으로 현재 상어의 위치, 이동 방향, 현재까지 먹은 물고기 번호의 합을 가질 것이고 메서드로는 이동하고 물고기 잡아먹는 기능이 필요해 보입니다.
물고기 클래스는 필드 값으로 현재 물고기의 위치, 이동 방향, 물고기 번호를 가지고 메서드로는 위치 이동하는 메서드가 있을 것입니다.
여기까지만 구상하고 기타 필요한 부분은 코드를 짜면서 추가하겠습니다. 아마 이차원 배열의 깊은 복사 부분에서 조금 골치 아플 수도 있겠네요
4. 코드 작성
1. 정답 코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
// 백준 19236번 청소년 상어 라이브 코딩
public class Main {
static Fish[][] board;
// 위 부터 반시계로 8방향(1~8)
static int[] dr = {0, -1,-1,0,1,1,1,0,-1};
static int[] dc = {0, 0,-1,-1,-1,0,1,1,1};
static int resultMax;
static class Shark{
int r;
int c;
int sumofFish;
int direction;
public Shark(int r, int c) {
this.r = r;
this.c = c;
}
void eatFish(Fish[][] board) {
sumofFish += board[r][c].num;
this.direction = board[r][c].direction;
board[r][c] = null;
}
}
static class Fish {
int r;
int c;
int num;
int direction;
public Fish(int r, int c, int num, int direction) {
this.r = r;
this.c = c;
this.num = num;
this.direction = direction;
}
@Override
public String toString() {
return "" + num;
}
void move(Shark shark, Fish[][] board){
boolean moved = false;
int movecnt = 0;
while(!moved) {
int direction = (this.direction+movecnt)%9;
if(direction==0) {
direction = 1;
}
int nr = this.r+dr[direction];
int nc = this.c+dc[direction];
int curr = this.r;
int curc = this.c;
if(inRange(nr,nc) && !(shark.r==nr && shark.c==nc)) {
if(board[nr][nc]!=null) {
Fish temp = board[nr][nc];
board[nr][nc] = board[curr][curc];
board[curr][curc] = temp;
board[curr][curc].r = curr;
board[curr][curc].c = curc;
board[nr][nc].r = nr;
board[nr][nc].c = nc;
} else if(board[nr][nc]==null) {
board[nr][nc] = board[curr][curc];
board[nr][nc].r = nr;
board[nr][nc].c = nc;
board[curr][curc] = null;
}
this.direction = direction;
moved = true;
} else {
movecnt++;
if(movecnt==8) {
return;
}
}
}
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
board = new Fish[4][4];
for(int r = 0; r < 4; r++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for(int c = 0; c < 4; c++) {
int num = Integer.parseInt(st.nextToken());
int direction = Integer.parseInt(st.nextToken());
board[r][c] = new Fish(r,c,num,direction);
}
}
Shark shark= new Shark(0,0);
resultMax = Integer.MIN_VALUE;
goShark(shark, board);
bw.write(resultMax+"");
bw.flush();
bw.close();
br.close();
}
static void goShark(Shark shark, Fish[][] board) {
PriorityQueue<Fish> q = new PriorityQueue<>(new Comparator<Fish>(){
@Override
public int compare(Fish o1, Fish o2) {
return o1.num-o2.num;
}
});
Fish[][] nextBoard = new Fish[4][4];
for(int r = 0; r < 4; r++) {
for(int c = 0; c < 4; c++) {
if(board[r][c]!=null) {
Fish cur = board[r][c];
Fish newFish = new Fish(cur.r,cur.c,cur.num,cur.direction);
nextBoard[r][c] = newFish;
}
}
}
// 이동한 위치에서 물고기 잡아먹기
shark.eatFish(nextBoard);
for(int r = 0; r < 4; r++) {
for(int c = 0; c < 4; c++) {
if(nextBoard[r][c]!=null) {
q.add(nextBoard[r][c]);
}
}
}
while(q.size()>0) {
Fish curFish = q.poll();
curFish.move(shark,nextBoard);
}
// for(Fish[] arr : nextBoard) {
// System.out.println(Arrays.toString(arr));
// }
int moveCnt = 1;
int snr = shark.r+dr[shark.direction]*moveCnt;
int snc = shark.c+dc[shark.direction]*moveCnt;
while(inRange(snr,snc)) {
if(nextBoard[snr][snc]!=null) {
Shark nextShark = new Shark(snr,snc);
nextShark.sumofFish = shark.sumofFish;
goShark(nextShark, nextBoard);
}
moveCnt++;
snr = shark.r+dr[shark.direction]*moveCnt;
snc = shark.c+dc[shark.direction]*moveCnt;
}
resultMax = Math.max(resultMax, shark.sumofFish);
}
static boolean inRange(int nr, int nc) {
if(nr>=0 && nr < 4 && nc >= 0 && nc < 4) {
return true;
} else {
return false;
}
}
}
2. 주의할 점
정답은 한 번에 맞췄지만 시간은 조금 걸렸습니다. 풀이를 구상했던 부분에서 생각하지 못한 것들이 코드를 짜다보니 많이 나왔네요
- 먼저 깊은 복사에 대한 부분을 고려해야 합니다. 재귀를 할 때 언제 깊은 복사를 할 것인지 어떤 값을 깊은 복사를 해야하는지 등등 코드를 짜다보니 많이 헷갈렸는데요 자바에서의 깊은 복사에 대한 정확한 이해가 되어 있어야 문제를 조금 더 빨리 풀 수 있을 것입니다.
- 풀이를 구상할 때는 생각하지 못했던 부분인데 물고기가 이동 할 때마다 1번부터 순서대로 이동하는 것을 관리해줄 자료구조가 하나 필요하다 생각했고 PriorityQueue가 적절한 것 같아 선택했습니다.
- 문제를 좀 더 꼼꼼히 읽어야 합니다. 분명 다 맞은 것 같은데 답이 안나와서 디버깅을 하다가 물고기가 방향을 바꿔 이동했을 때 물고기의 초기 방향값을 바꿔줘야 한다는 것을 놓쳤다는 것을 깨달았습니다. 문제를 읽을 때 체크를 해뒀다면 코드를 짤때 더 빠르게 풀었을 것입니다.
풀이 후기
이 문제는 백준에 있는 삼성 SW역량테스트 문제집에 있는 문제입니다. 삼성 SW역량테스트는 구현문제가 많이 나오는데요 이번 문제를 계기로 깊은 복사에 대한 공부를 한 번 더 복습해 볼 생각입니다.