[백준] 19236 - 청소년 상어

[백준] 19236 - 청소년 상어

[문제링크]

0. 백트래킹 / 구현 문제

1. 백트래킹을 위하여, 상어의 각 이동 단계마다 map과 물고기 방향 정보를 저장한다

2. 해당 상황에서 물고기 이동 - 가능한 모든 상어 이동에 대해 재귀를 돌린 다음, 저장해둔 정보를 복원하고 이전 단계로 돌아간다

3. 각 재귀 단계에서 먹은 물고기 번호의 합을 저장, 더이상 진행 불가능할때 전역변수인 maxEat과 비교, 갱신한다

import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main{ static int[][] dir = { {-1,0},{-1,-1},{0,-1},{1,-1}, {1,0},{1,1},{0,1},{-1,1} }; static int maxEat=0; static boolean[] deadFish; static int[][] fish; static int[][] map; public static void main(String[] args)throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); map = new int[4][4]; fish = new int[17][3]; deadFish = new boolean[17]; for (int i = 0; i < 4; i++) { StringTokenizer st = new StringTokenizer(br.readLine()); for (int j = 0; j < 4; j++) { int num = pint(st.nextToken()); int dir = pint(st.nextToken()); map[i][j]=num; fish[num][0]=i; fish[num][1]=j; fish[num][2]=dir-1; } } //fish[0] = shark deadFish[map[0][0]]=true; maxEat+=map[0][0]; fish[0][2] = fish[ map[0][0] ][2]; map[0][0]=-1; rec(maxEat); System.out.println(maxEat); } static void rec(int eat) { //comparemaxEat if(maxEat=4 || nY>=4 || map[nX][nY]==-1) { curDir= (curDir+1)%8; continue; } //swap int tmp = map[nX][nY]; map[nX][nY]=map[curX][curY]; map[curX][curY]=tmp; fish[i][0]=nX;fish[i][1]=nY; fish[i][2]=curDir; if(tmp!=0) { fish[tmp][0]=curX; fish[tmp][1]=curY; } break; } } //shark move //eat map[ fish[0][0] ][ fish[0][1] ]=0;//빈 공간화 while(true) { fish[0][0]+=dir[fish[0][2]][0]; fish[0][1]+=dir[fish[0][2]][1]; if(fish[0][0]<0 || fish[0][0]>=4 || fish[0][1]<0 || fish[0][1]>=4) { break; } if(map[fish[0][0]][fish[0][1]]==0)continue; int tmp = map[ fish[0][0] ][ fish[0][1] ]; map[ fish[0][0] ][ fish[0][1] ]=-1; deadFish[tmp]=true; int tmpShakeDir = fish[0][2]; fish[0][2]=fish[tmp][2]; rec(eat+tmp); fish[0][2]=tmpShakeDir; map[ fish[0][0] ][ fish[0][1] ]=tmp; deadFish[tmp]=false; } //return //restore for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { map[i][j]=tmpMap[i][j]; } } for (int i = 0; i < 17; i++) { fish[i][0]=tmpFish[i][0]; fish[i][1]=tmpFish[i][1]; fish[i][2]=tmpFish[i][2]; deadFish[i]=tmpDeadFish[i]; } return; } static int pint(String s) { return Integer.parseInt(s); } }

결과 화면

from http://nato-blog.tistory.com/144 by ccl(S) rewrite - 2021-11-04 07:27:45