[백준] 19236번 청소년 상어 (java, 시뮬레이션)

www.acmicpc.net/problem/19236

19236번: 청소년 상어

물고기 이동은 구현에서 상어이동은 dfs로 완탐을 돌려줘야되는 문제여서 복잡했다 ㅠㅠ 지쳐.. 

 

중간에 상어가 멈춰서 ?? 했는데 나는 상어이동을 bfs로 구현했고 물고기가 있는 칸으로만 이동하는 것으로 짰더니 

 

빈 칸으로는 이동을 못해 오도가도 못한 상태로 끝나버렸다. 추후 빈 칸도 갈 수 있도록 했더니 통과되었다.

 

칸이 4x4로 정해져있기 때문에 무조건 3번 이동이 가능한지 for문으로 확인하는 방식으로 짜도 된다.

 

map에는 물고기 번호를 저장하고 물고기리스트 fishes[물고기번호]에는 클래스로 좌표와 방향을 저장했다.

 

 

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.concurrent.ForkJoinPool;

class Fish{
	int y;
	int x;
	int dir;
	int sum;
	public Fish(int y, int x, int dir) {
		super();
		this.y = y;
		this.x = x;
		this.dir = dir;
	}
	
	public Fish(int y, int x, int dir,int sum) {
		super();
		this.y = y;
		this.x = x;
		this.dir = dir;
		this.sum=sum;
	}
	
}


public class Main {
	static int[] ypos= {-1,-1,0,1,1,1,0,-1};//↑, ↖, ←, ↙, ↓, ↘, →, ↗
	static int[] xpos= {0,-1,-1,-1,0,1,1,1};
	static int answer;
	
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int[][] map=new int[4][4];
		Fish shark; //상어~
		Fish[] fishes=new Fish[17];//방향정보 저장

		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				int a=sc.nextInt();
				int b=sc.nextInt();
				map[i][j]=a;//물고기 번호
				fishes[a]=new Fish(i,j,b-1);
			}
		}
		int num=map[0][0];//물고기번호
		shark=new Fish(0,0,fishes[num].dir,num);//0,0
		fishes[num].dir=-1;//잡아 먹힘 표시
		map[0][0]=0;//물고기 먹음
		
		
		moveShark(map,shark,fishes);
		
		System.out.println(answer);
	}
	
	private static ArrayList<Fish> getFishList(int[][] map,Fish shark,Fish[] fishes){
		
		ArrayList<Fish> list=new ArrayList<>();
		Queue<Fish> q=new LinkedList<Fish>();
		q.add(shark);
		while(q.size()!=0) {
			Fish cur=q.poll();
			int y=cur.y;
			int x=cur.x;
			int d=cur.dir;
			int yy=y+ypos[d];
			int xx=x+xpos[d];
			if(xx<0 || yy<0 || xx>=4 || yy>=4)continue;
			if(map[yy][xx]==0) {//빈 칸이동
				q.add(new Fish(yy,xx,d));
			}else {
				int num=map[yy][xx];
				list.add(new Fish(yy,xx,fishes[num].dir));
				q.add(new Fish(yy,xx,d));
			}
		
		}
		return list;
	}

	private static void moveShark(int[][] map,Fish shark,Fish[] fishes) {
		if(answer<shark.sum)answer=shark.sum;

		moveFish(map,shark,fishes);//물고기 이동
		// 상어이동
		//상어가 먹을 물고기 리스트
		ArrayList<Fish> list=getFishList(map, shark, fishes);

		for (int i = 0; i < list.size(); i++) {
			int[][] copy=copiedMap(map);
			Fish[] cfishes=copiedFish(fishes);
			Fish cur=list.get(i);
			int num=copy[cur.y][cur.x];

			//이번 물고기 먹음
			copy[cur.y][cur.x]=0;
			Fish newShark=new Fish(cur.y,cur.x,cur.dir,shark.sum+num);//먹은 물고기의 방향으로 전환됨
			cfishes[num].dir=-1;
			moveShark(copy,newShark,cfishes);// dfs 돌리기
		}
		

	}


//	물고기 이동
	private static void moveFish(int[][] map,Fish shark,Fish[] fishes) {
		

		for (int num = 1; num <= 16; num++) {//번호 작은 물고기부터
			if(fishes[num].dir==-1)continue;
			int d=fishes[num].dir;//원래 방향
			int y=fishes[num].y;
			int x=fishes[num].x;
			
			while(true) {

				int yy=y+ypos[d];
				int xx=x+xpos[d];
//				범위 벗어남
				if(xx<0 || yy<0 || xx>=4 || yy>=4) {
					d=(d+1)%8;
					if(d==fishes[num].dir)break;//원래 방향으로 되돌아오면 더이상 갈 곳 없음  break
					continue;
				}
//				상어있는 곳 못감
				if(xx==shark.x && yy==shark.y) {
					d=(d+1)%8;
					if(d==fishes[num].dir)break;//원래 방향으로 되돌아오면 더이상 갈 곳 없음  break
					continue;
				}
				
				if(map[yy][xx]==0) {//빈칸
					map[yy][xx]=num;
					map[y][x]=0;
					fishes[num]=new Fish(yy,xx,d);
					break;
				}else {//물고기 있는 칸
					int temp=map[yy][xx];
					map[yy][xx]=num;
					map[y][x]=temp;
					fishes[num].y=yy;
					fishes[num].x=xx;
					fishes[num].dir=d;//방향전환하는 애라서 갱신
					fishes[temp].y=y;
					fishes[temp].x=x;
					break;
				}
				
			}
			
		}

	}
	
	private static int[][] copiedMap(int[][] map){
		int[][] copied=new int[4][4];
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				copied[i][j]=map[i][j];
			}
		}
		return copied;
	}
	
	private static Fish[] copiedFish(Fish[] fishes) {
		Fish[] copied=new Fish[17];
		for (int i = 1; i <=16; i++) {
			Fish cur=fishes[i];
			copied[i]=new Fish(cur.y,cur.x,cur.dir);
		}
		return copied;
	}
	
}