[JAVA] 백준 청소년 상어

첫번째 상어 먹고, 물고기 움직인 결과

 

 

처음에 시도했던 코드는 아래와같다.

처음엔 시도하던 코드

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

class Main {
    static int sharkX, sharkY, sharkD;

    static int eaten = 0;
    static int[][] a = new int[4][4];
    static int[][] dir = new int[4][4];
    static int[] dirx = {0, 0, -1, -1, -1, 0, 1, 1, 1};//index=0일때는 0,0
    static int[] diry = {0, -1, -1, 0, 1, 1, 1, 0, -1};
    static Stack<Integer> eatenList = new Stack<>();
    static int max = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        for (int i = 0; i < 4; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 4; j++) {
                a[i][j] = Integer.parseInt(st.nextToken());
                dir[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        eat(0, 0);//시작
        fishMove();

        System.out.println(max);
    }

    static void sharkMove() {
        int x = sharkX;
        int y = sharkY;
        int d = sharkD;
        x = x + dirx[d];
        y = y + diry[d];
        int count = 0;
        while (x >= 0 && y >= 0 && x < 4 && y < 4) {//범위 내에서만
            Stack<Integer> stackBefore = new Stack<>();
            for (int l : eatenList) stackBefore.add(l);
            int eatenBefore = eaten;
            int[][] aBefore = new int[4][4];
            int[][] dirBefore = new int[4][4];
            for (int i = 0; i < 4; i++) System.arraycopy(a[i], 0, aBefore[i], 0, 4);
            for (int i = 0; i < 4; i++) System.arraycopy(dir[i], 0, dirBefore[i], 0, 4);

            if (eat(x, y)) {//갈수있으면 먹고
                fishMove();
                count++;
            }
            for (int i = 0; i < 4; i++) System.arraycopy(aBefore[i], 0, a[i], 0, 4);
            for (int i = 0; i < 4; i++) System.arraycopy(dirBefore[i], 0, dir[i], 0, 4);
            eaten = eatenBefore;
            eatenList = new Stack<Integer>();
            for (int l : stackBefore) eatenList.add(l);
            x = x + dirx[d];
            y = y + diry[d];
        }
        int sum = 0;
        for (int s : eatenList) sum += s;

        if (count == 0) {
            max = Math.max(max, sum);//갈수있는곳이 아무곳도 없을때만 최대값 계산
        }
    }

    static boolean eat(int x, int y) {
        if (a[y][x] != 0) {//갈수있으면
            sharkX = x;//상어위치x
            sharkY = y;//상어위치y
            eaten += a[y][x];//먹어
            eatenList.add(a[y][x]);
            sharkD = dir[y][x];//방향설정
            a[y][x] = 0;//해당위치 초기화
            dir[y][x] = 100;
            dir[y][x] = 100;
            return true;
        } else {
            return false;
        }
    }

    static void fishMove() {
        for (int findNum = 1; findNum <= 16; findNum++) {

            boolean eatenpass = false;
            for (int l = 0; l < eatenList.size(); l++) {
                if (findNum == eatenList.get(l)) eatenpass = true;
            }

            if (eatenpass) continue;//먹힌거는 빼야죠


            int fx = 0, fy = 0, fd = 0, fnum = 0;
            boolean findOK = false;
            for (int i = 0; i < 4; i++) {
                for (int j = 0; j < 4; j++) {
                    if (a[i][j] == findNum) {
                        fx = j;
                        fy = i;
                        fd = dir[i][j];
                        fnum = a[i][j];
                        findOK = true;
                        break;
                    }
                }
                if (findOK) break;
            }
            int dx = 0, dy = 0;
            for (int i = 0; i < 8; i++) {//상어가 있거나, 공간의 경계를 넘는 칸이다.
                dx = fx + dirx[fd];
                dy = fy + diry[fd];
                if (boundaryCheck(dx, dy) && a[dy][dx] != 0) break;
                else {
                    fd = fd + 1;
                    if (fd == 9) fd = 1;
                }
            }//갈수있는칸 찾았으면 아래실행
            dir[fy][fx] = fd;
            swap(fx, fy, dx, dy);
        }

        sharkMove();
    }

    static boolean boundaryCheck(int bx, int by) {
        return bx >= 0 && by >= 0 && bx < 4 && by < 4;
    }

    static void swap(int x, int y, int dx, int dy) {
        int temp = a[y][x];
        a[y][x] = a[dy][dx];
        a[dy][dx] = temp;

        temp = dir[y][x];
        dir[y][x] = dir[dy][dx];
        dir[dy][dx] = temp;
    }
}

 

https://haerang94.tistory.com/388

[백준] 19236번 청소년 상어 (java, 시뮬레이션)

위 블로그에서 코드를 참고하였다.

 

달랐던점은 문제에서 상어가 지나가고 난 빈 칸에도 움직일수 있게 만들라고 했는데 그 사항을 고려하지 않았었다.

그리고 객체배열을 만들어서 물고기의 좌표값을 모두 집어넣었다.

 

moveFish메소드 , getFishList메소드 , moveShark메소드 로 크게 나누고, copiedMap, copiedFish로 세부적으로 나누었다.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.concurrent.ForkJoinPool;

class Fish{
    int y;
    int x;
    int dir;
    int sum;
    public Fish(int y, int x, int dir) {
        super();
        this.y = y;
        this.x = x;
        this.dir = dir;
    }

    public Fish(int y, int x, int dir,int sum) {
        super();
        this.y = y;
        this.x = x;
        this.dir = dir;
        this.sum=sum;
    }

}


class Main {
    static int[] ypos= {-1,-1,0,1,1,1,0,-1};//↑, ↖, ←, ↙, ↓, ↘, →, ↗
    static int[] xpos= {0,-1,-1,-1,0,1,1,1};
    static int answer;

    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int[][] map=new int[4][4];
        Fish shark; //상어~
        Fish[] fishes=new Fish[17];//방향정보 저장

        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                int a=sc.nextInt();
                int b=sc.nextInt();
                map[i][j]=a;//물고기 번호
                fishes[a]=new Fish(i,j,b-1);
            }
        }
        int num=map[0][0];//물고기번호
        shark=new Fish(0,0,fishes[num].dir,num);//0,0
        fishes[num].dir=-1;//잡아 먹힘 표시
        map[0][0]=0;//물고기 먹음


        moveShark(map,shark,fishes);

        System.out.println(answer);
    }

    private static ArrayList<Fish> getFishList(int[][] map,Fish shark,Fish[] fishes){

        ArrayList<Fish> list=new ArrayList<>();
        Queue<Fish> q=new LinkedList<Fish>();
        q.add(shark);
        while(q.size()!=0) {
            Fish cur=q.poll();
            int y=cur.y;
            int x=cur.x;
            int d=cur.dir;
            int yy=y+ypos[d];
            int xx=x+xpos[d];
            if(xx<0 || yy<0 || xx>=4 || yy>=4)continue;
            if(map[yy][xx]==0) {//빈 칸이동
                q.add(new Fish(yy,xx,d));
            }else {
                int num=map[yy][xx];
                list.add(new Fish(yy,xx,fishes[num].dir));
                q.add(new Fish(yy,xx,d));
            }

        }
        return list;
    }

    private static void moveShark(int[][] map,Fish shark,Fish[] fishes) {
        if(answer<shark.sum)answer=shark.sum;

        moveFish(map,shark,fishes);//물고기 이동
        // 상어이동
        //상어가 먹을 물고기 리스트
        ArrayList<Fish> list=getFishList(map, shark, fishes);

        for (int i = 0; i < list.size(); i++) {
            int[][] copy=copiedMap(map);
            Fish[] cfishes=copiedFish(fishes);
            Fish cur=list.get(i);
            int num=copy[cur.y][cur.x];

            //이번 물고기 먹음
            copy[cur.y][cur.x]=0;
            Fish newShark=new Fish(cur.y,cur.x,cur.dir,shark.sum+num);//먹은 물고기의 방향으로 전환됨
            cfishes[num].dir=-1;
            moveShark(copy,newShark,cfishes);// dfs 돌리기
        }
    }


    //	물고기 이동
    private static void moveFish(int[][] map,Fish shark,Fish[] fishes) {


        for (int num = 1; num <= 16; num++) {//번호 작은 물고기부터
            if(fishes[num].dir==-1)continue;
            int d=fishes[num].dir;//원래 방향
            int y=fishes[num].y;
            int x=fishes[num].x;

            while(true) {

                int yy=y+ypos[d];
                int xx=x+xpos[d];
//				범위 벗어남
                if(xx<0 || yy<0 || xx>=4 || yy>=4) {
                    d=(d+1)%8;
                    if(d==fishes[num].dir)break;//원래 방향으로 되돌아오면 더이상 갈 곳 없음  break
                    continue;
                }
//				상어있는 곳 못감
                if(xx==shark.x && yy==shark.y) {
                    d=(d+1)%8;
                    if(d==fishes[num].dir)break;//원래 방향으로 되돌아오면 더이상 갈 곳 없음  break
                    continue;
                }

                if(map[yy][xx]==0) {//빈칸
                    map[yy][xx]=num;
                    map[y][x]=0;
                    fishes[num]=new Fish(yy,xx,d);
                    break;
                }else {//물고기 있는 칸
                    int temp=map[yy][xx];
                    map[yy][xx]=num;
                    map[y][x]=temp;
                    fishes[num].y=yy;
                    fishes[num].x=xx;
                    fishes[num].dir=d;//방향전환하는 애라서 갱신
                    fishes[temp].y=y;
                    fishes[temp].x=x;
                    break;
                }

            }

        }

    }

    private static int[][] copiedMap(int[][] map){
        int[][] copied=new int[4][4];
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                copied[i][j]=map[i][j];
            }
        }
        return copied;
    }

    private static Fish[] copiedFish(Fish[] fishes) {
        Fish[] copied=new Fish[17];
        for (int i = 1; i <=16; i++) {
            Fish cur=fishes[i];
            copied[i]=new Fish(cur.y,cur.x,cur.dir);
        }
        return copied;
    }

}

moveFish메소드 getFishList메소드 moveShark메소드 로 크게 나누고, copiedMap, copiedFish로 세부적으로 나누었다.