[ 백준 19236] 청소년 상어 - Java

문제 링크

http://boj.kr/19236

19236번: 청소년 상어

문제 풀이

삼성 코딩테스트 기출문제입니다.

 

그 전에 나왔던 아기상어(http://boj.kr/16236)의 시리즈로 내놨나 봐요 ㅎㅎ

 

아기상어는 BFS로 푸는 문제였는데 요 청소년 상어는 문제에서 주어지는대로 이동시키는 시뮬레이션 문제로 보입니다!

 

어렵지는 않았지만 문제를 읽다보니 물고기가 없는 칸으로는 이동할 수 없다. 이부분이 있는데 이 부분을 잘 못 이해해서 물고기 없는칸 이후 방향으로는 탐색하지 않았는데, 그렇지 않고 없는칸은 넘어가고 계속 탐색을 해주어야 합니다.

 

이건 문제를 읽다보면 오해의 소지가 있지않나.. 생각이 드는데요. 바로 소스코드 올리겠습니다.

소스 코드

import java.util.Scanner;

class Fish {
	Integer num;
	int way;
	boolean dead;
	public Fish(int num, int way,boolean dead) {
		this.num = num;
		this.way = way;
		this.dead = dead;
	}

	public Fish clone() {
		return new Fish(num,way,dead);
	}

	@Override
	public String toString() {
		if(dead) return "["+num+" X]";
		return "["+num+" O]";
	}
}

public class Sol {
	static int [] dx = { -1, -1, 0 ,1,1,1, 0 , -1};
	static int [] dy = { 0 ,-1,-1,-1, 0, 1, 1, 1};
	static int max=0;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		Fish map [][] = new Fish[4][4];
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map.length; j++) {
				map[i][j] = new Fish(sc.nextInt(), sc.nextInt()-1,false);
			}
		}
		//크기가 굉장히 작음. 브루트포스 돌리면될듯하다.
		//상어가 이동해서 그자리의 물고기를 먹을수 있을때마다 분기
		//그를 위해서는 상어의 위치및 방향, 분기할때마다 map을 복사, 번호의 합을 가지면 될것 같다.
		eatFish(0, 0, -1, 0, map);
		System.out.println(max);

	}

	static void eatFish(int x,int y,int way,int sum,Fish [][] map ) {

		//상어가 물고기를 먹음.
		sum += map[x][y].num;
		way = map[x][y].way%8;
		map[x][y].dead = true;

		max = Math.max(max, sum);
		moveFish(map, x, y); //물고기 위치이동

		for(int d=1; d<4 ;d++) {

			int nx = x + dx[way]*d;
			int ny = y + dy[way]*d;

			if(nx<0||ny<0||nx>=4||ny>=4) break;
			if(map[nx][ny].dead) continue;

			Fish newMap [][] = new Fish[4][4]; // 새로 선언
			for (int i = 0; i < 4; i++) {
				for (int j = 0; j < 4; j++) {
					newMap[i][j] = map[i][j].clone();
				}
			}
			eatFish(nx, ny, way, sum, newMap); // 가능한 상어 위치 모두 분기
		}

	}

	static void moveFish(Fish [][] map,int x,int y) {

		//번호가 작은 물고기부터 이동해야함.
		int num = 1 ;

		while(num <= 16) {
			changePos(map, num++,x,y);
		}
	}

	static void changePos(Fish [][] map,int num, int x,int y) {
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map.length; j++) {
				if (map[i][j].num == num && !map[i][j].dead) {
					int cnt =0;
					while(cnt<8) {

						int way = map[i][j].way%8;
						int nx = i+dx[way];
						int ny = j+dy[way];

						if(!isRange(nx,ny) || (x == nx && y ==ny)) {
							map[i][j].way++;
							cnt ++;
							continue;
						}
						Fish temp = map[nx][ny];
						map[nx][ny] = map[i][j];
						map[i][j] = temp;

						return;
					}
				}
			}
		}
	}

	static boolean isRange(int x , int y) {
		if(x<0 || y<0 || x>=4 || y>=4)return false;
		return true;
	}
}