글 읽기 - 분명 Set에 객체 저장하는데 중복이 허용됩니다..

frtt0608 3년 전 0

1. 처음에 setArcher함수로 궁수 배치합니다.

2. defenseCastle로 성을 지키면서

3. attackEnemy함수에 que를 사용해 적을 잡는데.

4. map을 복사한 copy_map에서 적을 잡으면 killEnemySet이라는 set에 저장하는데 이상하게 중복이 허용되면서 저장이 됩니다..

혹시 사용자 정의 클래스로 만든 객체라서 중복으로 판단하지 않는건지...

추가로 system.arraycopy로 map을 복사해서 사용할려했는데 map이 자꾸 업데이트되서 결국 이중 for문으로 해결했습니다..

제가 알기론 system.arraycopy가 deepcopy로 배열 복사하는 걸로 알고있는데 상황마다 틀린건가요..??

import java.util.*;
import java.io.*;

/**
 * Main
 */

// 궁수 3명 배치
// 궁수는 동시에 공격, 가장 왼쪽에 적 공격, 같은 적 공격 가능
// 1. 궁수 배치
// 2. 게임 진행
// 3. 가장많이 잡은 적군 수 출력.

public class Main {
    static int N, M, D, map[][], maxKill;

    static public class Node {
        int x;
        int y;
        int dist;

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

        Node(int x, int y, int dist) {
            this.x = x;
            this.y = y;
            this.dist = dist;
        }
    }

    static public boolean wall(int x, int y) {
        if(x>=N || x<0 || y>=M || y<0) return true;
        return false;
    }
    
    static public int[][] downEnemy(int copy_map[][]) {
        int temp_map[][] = new int[N][M];

        for(int i=0; i<N-1; i++) {
            for(int j=0; j<M; j++) {
                if(copy_map[i][j]==1) temp_map[i+1][j] = 1;        
            }
        }

        return temp_map;
    }

    static public void setArcher(int cnt, int idx, boolean visited[]) {
        if(cnt==3) {
            defenseCastle(visited);
            return;
        }
        
        if(idx >= M) return;

        visited[idx] = true;
        setArcher(cnt+1, idx+1, visited);
        visited[idx] = false;
        setArcher(cnt, idx+1, visited);
    }

    static public boolean checkMap(int copy_map[][]) {
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                if(copy_map[i][j]==1) return false;
            }
        }

        return true;
    }

    static public Set<Node> attackArcher(ArrayList<Integer> archerList, int copy_map[][]) {
        Set<Node> killEnemySet = new HashSet<>();
        int[] dx = {0,-1,0}, dy={-1,0,1};

        for(Integer archer: archerList) {
            Queue<Node> que = new LinkedList<>();
            que.offer(new Node(N, archer, 0));
            
            loop:
            while(!que.isEmpty()) {
                Node n = que.poll();
                
                if(n.dist >= D) continue;

                for(int dir=0; dir<3; dir++) {
                    int nx = n.x + dx[dir];
                    int ny = n.y + dy[dir];
                    if(wall(nx, ny)) continue;
                    if(copy_map[nx][ny]==1) {
                        killEnemySet.add(new Node(nx, ny));
                        break loop;
                    }
                    que.offer(new Node(nx, ny, n.dist+1));
                }
            }
        }

        return killEnemySet;
    }

    static public void defenseCastle(boolean visited[]) {
        
        int copy_map[][] = new int[N][M];
        int killCnt = 0;
        
        ArrayList<Integer> archerList = new ArrayList<>();
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                copy_map[i][j] = map[i][j];
            }
        }

        for(int i=0; i<M; i++) {
            if(visited[i]) archerList.add(i);
        }

        for(int turn=0; turn<N; turn++) {
            System.out.println("turn :" + turn);
            Set<Node> killEnemySet = new HashSet<>();
            if(checkMap(copy_map)) break;

            killEnemySet = attackArcher(archerList, copy_map);
            if(killEnemySet.size()==0) continue;
            Iterator<Node> setIter = killEnemySet.iterator();

            while(setIter.hasNext()) {
                Node kill = setIter.next();
                System.out.println(kill.x + "," + kill.y);
            }

            killCnt += killEnemySet.size();
            for(Node kill: killEnemySet) {
                copy_map[kill.x][kill.y] = 0;
            }

            copy_map = downEnemy(copy_map);
        }

        maxKill = Math.max(maxKill, killCnt);
    }



    static public void main(String args[]) throws IOException {
        System.setIn(new FileInputStream("input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        D = Integer.parseInt(st.nextToken());
        boolean visited[] = new boolean[M];
        map = new int[N][M];

        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        setArcher(0, 0, visited);

        System.out.println(maxKill);
    }
}

bupjae 3년 전 1

java 에서 hash 기반의 컬렉션을 이용하려면 컬렉션에 넣으려는 원소 (여기서는 Node) 의 equals() 와 hashCode() 가 올바르게 재정의되어야 합니다.

equals() 는 다음 조건을 만족해야 합니다.

* a.equals(a) == true

* a.equals(b) == b.equals(a)

* a.equals(b) == true 이고 b.equals(c) == true 이면 a.equals(c) == true

hashCode() 는 다음 조건을 만족해야 합니다.

* a.equals(b) == true 이면 a.hashCode() == b.hashCode()

* a.equals(b) == false 일 때 a.hashCode() != b.hashCode() 를 만족하면 컬렉션 성능이 좋아집니다.

frtt0608 3년 전 0

아... hashCode를 생각못했네요...ㅠㅠ
감사합니다!!

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

문제

문제

출처

ICPC

분명 Set에 객체 저장하는데 중복이 허용됩니다..

frtt0608 3년 전 0

bupjae 3년 전 1

frtt0608 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말