BOJ - 19236 ) 청소년상어

 

 

---

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

19236번: 청소년 상어

---

상어의 움직이는 칸수 ( 최대 3칸 ) 에따라서 DFS를 구현하면 풀리는 문제이다.

매 DFS STEP마다 최댓값을 갱신하여준다.

---

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


public class 청소년상어 {

	public static class shark{
		int y,x,dir,num;
		boolean isLive;
		public shark(int y, int x, int dir, int num, boolean isLive) {
			this.y = y;
			this.x = x;
			this.dir = dir;
			this.num = num;
			this.isLive = isLive; 
			// 좌표 , 방향 , 숫자, 살아있는지?
		}
	}
	public static int dir[][] = { {-1,0} , {-1,-1} ,{0,-1} , {1,-1}, {1,0} , {1,1} , {0,1},{-1,1} }; // +1 %8
	public static int answer  = 0;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		shark [][] map = new shark[4][4];
		for(int i = 0 ; i < 4 ; i ++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j = 0 ; j < 4 ; j ++) {
				int snum = Integer.parseInt(st.nextToken());
				int sdir = Integer.parseInt(st.nextToken());
				map[i][j] = new shark(i, j, sdir-1, snum,true);
			}
		}// init map
		map[0][0].isLive= false;
		DFS(0,0,map[0][0].dir , map[0][0].num, map);
		System.out.print(answer);
		
	}
	private static void DFS(int y, int x, int mdir, int score, shark[][] map) {
		answer = answer > score ? answer : score;
		//맵 복사
		shark[][] cmap = new shark[4][4];
		for(int i = 0 ; i < 4 ; i ++) {
			for(int j = 0 ; j < 4 ; j++) {
				cmap[i][j] = new shark(map[i][j].y, map[i][j].x, map[i][j].dir, map[i][j].num,map[i][j].isLive);
				}
			}

		//물고기의 이동 
		for(int i = 1 ; i <=16 ; i++) {
			for(int j = 0 ; j < 16 ; j++) {
				if(cmap[j/4][j%4].num ==i && cmap[j/4][j%4].isLive) {
					
					int nowy = cmap[j/4][j%4].y;
					int nowx = cmap[j/4][j%4].x;
					int nowdir = cmap[j/4][j%4].dir;
					int nownum = cmap[j/4][j%4].num;
					int next = 0;
					
					while(true) {
						nowdir += next;
						nowdir %=8;
						int ny = nowy + dir[nowdir][0];
						int nx = nowx + dir[nowdir][1];
						if(ny <4 && nx <4 && nx>=0 && ny>=0 && !(ny==y&&nx==x)) {
							if(cmap[ny][nx].isLive) {
					
								int tempnum = cmap[ny][nx].num;
								int tempdir = cmap[ny][nx].dir;
								
							
								cmap[nowy][nowx].dir = tempdir;
								cmap[nowy][nowx].num = tempnum;
								
							
								cmap[ny][nx].dir = nowdir;
								cmap[ny][nx].num = nownum;
								
							} else {
							
								cmap[ny][nx].dir = nowdir;
								cmap[ny][nx].num = nownum;
								cmap[ny][nx].isLive = true;
								cmap[nowy][nowx].isLive=false;
							}
							break;
						}
						next=1;
						if(next>=8)break;
					}
					break;
				}
			}
		}
		
		
		//상어의 이동 - 최대로 움직여봤자 3칸
		
		for(int i = 1 ; i < 4; i++) {
			int ny = y + dir[mdir][0]*(i);
			int nx = x + dir[mdir][1]*(i);
			if(ny<4 && nx <4 && nx >=0 && ny >=0 && cmap[ny][nx].isLive) {
				//범위에있고 먹을수있는거
				cmap[ny][nx].isLive= false;
				DFS(ny,nx,cmap[ny][nx].dir , score + cmap[ny][nx].num , cmap);
				cmap[ny][nx].isLive = true;
			}
		}
	}
}

---