문제 링크
19236번: 청소년 상어
첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는
www.acmicpc.net
주의사항
- JAVA를 사용하여 프로그램을 사용하였습니다.
- 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.
public class Main{
public static void main(String[] args){
}
}문제 설명
접근 방법
이 문제에 핵심은
1. 상어는 (0, 0)에 있는 물고기를 먹으며 해당 물고기의 방향으로 가집니다.
2. 상어는 방향으로 여러 칸을 이동할 수 있으며 여러 칸 이동시 지나가는 물고기는 먹지 않습니다.
3. 물고기가 이동한 이후 상어가 이동하기 시작합니다.
4. 물고기가 이동하려는 칸에 물고기가 존재하면 서로 위치를 바꿉니다.
5. 물고기가 이동하려는 칸이 상어나 경계일 경우 방향을 반시계 방향 45도로 바꾼 뒤 다시 이동을 시작한다.
6. 상어가 더 이상 물고기를 먹지 못할 때 먹을 수 있는 물고기 번호의 합의 최대값을 결과로 출력합니다.
알고리즘 진행 순서.
1. 입력되는 정보들을 저장합니다.
2. 백트래킹으로 상어의 이동을 조절하며 각 상황에 시뮬레이션을 진행합니다.
3. 상어의 모든 이동 경우를 탐색한 뒤 먹은 물고기 번호의 최대 합을 결과로 출력합니다.
방향(8가지)
물고기는 8가지방향으로 이동이 가능하다.
현재 물고기 위치(y, x)
↑ : (y-1, x)
↖: (y-1, x-1)
← : (y, x-1)
↙ : (y+1, x-1)
↓ : (y+1, x)
↘ : (y+1, x+1)
→ : (y, x+1)
↗ : (y-1, x+1)
예제입력 1
1. 입력되는 정보들을 저장합니다.
| 7(↘) | 2(←) | 15(↘) | 9(↗) |
| 3(↑) | 1(↗) | 14(→) | 10(↑) |
| 6(↑) | 13(↘) | 4(←) | 11(↙) |
| 16(↑) | 8(→) | 5(↖) | 12(↖) |
상어 진입
| 상어(7)(↘) | 2(←) | 15(↘) | 9(↗) |
| 3(↑) | 1(↗) | 14(→) | 10(↑) |
| 6(↑) | 13(↘) | 4(←) | 11(↙) |
| 16(↑) | 8(→) | 5(↖) | 12(↖) |
2. 백트래킹으로 상어의 이동을 조절하며 각 상황에 시뮬레이션을 진행합니다.
※백트래킹으로 모든 경우를 탐색하지만 설명할 때에는 최대합일 때 경우를 보여드리겠습니다.
| 상어(7)(↘) | 2(←) | 15(↘) | 9(↗) |
| 3(↑) | 1(↗) | 14(→) | 10(↑) |
| 6(↑) | 13(↘) | 4(←) | 11(↙) |
| 16(↑) | 8(→) | 5(↖) | 12(↖) |
물고기 이동!
| 상어(7)(↘) | 2(↙) | 9(←) | 10(↑) |
| 6(↑) | 12(↖) | 1(↗) | 14(→) |
| 16(↑) | 5(↖) | 15(↘) | 13(↑) |
| 3(↙) | 4(←) | 11(↙) | 8(→) |
상어 먹기!
| 2(↙) | 9(←) | 10(↑) | |
| 6(↑) | 12(↖) | 1(↗) | 14(→) |
| 16(↑) | 5(↖) | 상어(22)(↘) | 13(↑) |
| 3(↙) | 4(←) | 11(↙) | 8(→) |
물고기 이동!
| 12(↖) | 9(←) | 10(↑) | 14(↑) |
| 16(↑) |
6(←) | 1(↗) | |
| 5(↖) | 13(↖) | 상어(22)(↘) | 8(↑) |
| 3(→) | 4(→) | 2(↙) | 11(→) |
상어 먹기!
| 12(↖) | 9(←) | 10(↑) | 14(↑) |
| 16(↑) |
6(←) | 1(↗) | |
| 5(↖) | 13(↖) | 8(↑) | |
| 3(→) | 4(→) | 2(↙) | 상어(33)(→) |
물고기 이동!
| 9(←) | 16(↑) | 10(↑) | 14(↑) |
| 13(↖) |
12(↖) | 1(↑) |
|
| 3(→) | 6(←) | 8(↑) | 2(↗) |
| 5(↓) | 4(→) | 상어(33)(→) |
상어 먹기!
상어가 방향대로 이동해도 먹을 수 있는 물고기가 존재하지 않기 때문에 현재 값을 최대값과 비교합니다.
현재 값이 최대값이기 때문에 최대값으로 저장
3. 상어의 모든 이동 경우를 탐색한 뒤 먹은 물고기 번호의 최대 합을 결과로 출력합니다.
최대값 33을 출력합니다.
- BufferedReader를 사용하여 입력 값을 받았습니다.
- StringTokenizer를 이용하여 입력된 정보들을 띄어쓰기 기준으로 나누었습니다.
- init을 실행하여 상어의 진입을 진행하도록 합니다.
- start함수으로 모든 경우의 시뮬레이션을 진행합니다.
- 모든 경우의 시뮬레이션 종료 후 상어가 물고기를 먹은 최대합을 BufferedWriter 저장하였습니다.
- BufferedWriter에 저장된 결과값을 출력하였습니다.
- init함수는 상어가 처음이 진입하는 것을 진행합니다.
- start함수는 백트래킹으로 상어가 이동할 수 있는 모든 경우에서 fishMove를 이용해 시뮬레이션을 진행합니다.
- fishMove함수는 문제에 설명한 규칙대로 물고기의 움직임을 진행합니다.
- inSpace는 물고기나 상어가 이동하려는 칸이 공간에 존재하는지 확인합니다.
import java.io.*;
import java.util.HashMap;
import java.util.StringTokenizer;
public class Main {
//물고기 정보 클래스
static class info{
int x, y, d;
boolean dead;
public info(int x, int y, int d, boolean dead) {
this.x = x;
this.y = y;
this.d = d;
this.dead = dead;
}
}
static int[] dx = {0, 0, -1, -1, -1, 0, 1, 1, 1}; //물고기 방향에 따른 x변경값
static int[] dy = {0, -1, -1, 0, 1, 1, 1, 0, -1}; //물고기 방향에 따른 y변경값
static int[][] space = new int[4][4]; //공간에 물고기나 상어 위치 저장
static info[] fish = new info[17]; //물고기 정보 저장 리스트
static int point = 0; //물고기 먹은 번호 합의 최대값
public static void main(String[] args) throws IOException {
//입력값 처리하는 BufferedReader
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//결과값 출력하는 BufferedWriter
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
//물고기 정보 저장
for(int i=0;i<4;i++){
st = new StringTokenizer(br.readLine()," ");
for(int j=0;j<4;j++){
int n = Integer.parseInt(st.nextToken());
space[i][j] = n;
fish[n] = new info(j, i, Integer.parseInt(st.nextToken()), false);
}
}
init(); //상어 진입
start(0, 0, fish[point].d, point); //백트래킹으로 시뮬레이션 진행
bw.write(point + ""); //최대합 BufferedWriter 저장
bw.flush(); //결과 출력
bw.close();
br.close();
}
//백트래킹으로 모든 경우를 시뮬레이션 진행하는 함수
static void start(int x, int y, int d, int value){
point = Math.max(point, value); //현재 먹은 물고기 합 비교
//원 상태로 되돌리기 위해 현재 공간과 물고기 정보 복사
int[][] tempSpace = new int[4][4];
info[] tempFish = new info[17];
//공간 복사
for(int i=0;i<4;i++)
System.arraycopy(space[i], 0, tempSpace[i], 0, 4);
//물고기 정보 복사
for(int i=1;i<=16;i++)
tempFish[i] = new info(fish[i].x,fish[i].y, fish[i].d, fish[i].dead);
fishMove(); //물고기 이동 진행
//상어 이동할 수 있는 경우 모두 진행
for(int i=1;i<=4;i++){
int tempX = x + dx[d]*i;
int tempY = y + dy[d]*i;
if(!inSpace(tempX,tempY))
break;
if(space[tempY][tempX]==0)
continue;
int tempD = fish[space[tempY][tempX]].d;
int tempS = space[tempY][tempX];
fish[tempS].dead = true; //해당 물고기 죽었다고 표현
space[y][x] = 0;
space[tempY][tempX] = 17;
//다음 경우 진행
start(tempX, tempY, tempD, value + tempS);
space[tempY][tempX] = tempS;
space[y][x] = 17;
fish[tempS].dead = false; //해당 물고기 복구
}
//공간 원상태로 복구
for(int i=0;i<4;i++)
System.arraycopy(tempSpace[i], 0, space[i], 0, 4);
//물고기 정보 복구
for(int i=1;i<=16;i++)
fish[i] = new info(tempFish[i].x,tempFish[i].y, tempFish[i].d, tempFish[i].dead);
}
//물고기 이동 진행하는 함수
static void fishMove(){
for(int i=1;i<17;i++){
if(fish[i].dead) //죽은 물고기는 넘기기
continue;
info cur = fish[i];
for(int j=0;j<7;j++){
int tempX = cur.x + dx[cur.d];
int tempY = cur.y + dy[cur.d];
if(inSpace(tempX,tempY) && space[tempY][tempX]!=17){
if(space[tempY][tempX]!=0){ //이동하려는 칸에 물고기 존재시
info temp = fish[space[tempY][tempX]];
temp.x = cur.x;
temp.y = cur.y;
}
space[cur.y][cur.x] = space[tempY][tempX];
space[tempY][tempX] = i;
cur.x = tempX;
cur.y = tempY;
break;
}else //이동하려는 칸이 상어나 경계일 경우 방향 변경
cur.d = cur.d+1==9?1:cur.d+1;
}
}
}
//물고기 이동시 공간에 존재하는 확인하는 함수
static boolean inSpace(int x, int y){
if(x>=0 && y>=0 && x<4 && y<4)
return true;
return false;
}
//상어 진입을 진행하는 함수
static void init(){
point += space[0][0];
fish[space[0][0]].dead = true;
space[0][0] = 17;
}
}'백준' 카테고리의 다른 글
| [백준] code.plus(시뮬레이션과 구현,JAVA)19237번, 어른 상어 (0) | 2022.08.16 |
|---|---|
| [백준] 단계별로 풀어보기(단계:1,입출력과 사칙연산,JAVA) 3003번, 킹, 퀸, 룩, 비숍, 나이트, 폰 (0) | 2022.08.16 |
| [백준] code.plus(브루트 포스 Part 1,JAVA)16968번, 차량 번호판 1 (0) | 2022.08.14 |
| [백준] code.plus(시뮬레이션과 구현,JAVA)20061번, 도노미노도미노 2 (0) | 2022.08.13 |
| [백준] code.plus(시뮬레이션과 구현,JAVA)16939번, 2×2×2 큐브 (0) | 2022.08.13 |
댓글