글 읽기 - 반례를 찾아주실 수 있나요?

dldhk97 3년 전 1

놓친게 있나 싶어서 아예 처음부터 다시 짜는데도 틀렸다고 나옵니다.

게시판에 있는 여러 반례들을 돌려봐도 케이스를 찾기 힘드네요 ㅠㅠ

print는 제출시에는 제외하고 제출했습니다.

-------------------------------------------------

반례를 찾아서 해결하였습니다.

99번째 줄에서 익은 토마토를 찾으면 바로 bfs를 해버렸는데,

이렇게 되면 bfs가 아닌 무언가가 되는것 같습니다.

익은 토마토를 찾으면 Queue에 넣고, 3중 포문이 완료된 후 bfs를 하여 해결하였습니다.

아래는 반례입니다.

3 3 1
0 0 0
0 0 1
1 0 0

출력 : 3

정답 : 2

4 5 2
0 1 0 0
0 1 -1 1
-1 -1 1 -1
0 0 0 0
-1 -1 0 -1
-1 1 0 -1
0 0 -1 1
-1 0 1 0
0 0 0 -1
0 0 1 -1

출력 : 5

정답 : 3

5 5 2
1 -1 1 -1 1
0 0 -1 -1 1
0 -1 -1 1 0
0 -1 0 0 1
0 0 1 -1 1
1 -1 -1 -1 -1
0 -1 0 1 1
0 1 0 0 -1
-1 -1 -1 -1 -1
-1 0 0 1 -1

출력 : 4

정답 : 3

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

class TomatoBox {
    int M, N, H;

    int[][][] map;

    int countOfTomatoes = 0;
    int countOfRotten = 0;

    public TomatoBox(int M, int N, int H){
        this.M = M;
        this.N = N;
        this.H = H;

        map = new int[M][N][H];
    }

    public void addTomato(int x, int y, int z, int value){
        map[x][y][z] = value;

        if(value == 0)
            countOfTomatoes++;
        else if(value == 1)
            countOfRotten++;
    }

    void print(){
        for(int z = 0 ; z < H ; z++){
            for(int y = 0 ; y < N ; y++){
                for(int x = 0 ; x < M ; x++){
                    System.out.print(map[x][y][z] + "\t");
                }
                System.out.println();
            }
            System.out.println("--layer" + z + "--");
        }
        System.out.println("");
    }

    boolean[][][] visited;
    int[] directionX = {0, 0, -1, 1, 0, 0};
    int[] directionY = {0, 0, 0, 0, -1, 1};
    int[] directionZ = {-1, 1, 0, 0, 0, 0};

    void bfs(int[] point){
        Queue<int[]> queue = new ArrayDeque<>();
        queue.add(point);

        while(!queue.isEmpty()){
            int[] p = queue.poll();
            int x = p[0]; int y = p[1]; int z = p[2];

            if(visited[x][y][z] || map[x][y][z] == -1) continue;

            print();
            visited[x][y][z] = true;

            for(int i = 0 ; i < 6 ; i++){
                int newX = x + directionX[i];
                int newY = y + directionY[i];
                int newZ = z + directionZ[i];

                if((0 <= newX && newX < M) && (0 <= newY && newY < N) && (0 <= newZ && newZ < H)){
                    if(map[newX][newY][newZ] == -1) continue;

                    if(map[newX][newY][newZ] == 0){
                        map[newX][newY][newZ] = map[x][y][z] + 1;
                    }
                    else{
                        map[newX][newY][newZ] = Math.min(map[newX][newY][newZ], map[x][y][z] + 1);
                    }

                    int[] newPoint = {newX, newY, newZ};
                    queue.add(newPoint);
                }
            }
        }
    }

    public int solve(){
        if(countOfRotten == 0){
            return -1;  // 익은 토마토가 존재하지 않음.
        }
        if(countOfTomatoes == 0){
            return 0;   // 이미 모든 토마토가 익음
        }

        visited = new boolean[M][N][H];

        for(int z = 0 ; z < H ; z++){
            for(int y = 0 ; y < N ; y++){
                for(int x = 0 ; x < M ; x++){
                    if(visited[x][y][z] || map[x][y][z] != 1) continue;

                    int[] point = {x, y, z};
                    bfs(point);
                }
            }
        }

        print();

        // 익지 않은 토마토 탐색 & 경과일 계산
        int days = 0;
        for(int z = 0 ; z < H ; z++){
            for(int y = 0 ; y < N ; y++){
                for(int x = 0 ; x < M ; x++){
                    if(map[x][y][z] == 0) return -1;        // 익지 않은 토마토가 존재
                    days = Math.max(days, map[x][y][z]);
                }
            }
        }

        return days - 1;
    }
}

public class Main{
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        int H = Integer.parseInt(st.nextToken());

        TomatoBox box = new TomatoBox(M, N, H);

        for(int h = 0 ; h < H ; h++){
            for(int y = 0 ; y < N ; y++){
                st = new StringTokenizer(br.readLine());

                for(int x = 0 ; x < M ; x++){
                    int value = Integer.parseInt(st.nextToken());
                    box.addTomato(x, y, h, value);
                }
            }
        }

        int result = box.solve();
        System.out.println(result);
    }
}

dkkim0122 2년 전 0

혹시

'99번째 줄에서 익은 토마토를 찾으면 바로 bfs를 해버렸는데,

이렇게 되면 bfs가 아닌 무언가가 되는것 같습니다.'

라고 하셨는데, 그 이유가 있을까요...?

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

문제

문제

출처

ICPC

반례를 찾아주실 수 있나요?

dldhk97 3년 전 1

dkkim0122 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말