글 읽기 - 제발 도와주세요 ㅠㅠ..... 고수님들...

le_effort 2년 전 0

예제 4번부터 값이 틀리게 나오는데 도저히 어디가 잘못된건지 감을 못잡겠습니다.....

정말 풀고싶어요 도와주시면 감사하겠습니다 ㅠㅠㅠ

import java.io.*;
import java.util.*;
public class Main {
    static int m,s;
    static Node map[][] = new Node[5][5];
    static int fdx[] = { 0, 0, -1, -1, -1, 0, 1, 1, 1 };
    static int fdy[] = { 0, -1, -1, 0, 1, 1, 1, 0, -1 };
    static Node copyMap [][];
    static boolean visited [][];
    static ArrayList<SharkMoveInfo> tmp_moveInfos = new ArrayList<>();
    static ArrayList<SharkMoveInfo> moveInfos = new ArrayList<>();
    static int sdx[] = { 0, -1, 0, 1, 0 };
    static int sdy[] = { 0, 0, -1, 0, 1 };
    static int max =-1;

    static ArrayList<FishInfo> fishInfos;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 입력
        String [] t=  br.readLine().split(" ");
        m = Integer.parseInt(t[0]);
        s=  Integer.parseInt(t[1]);

        for(int i=1; i<=4; i++){
            for(int j=1; j<=4; j++){
                map[i][j] = new Node();
            }
        }

        for(int i=0; i<m; i++){
            t = br.readLine().split(" ");
            map[Integer.parseInt(t[0])][Integer.parseInt(t[1])].fish.add(Integer.parseInt(t[2]));
        }

        t = br.readLine().split(" ");
        map[Integer.parseInt(t[0])][Integer.parseInt(t[1])].isShark = true;

        for(int i=0; i<s; i++){
            decreaseFishSmell();
            copyMapMagic();
            moveFish();
            moveShark();
            removeFishSmell();
            completeCopyMagic();
        }
        int ans = 0;

        for(int i=1; i<=4; i++){
            for(int j=1; j<=4; j++){
                ans+=map[i][j].fish.size();
            }
        }
        System.out.println(ans);
    }
    public static void print(){
        System.out.println("물고기 수");
        for(int i=1; i<=4; i++){
            for(int j=1; j<=4; j++){
                System.out.print(map[i][j].fish.size()+" ");
            }
            System.out.println();
        }
    }
    public static void decreaseFishSmell(){
        for(int i=1; i<=4; i++){
            for(int j=1; j<=4; j++){
                if(map[i][j].isSmell){
                    map[i][j].smellCnt--;
                }
            }
        }
    }
    public static void completeCopyMagic(){
        for(int i=1; i<=4; i++){
            for(int j=1; j<=4; j++){
                for(int k=0; k<copyMap[i][j].fish.size(); k++){
                    map[i][j].fish.add(copyMap[i][j].fish.get(k));
                }
            }
        }
    }
    public static void removeFishSmell(){

        for(int i=1; i<=4; i++){
            for(int j=1; j<=4; j++){
                if(map[i][j].isSmell && map[i][j].smellCnt ==0){
                    map[i][j].isSmell = false;
                }
            }
        }
    }
    public static void moveShark(){

        int sx=0;
        int sy =0;

        // 상어가 있는 칸 찾기
        for(int i=1; i<=4; i++){
            for(int j=1; j<=4; j++){
                if(map[i][j].isShark){
                    map[i][j].isShark = false;
                    sx=i;
                    sy=j;
                    break;
                }
            }
        }

        visited = new boolean[5][5];
        // 상어 이동
        dfs(0,sx,sy);

        // 상어가 이동한 경로에 있는 물고기 삭제

        for(int i=0; i<moveInfos.size(); i++){
            SharkMoveInfo s= moveInfos.get(i);
            if(map[s.x][s.y].fish.size()!=0){
                map[s.x][s.y].fish.clear();
                map[s.x][s.y].isSmell = true;
                map[s.x][s.y].smellCnt = 2;
            }
            if(i==2){
                map[s.x][s.y].isShark = true;
            }
        }

    }
    public static void dfs(int level,int x, int y){
        if(level ==3){
            int sum = 0;
            visited = new boolean[5][5];

            for(SharkMoveInfo s : tmp_moveInfos){
                if(!visited[s.x][s.y]){
                    visited[s.x][s.y] = true;
                    sum+=map[s.x][s.y].fish.size();
                }
            }

            if(max < sum){
                moveInfos.clear();
                max = sum;
                for(SharkMoveInfo s : tmp_moveInfos){
                    moveInfos.add(new SharkMoveInfo(s.x,s.y,s.dir));
                }
            }
            return;
        }

        for(int i=1; i<=4; i++){
            int nx = x+sdx[i];
            int ny = y+sdy[i];
            if(!isRange(nx,ny)) continue;

            tmp_moveInfos.add(new SharkMoveInfo(nx,ny,i));
            dfs(level+1,nx,ny);
            tmp_moveInfos.remove(tmp_moveInfos.size()-1);
        }
    }
    public static void moveFish(){
        fishInfos = new ArrayList<>();
        // 모든 물고기 이동
        for(int i=1; i<=4; i++){
            for(int j=1; j<=4; j++){

                for(int k=0; k<map[i][j].fish.size(); k++){

                    int dir = map[i][j].fish.get(k);    // 이동할 물고기의 원래 방향
                    int beforeDir = dir;

                    // 물고기가 들어갈 방향 찾기
                    for(int l=1; l<=8; l++){
                        int nx = i+fdx[dir];
                        int ny = j+fdy[dir];
                        if(isRange(nx,ny) && !map[nx][ny].isSmell && !map[nx][ny].isShark){


                            fishInfos.add(new FishInfo(i,j,beforeDir,nx,ny,dir));
                            break;
                        }
                        dir-=1;
                        if(dir==0) dir=8;
                    }

                }
            }
        }

        // 이동한 물고기 위치에 넣어주기
        for(int i=0; i<fishInfos.size(); i++){
            FishInfo fishInfo = fishInfos.get(i);

            for(int j=0; j<map[fishInfo.bx][fishInfo.by].fish.size(); j++){
                if(map[fishInfo.bx][fishInfo.by].fish.get(j) == fishInfo.bdir){
                    map[fishInfo.bx][fishInfo.by].fish.remove(j);
                    map[fishInfo.nx][fishInfo.ny].fish.add(fishInfo.ndir);
                    break;
                }
            }
        }
    }
    public static void copyMapMagic(){
         copyMap = new Node[5][5];
        for(int i=1; i<=4; i++){
            for(int j=1; j<=4; j++){
                copyMap[i][j] = new Node();
            }
        }

        for(int i=1; i<=4; i++){
            for(int j=1; j<=4; j++){
                for(int k=0; k<map[i][j].fish.size(); k++){
                    copyMap[i][j].fish.add(map[i][j].fish.get(k));
                }
            }
        }

    }
    public static boolean isRange(int x, int y){
        if(x>=1 && y>=1 && x<=4 && y<=4) return true;
        return false;
    }
}
class Node{
    boolean isShark;
    boolean isSmell;
    int smellCnt;
    ArrayList<Integer> fish = new ArrayList<>();
}
class FishInfo{
    int bx,by,bdir,nx,ny,ndir;

    public FishInfo(int bx, int by, int bdir, int nx, int ny, int ndir) {
        this.bx = bx;
        this.by = by;
        this.bdir = bdir;
        this.nx = nx;
        this.ny = ny;
        this.ndir = ndir;
    }
}
class SharkMoveInfo{
    int x,y,dir;

    public SharkMoveInfo(int x, int y, int dir) {
        this.x = x;
        this.y = y;
        this.dir = dir;
    }
}

kdh6429 2년 전 0

상어의 이동 방법 중 사전 순 정의는 어디에 있나요?

le_effort 2년 전 0

dfs를 탈 때 같은 점수일 경우 사전 순으로 정의하는데

dfs를 사전순 정의 순서대로 시행해서 같은 점수 일 경우에는 먼저 dfs를 탄 부분이 사전순으로 앞서는 부분이므로 따로 하지는 않았습니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

제발 도와주세요 ㅠㅠ..... 고수님들...

le_effort 2년 전 0

kdh6429 2년 전 0

le_effort 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말