[Java] 백준 19236 청소년 상어

 

 

https://www.acmicpc.net/problem/19236

19236번: 청소년 상어

---

1. 접근방법

1.  문제를 읽어보면 딱히 어려운 설명은 없어서 천천히 읽어보고 이해한 후 풀어야 겠다고 생각함 

2.  물고기 이동 함수, 상어 재귀 함수, 딥카피 함수 3개가 있으면 편하겠다고 생각함

 

2. 어려웠던점

 

좌측 재귀타기전 우측 재귀탄후 돌아온 모습

좌측과 우측은 서로 독립적인 공간에서 작업하고 돌아오기에 같은 값으로 돌아와야했다. 하지만 그렇지 않았다...

객체를 생성하고 딥카피 할때 일반적인 2차원 배열처럼 복사를 수행하고 디버깅했는데 계속 값이 달랐다. 

아래는 일반적인 딥카피를 수행했을때이다.

private static fish[][] copyarrays(fish[][] ori) {
        fish temp[][]= new fish[4][4];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                temp[i][j] = ori[i][j];
            }
        }
        return temp;
    }

결과적으로 마지막으로 사용한 부분은 객체를 전부 새로 생성하는 방식으로 고칠 수 있었다.

수를 복사하는 부분은 일반적은 포문 2개를 통해 해결할 수 있었는데.

객체를 복사하는경우 주소가 복사돼 새로운 배열은 만들어 전달해주어도 문제가 발생했다.

private static fish[][] copyarrays(fish[][] ori) {
		fish temp[][]= new fish[4][4];
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				if(ori[i][j]==null) {
					temp[i][j] = null;
					continue;
				}
				temp[i][j] = new fish(ori[i][j].num, ori[i][j].dir);
			}
		}
		return temp;
	}

3. 실수한 부분

1. 물고기 방향 이동 불가능 한상태에서 반시계방향으로 방향을 틀어준 후 다시 방향을 원위치 하는것이아닌 이동한 방향을 고정적으로 가지고 가야하는 부분

 

전형적으로 문제 설명대로 안하고 당연히 이거겠지라고 생각한 내잘못이다.

문제를 좀 더 꼼꼼히 읽을 필요가 있다..

 

4. 코드

 

import java.io.*;
import java.util.*;
public class Main {
	static int row=4,col=4,res=0;
	static fish map[][] = new fish[4][4];
	//0 상 1 좌상 2 좌 3 좌하 4 하 5 우하 6 우 7 우상
	static int[][] dxdy = { {-1,-1,0,1,1,1,0,-1 }, {0,-1,-1,-1,0,1,1,1 } };
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		for (int i = 0; i < row; i++) {
			StringTokenizer stz = new StringTokenizer(br.readLine()," ");
			for (int j = 0; j < col; j++) {
				map[i][j] = new fish(Integer.parseInt(stz.nextToken()), Integer.parseInt(stz.nextToken())-1);
			}
		}
		
		int val = map[0][0].num;
		map[0][0] = new fish(17, map[0][0].dir );
		sharkfeed(copyarrays(map),val);
		// 불가능시 브레이크 및 출력
		// 가능 시 여러개면 모두 재귀
		// 하나면 바로 끝
		System.out.println(res);
		//물고기 번호 찾는 함수
		//물고기 이동시키는 함수
		//상어 이동시키는 변수
	}
	private static fish[][] copyarrays(fish[][] ori) {
		fish temp[][]= new fish[4][4];
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				if(ori[i][j]==null) {
					temp[i][j] = null;
					continue;
				}
				temp[i][j] = new fish(ori[i][j].num, ori[i][j].dir);
			}
		}
		return temp;
	}
	private static void sharkfeed(fish[][] temp,int value) {
		// 물고기 이동
		res = Math.max(res, value);
		
		findFish(1,temp);
		
 		// 상어 이동 가능 불가능?
out:	for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				if(temp[i][j]==null) continue;
				if(temp[i][j].num==17) {
					int nx=i,ny=j;
					fish[][] comp;
					while(true) {
						nx = nx+dxdy[0][temp[i][j].dir];
						ny = ny+dxdy[1][temp[i][j].dir];
						if(0<=nx && nx<row && 0<=ny && ny<col) {
							if(temp[nx][ny]==null) continue;
							comp = copyarrays(temp);
							comp[nx][ny]= new fish(temp[i][j].num, temp[nx][ny].dir);
//							comp[nx][ny].num = 17; // 
							comp[i][j]=null;
							sharkfeed(comp, value+temp[nx][ny].num);
							
						}else {
							break;
						}
					}
					break out;
				}
			}
		}
	}
	private static void findFish(int idx,fish[][] temp) {
		if(idx == 17) return;
		
	out: for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				if(temp[i][j]==null) continue;
				if(temp[i][j].num==idx) {
					moveFish(i,j,temp);
					break out;
				}
			}
		}
		findFish(idx+1,temp);
	}
	private static void moveFish(int x, int y,fish[][] temp) {
		// 이동
		// 8회 이동 후에도 움직이지 못하면 제자리
		// 상어 자리나 보드 벗어나면 다음 방향으로 변경
		//0 상 1 좌상 2 좌 3 좌하 4 하 5 우하 6 우 7 우상
		int cnt =0;
		int nx,ny;
		fish comp;
		while(true) {
			if(cnt==8) break;
			int dirr =(temp[x][y].dir+cnt)%8;
			nx = x+dxdy[0][dirr];
			ny = y+dxdy[1][dirr];
			if(0<=nx && nx<row && 0<=ny && ny<col ) {
				if(temp[nx][ny]==null) {
					temp[nx][ny] = temp[x][y];
					temp[nx][ny].dir = dirr;
					temp[x][y] = null;
					break;
				}
				if(temp[nx][ny].num!=17) {
					comp = temp[nx][ny];
					temp[nx][ny] = temp[x][y];
					temp[x][y] = comp;
					temp[nx][ny].dir = dirr;
					break;
				}
			}
			cnt++;
		}
	}
	static class fish{
		int num;
		int dir;
		public fish(int num, int dir) {
			super();
			this.num = num;
			this.dir = dir;
		}
		@Override
		public String toString() {
			return "["+num + " " + dir+"]";
		}
		
	}
}