글 읽기 - 97% 실패

kimby469 3년 전 1

97% 이후로 실패가 있는데...

어떤 반례가 있는지 찾지 못해 이렇게 글을 남기게 되었습니다.

combination 조합으로 해당 바이러스 m개를 뽑은 후 m개를 다 뽑은 후에

전염을 시켜보는데 해당 -2 인 부분이 바이러스가 선택된 것입니다.

-1인 부분을 벽이라고 바꾸었습니다. 왜냐하면 해당 2차원 배열에 해당 거리만큼의 갱신을 해야하므로 구분하기 위해 그렇게 했습니다.

해당 ny,nx 새로운 점들이 벽이거나 바이러스가 아니면 해당 배열에 거리를 갱신합니다.

반례에 도움 부탁드립니다.

package Thur_Sunday_aWeek_Al.SAMSUNG;

import java.util.*;

/*
바이러스를 m개 만큼 순서에 상관없이 뽑고. bfs 돌려서 거리를 map에 남긴다.

*/
public class Laboratory2 {
    static class Position {
        int y;
        int x;

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

    static int dy[] = {-1, 1, 0, 0};
    static int dx[] = {0, 0, -1, 1};
    static int map[][];
    static int n;
    static int m;
    static ArrayList<Position> virus = new ArrayList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        map = new int[n][n];
        int cnt=0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int a = sc.nextInt();
                if (a == 2)
                    virus.add(new Position(i, j));
                map[i][j] = a;
                if(a==0)
                    cnt++;
            }
        }



        if (cnt!=0) {
            combination(0, 0);
            if (Min == Integer.MAX_VALUE)
                System.out.println(-1);
            else
                System.out.println(Min);
        }
        else {
            System.out.println("1");
        }

    }

    static Stack<Position> s = new Stack<>();

    static void combination(int idx, int depth) {
        if (depth == m) {
            int temp[][] = new int[n][n];
            temp = copy();
            bfs(temp);
            return;
        }
        for (int i = idx; i < virus.size(); i++) {
            s.push(virus.get(i));
            combination(i + 1, depth + 1);
            s.pop();
        }
    }

    static int Min = Integer.MAX_VALUE;

    static int[][] copy() {
        int temp[][] = new int[n][n];
        for (Position p : s) {
            temp[p.y][p.x] = -2;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (map[i][j] != 2) {
                    if (map[i][j] == 1) // wall
                    {
                        temp[i][j] = -1;
                    } else
                        temp[i][j] = map[i][j];
                }
            }
        }
        return temp;
    }

    static boolean flag = true;

    static void bfs(int map[][]) {
        int max = -1;
        Queue<Position> q = new LinkedList<>();
        boolean visited[][] = new boolean[n][n];
        for (Position p : s) {
            q.offer(p);
            visited[p.y][p.x] = true;
        }
        while (!q.isEmpty()) {
            Position cur = q.poll();
            for (int i = 0; i < 4; i++) {
                int ny = cur.y + dy[i];
                int nx = cur.x + dx[i];

                if (ny >= 0 && nx >= 0 && ny < n && nx < n && !visited[ny][nx]) // boundary
                {
                    visited[ny][nx] = true;
                    if (map[ny][nx] != -1 && map[ny][nx] != -2) {
                        if (map[ny][nx] == 0 && map[cur.y][cur.x] == -2) {
                            map[ny][nx] = map[cur.y][cur.x] + 2 + 1;
                        } else if (map[ny][nx] == 0 && map[cur.y][cur.x] != -2) {
                            map[ny][nx] = map[cur.y][cur.x] + 1;
                        } else {
                            map[ny][nx] = Math.min(map[ny][nx], map[cur.y][cur.x] + 1);
                        }
                        max = Math.max(map[ny][nx], max);
                        q.add(new Position(ny, nx));
                    }
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (map[i][j] == 0) {
                    max = Integer.MAX_VALUE;
                }
//                System.out.print((map[i][j])+" ");
            }
//            System.out.println();
        }
//        System.out.println("------------------------");
        Min = Math.min(max, Min);
    }
}

/*
3
3
2 2 2
0 1 0
0 0 0
*/

fbfbf1 3년 전 11

시간이 조금 지났지만 저도 97%에서 틀려서 게시판에 다른 글 찾아보니

5 2

1 1 1 1 1

1 1 2 1 1

1 1 1 1 1

이 반례 넣으면

답이 0이 나와야되는데(바이러스를 놓는순간 다 퍼져버리니)

저 같은 경우는 -1 이 나와서 틀리더라고요

저도 글쓴이분과 똑같이 123번째 줄처럼 BFS를 돌 때마다 max값을 찾아줬는데

이거 말고 BFS가 다 끝나고 max값을 찾아주는 식으로 바꾸니 해결됐습니다.

ksh04132 2년 전 3

감사합니다! 저도 해당 문제가 97% 틀렸습니다 당하고 있었는데, 해당 반례를 확인하고 고칠 수 있었습니다.

감사합니다 :)

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

문제

문제

출처

ICPC

97% 실패

kimby469 3년 전 1

fbfbf1 3년 전 11

ksh04132 2년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말