[백준] 19236 - 청소년 상어 (JAVA)

1. 소요시간 : 3시간
2. 문제 사이트 : 백준
3. 문제 수준 : 골드 2
4. 문제 유형 : 구현, 시뮬레이션, 백트래킹
5. 다른 사람의 풀이를 참고 했는가 ? : X
6. 문제 링크 : https://www.acmicpc.net/problem/19236
7. 푼 날짜 : 2023.04.27

1. 사용한 자료구조 & 알고리즘

백트래킹, 구현, 시뮬레이션

2. 풀이과정

1. 백트래킹으로 탐색한다.
2. 물고기들을 우선 이동시킨다.
3. 상어의 위치는 -1로 표시하고, 물고기가 이동한 뒤 상어가 바라보는 방향으로 1칸, 2칸, 3칸 까지 확인한다. 각각의 위치가 물고기라면 백트래킹으로 이어서 탐색한다.

3. 소스코드

import java.util.*;
import java.io.*;

public class Main{

	static int fish[][][]=new int [4][4][2];
	static int dy[]= {0,-1,-1,0,1,1,1,0,-1};
	static int dx[]= {0,0,-1,-1,-1,0,1,1,1};
	static int max = 0;

	
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb=new StringBuilder();
		StringTokenizer st;

		for(int i=0;i<4;i++) {
			st=new StringTokenizer(br.readLine());
			for(int j=0;j<4;j++) {
				int num=Integer.parseInt(st.nextToken());
				int dir=Integer.parseInt(st.nextToken());
				fish[i][j][0]=num;
				fish[i][j][1]=dir;
			}
		}
	
		int sum = fish[0][0][0];
		
		//상어의 좌표는 -1로 표시
		fish[0][0][0]= -1;
		
		max = sum;
		
		//백트래킹 탐색
		backtracking(fish,sum);
		
		
		System.out.println(max);
		
	}
	public static void backtracking(int map[][][],int sum) {
		//최댓값 갱신
		max= Math.max(max,sum);
		
		//물고기들을 이동시킴
		int copy[][][] = moveFish(map);
		
		//상어의 좌표를 찾음
		int sharkY=0;
		int sharkX=0; 
		for(int i=0;i<4;i++) {
			for(int j=0;j<4;j++) {
				if(copy[i][j][0] == -1) {
					sharkY=i;
					sharkX=j;
				}
			}
		}
		int prevY=sharkY;
		int prevX=sharkX;
	
		//상어가 위치한 좌표의 방향을 찾음
		int dir = copy[sharkY][sharkX][1];
	
		for(int p=0;p<3;p++) {
			//맵을 복사함.
			int newarr[][][]=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++) {
						newarr[i][j][k] = copy[i][j][k];
					}
				}
			}
		
			//상어의 방향으로 1칸 이동
			sharkY+=dy[dir];
			sharkX+=dx[dir];
			//맵을 벗어났다면 break
			if(sharkY<0||sharkX<0||sharkY>=4||sharkX>=4)
				break;
		
			//해당 좌표가 물고기라면 물고기를 먹고, 상어의 좌표를 이동시킴.
			//그리고 백트래킹을 이어서 탐색
			if(newarr[sharkY][sharkX][0]>0) {
				newarr[prevY][prevX][0] = 0;
				newarr[prevY][prevX][1] = 0;
				int temp = newarr[sharkY][sharkX][0];
				newarr[sharkY][sharkX][0] = -1;
				backtracking(newarr,sum+temp);
			}
			
			
			
		}
		
		
	}

	//물고기를 이동시키는 메소드
	public static int[][][] moveFish(int map[][][]) {
		int count =0;
	
		//맵을 복사함
		int clone[][][]=new int[4][4][2];
		for(int i=0;i<4;i++) {
			for(int j=0;j<4;j++) {
				clone[i][j][0] =map[i][j][0];
				clone[i][j][1] =map[i][j][1];
				//물고기의 개수를 세어줌
				if(clone[i][j][0]>0)count ++;
			}
		}
		
		//방문처리할 해시셋
		HashSet<Integer> set=new HashSet<>();
	
		
		int dir = 0;
		//물고기의 개수만큼 반복
		while(count-->0) {
	
			int min = Integer.MAX_VALUE;
			int yy=0;
			int xx=0;
			for(int i=0;i<4;i++) {
				for(int j=0;j<4;j++) {
					//해당 좌표가 물고기이고
					//아직까지 이동하지 않은 가장 낮은 번호의 물고기라면
					if(clone[i][j][0]>0&&
							clone[i][j][0]<min&&
							!set.contains(clone[i][j][0])) {
						//최소 물고기 번호 갱신.
						min = clone[i][j][0];
						dir = clone[i][j][1];
						yy=i;
						xx=j;
					}
				}
			}
			//최소값의 물고기는 이동시킬 것이므로 해시셋에 추가
			set.add(min);
			int nextY=0;
			int nextX=0;
			//해당 방향이 이동가능한 방향인지 확인
			while(true) {
				nextY = yy + dy[dir];
				nextX = xx + dx[dir];
				//맵을 벗어나면 45도 회전
				if(nextY<0||nextX<0||nextY>=4||nextX>=4) 
					dir ++;
				//상어라면 45도 회전
				else if(clone[nextY][nextX][0]== -1)
					dir++;
				//아니라면 이동할 좌표를 찾았음
				else
					break;
				
				if(dir>8)
					dir=1;
			}
			//두 물고기의 위치를 교환
			int temp1 = clone[yy][xx][0];
			int temp2 = dir;
			clone[yy][xx][0] = clone[nextY][nextX][0];
			clone[yy][xx][1] = clone[nextY][nextX][1];
			clone[nextY][nextX][0] =temp1;
			clone[nextY][nextX][1] =temp2;
	
		}
	
		return clone;
		
		
		
	}
}

4. 결과

5. 회고

문제 풀다가 머리 100가닥은 빠진거같다.
생각하지 못한 오류를 계속 겪어서 답답했다. 백트래킹 문제는
오류가 생겼을 때 디버깅 하는게 너무 힘든 것 같다.

하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212