[Java] BOJ 19236 청소년상어

[Java] BOJ 19236 청소년상어

 

www.acmicpc.net/problem/19236

19236번: 청소년 상어

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_19236_청소년상어 {
	static class Fish {
		int n, d;

		public Fish(int n, int d) {
			this.n = n;
			this.d = d;
		}
	}
	static class Shark {
		int x, y, d;
		
		public Shark(int x, int y, int d) {
			this.x = x;
			this.y = y;
			this.d = d;
		}
	}
	
	static Fish[][] grid = new Fish[4][4];
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		for (int i = 0; i < 4; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 4; j++) {
				int n = Integer.parseInt(st.nextToken());
				int d = Integer.parseInt(st.nextToken());
				grid[i][j] = new Fish(n, d);
			}
		}
		
		int eat = grid[0][0].n;
		grid[0][0].n = -1;
		solve(grid, eat, new Shark(0, 0, grid[0][0].d));
		
		System.out.println(MAX);
	} // main

	static int[][] dir = { {0, 0}, {-1, 0},{-1, -1},{0, -1},{1, -1},{1, 0},{1, 1},{0, 1},{-1, 1} };
	static int MAX = 0;
	private static void solve(Fish[][] grid, int SUM, Shark shark) {
		// 상어 이동 끝
		if(MAX < SUM) MAX = SUM;
				
		// 물고기 이동
		int num = 1;
		while(true) {
			if(num == 17) break;
			
		out:for (int i = 0; i < 4; i++) {
				for (int j = 0; j < 4; j++) {
					if(grid[i][j].n == num) {
						int cnt = 1;
						int nx = -1, ny = -1;
						while(true) {
							if(cnt == 9) break;

							nx = i + dir[grid[i][j].d][0];
							ny = j + dir[grid[i][j].d][1];
							
							if(!isInBound(nx, ny) || (shark.x == nx && shark.y == ny)) 
								grid[i][j].d = grid[i][j].d+1 == 9? 1 : grid[i][j].d+1;
							else {
								Fish tmp = grid[nx][ny];
								grid[nx][ny] = grid[i][j];
								grid[i][j] = tmp;
								break;
							}
							cnt++;
						}
						break out;
					}
				}
			}
			num++;
		} //while
		
		// 상어 이동
		int n = 1;
		while(true) {
			int nx = shark.x + (dir[shark.d][0] * n);
			int ny = shark.y + (dir[shark.d][1] * n);
			
			if(!isInBound(nx, ny)) break;
			if(grid[nx][ny].n != -1) {
				Fish[][] copy = copyGrid(grid);
				copy[nx][ny].n = -1;
				Shark newShark = new Shark(nx, ny, grid[nx][ny].d);
				solve(copy, SUM+grid[nx][ny].n, newShark);
			}
			n++;
		}
			
	} // solve
	
	static Fish[][] copyGrid(Fish[][] grid) {
		Fish[][] copy = new Fish[4][4];
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				Fish f = grid[i][j];
				copy[i][j] = new Fish(f.n, f.d);
			}
		}
		
		return copy;
	}
	static boolean isInBound(int x, int y) {
		if(x < 0 || x >= 4 || y < 0 || y >= 4) return false;
		
		return true;
	}
}

 

 

물고기의 방향과 번호를 기억하는 클래스 Fish,

상어의 위치와 방향을 기억하는 클래스 Shark 를 두었다.

 

맨 처음 무조건 0,0 에 상어가 위치하므로 미리 상어가 먹은 물고기번호에 추가해주고 grid[0][0] 의 물고기를 없앴다(-1처리)

 

solve 는 이 때까지 상어가 먹은 물고기번호 합인 SUM, 현재 상어상태, 현재 grid 상태를 매개변수로 들고다닌다.

 

1. solve에 처음 들어오면 SUM을 MAX와 비교하여 MAX를 업데이트했다.

 

2. 물고기를 이동해야하므로 1번부터 16번 물고기까지 모두 이동처리한다. 배열이 크지 않아서 난 그냥 번호 올라갈 때마다 이중 for문을 돌려 현재 물고기번호를 찾으면 가야하는 방향으로 이동시켰다.

물고기가 갈 수 없다면 방향에 +1를 했다.

 

3. 물고기를 다 이동시켰으니 상어를 이동시킨다.

상어 방향이 d라면 d방향으로 몇 칸이든 이동할 수 있으니 방향 d * n 을 해서

n을 1부터 배열범위 나갈 때까지 증가시키며 모두 이동해볼 수 있도록 했고

각 상어의 이동마다 solve() 재귀를 두는데 이 때 배열을 copy하여 매개변수를 넘겼다.

 

내가 오류 찾느라 해맸던 부분은.. grid가 Fish 객체 grid라서 단지

Fish[][] copy = new Fish[4][4];
for (int i = 0; i < 4; i++) {
  for (int j = 0; j < 4; j++) {
    copy[i][j] = grid[i][j];
  }
}

위처럼 하면 객체 주소 복사되어 원래 grid까지 바뀐다..

 

이걸 실수해서

Fish[][] copy = new Fish[4][4];
for (int i = 0; i < 4; i++) {
  for (int j = 0; j < 4; j++) {
    Fish f = grid[i][j];
    copy[i][j] = new Fish(f.n, f.d);
  }
}

위처럼 바꾸어 통과했당