[코드트리 챌린지] ㅜㅜ 4주차

DP 니가 뭔데 .,,

볼때마다 새로운 DP썰이 시작합니다 ..

....
썰린건 나였다 ..이번주도

ㅜㅜㅜㅜ

왜 그대로냐 ,, 정말 !!!

근데 맞다 ,, 이번주 알고리즘 소홀히 했다..

그나저나 백트래킹 진짜 못한다

조금 오른거에 감사해야하나 ㅜ

dp를 하겠다는 초반 다짐과 다르게 나는 완전탐색 문제를 붙들고 털리고 있었다.
그 문제는 바로 금채굴하기
https://www.codetree.ai/missions/2/problems/gold-mining?&utm_source=clipboard&utm_medium=text

처음엔 마름모모양대로 탐색하는 걸 어떻게 해야할지 막막했는데

생각해보니 bfs로 최단거리로 찾으면 되지않나 싶었다.
몰라몰라,, 생각이 짧았다. 아래는 틀린 코드

import java.util.*;

public class Main {
    public static int N, M, gold, max, cnt, map[][],move[][];
    public static int[] dr = {-1,0,1,0};
    public static int[] dc = {0,1,0,-1};
    public static boolean visited[][];
    public static Queue<Node> q = new LinkedList<>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        map = new int[N][N];
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                map[i][j] = sc.nextInt();
                if(map[i][j]==1){
                    gold++;
                }
            }
        }
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                visited = new boolean[N][N];
                push(i,j);
                Max_gold();
            }
        }
        System.out.println(max);
    }

    public static void push(int x,int y){
        visited[x][y] = true;
        q.add(new Node(x,y));
    }

    public static void Max_gold(){
        for(int t=N-1;t>=0;t--){
            if(t!=0 && gold*M < cost(t)){continue;}
            visited = new boolean[N][N];
            move = new int[N][N];
            cnt = 0;
            while(!q.isEmpty()){
                Node now = q.poll();
                visited[now.x][now.y] = true;
                if(move[now.x][now.y]> t){continue;}
                if(map[now.x][now.y]==1){cnt++;}
                for(int i=0;i<4;i++){
                    int nx = now.x + dr[i];
                    int ny = now.y + dc[i];
                    if(canGo(nx,ny)){
                        move[nx][ny] = move[now.x][now.y] + 1;
                        push(nx,ny);
                    }
                }
            }
            int tmp = cnt*M;
            if(tmp >= cost(t)){
                max = Math.max(max,cnt);
            }
            cnt = 0;
        }
    }

    public static int cost(int x){
        return x * x + ( x + 1) * (x + 1);
    }

    public static boolean isRange(int x,int y){
        return 0 <= x && x < N && 0 <= y && y < N;
    }
    public static boolean canGo(int x,int y){
        if(!isRange(x,y)){return false;}
        if(visited[x][y]){return false;}
        return true;
    }

    static class Node {
        int x, y;
        public Node(int x,int y){
            this.x = x;
            this.y = y;
        }
    }
}

첫번째 문제는 내가 0을 곱해놓고 제대로 된 대소비교를 바라는게 문제였고

두번째 문제는 내가 마름모의 크기를 가능한 큰것부터 작은것으로 좁혀나갔는데 한번 크게 탐색해놓고 그 이후 작은 마름모의 시작노드를 안넣고 큐를 계속 돌려서 값이 제대로 안나왔었다. 그래서 한칸짜리의 탐색이 제대로 안됨

이틀을 이것때문에 스트레스받다가 결국 찾고 사이다 먹었다 ㅜㅜ

import java.util.*;

public class Main {
    public static int N, M, gold, max, cnt, map[][],move[][];
    public static int[] dr = {-1,0,1,0};
    public static int[] dc = {0,1,0,-1};
    public static boolean visited[][];
    public static Queue<Node> q = new LinkedList<>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        map = new int[N][N];
        visited = new boolean[N][N];
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                map[i][j] = sc.nextInt();
                if(map[i][j]==1){
                    gold++;
                }
            }
        }
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                push(i,j);
                Max_gold();
            }
        }
        System.out.println(max);
    }

    public static void push(int x,int y){
        visited[x][y] = true;
        q.add(new Node(x,y));
    }

    public static void Max_gold(){
        Node th = q.poll();
        for(int t=N-1;t>=0;t--){
            if(gold*M < cost(t) && t!=0){continue;}
            visited = new boolean[N][N];
            move = new int[N][N];
            cnt = 0;
            q.add(th);
            while(!q.isEmpty()){
                Node now = q.poll();
                visited[now.x][now.y] = true;
                if(move[now.x][now.y] <= t && map[now.x][now.y]==1){cnt++;}
                if(move[now.x][now.y]> t){
                    continue;}
                for(int i=0;i<4;i++){
                    int nx = now.x + dr[i];
                    int ny = now.y + dc[i];
                    if(canGo(nx,ny)){
                        move[nx][ny] = move[now.x][now.y] + 1;
                        push(nx,ny);
                    }
                }
            }
            int tmp = cnt*M;
            if(tmp >= cost(t)){
                max = Math.max(max,cnt);
            }
            cnt = 0;
        }
    }

    public static int cost(int x){
        return x * x + ( x + 1) * (x + 1);
    }

    public static boolean isRange(int x,int y){
        return 0 <= x && x < N && 0 <= y && y < N;
    }
    public static boolean canGo(int x,int y){
        if(!isRange(x,y)){return false;}
        if(visited[x][y]){return false;}
        return true;
    }

    static class Node {
        int x, y;
        public Node(int x,int y){
            this.x = x;
            this.y = y;
        }
    }
}