글 읽기 - 빙산문제 어디가 틀린지 잘 모르겠네요

jasony93 3년 전 0

바로 틀렸다고 나오는데 어디가 틀린지 잘 모르겠습니다.

빙산이 두개로 나눠지는걸 확인하는 방법을 세가지 method로 나눠서 쓰었습니다.

check1은 array를 (1,1)부터 끝가지 조회하면서 빙산이 있는지 확인합니다.

만약 빙산이 있다면 check2를 이용해 이어진 빙산들을 visited에 true로 표시합니다.

이렇게 첫번째 빙산덩어리가 모두 표시되면 check3을 이용해 표시된 빙산말고 다른 빙산이 있는지 확인합니다.

check1과 check3이 둘다 참이면 빙산이 두덩어리 이상이므로 그때의 year을 반환합니다.

몇가지 테스트를 해보긴했는데 반례를 못찾겠습니다.

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

public class Main {
    
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    static int[][] array;
    static int[][] array_copy;
    static boolean[][] visited;
    
    public static void main(String args[]) throws IOException{
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int rowSize = Integer.parseInt(st.nextToken());
        int columnSize = Integer.parseInt(st.nextToken());
        
        array = new int[rowSize][columnSize];
        array_copy = new int[rowSize][columnSize];
        visited = new boolean[rowSize][columnSize];
        
        for(int i = 0; i < rowSize; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < columnSize; j++){
                array[i][j] = Integer.parseInt(st.nextToken());
                array_copy[i][j] = array[i][j];
            }
        }
        
        int year = 0;
        boolean flag1, flag2;
        
        while(year < 10){
            year++;
            melt();
            flag1 = check1();
            flag2 = check3();
            if(flag1 && flag2){
                System.out.println(year);
                break;
            }
            visited = new boolean[rowSize][columnSize];
            flag1 = false;
            flag2 = false;
        }
        
        if(year == 10){
            System.out.print("0");
        }

    }
    
    //array를 (1,1)부터 조회하면서 빙산이 있는지를 확인한다
    static boolean check1(){
        
        for(int i = 1; i < array.length; i++){
            for(int j = 1; j < array[0].length; j++){
                if(!visited[i][j] && array[i][j] != 0){
                    check2(i,j);
                    return true;
                }
            }
        }
        
        return false;
    }
    
    static void check2(int i, int j){
        
        //방문한적이 있거나 빙산이 없으면 끝낸다
        if(visited[i][j] || array[i][j] == 0){
            return;
        }//방문한적이 없고 빙산이 있으면 참으로 표시한다
        else{
            visited[i][j] = true;
        }
        
        for(int k = 0; k < dx.length; k++){
            check2(i + dy[k], j + dx[k]);
        }
    }
    
    static boolean check3(){
        
        for(int i = 1; i < array.length - 1; i++){
            for(int j = 1; j < array[0].length - 1; j++){
                if(array[i][j] != 0 && !visited[i][j])
                    return true;
            }
        }
        
        return false;
    }
    
  
    static void melt(){
        
        int count = 0;
        
        for(int i = 1; i < array.length - 1; i++){
            for(int j = 1; j < array[0].length - 1; j++){
                for(int k = 0; k < dx.length; k++){
                    if(array_copy[i + dy[k]][j + dx[k]] == 0){
                        count++;
                    }  
                }
                array[i][j] -= count;
                
                if(array[i][j] < 0){
                    array[i][j] = 0;
                }
                count = 0;
            }
        }
        
        copy();
    }
    
    static void copy(){
        for(int i = 1; i < array.length - 1; i++){
            for(int j = 1; j < array[0].length - 1; j++){
                array_copy[i][j] = array[i][j];
            }
        }
    }
  
}

wbjeon2k 3년 전 0

아래 경우에서 아예 출력이 안됩니다

ckddn1224 2년 전 0

이 반례는 잘못된거 같아요!

배열의 좌측 최상단과 우측 최하단은 0이라는 제한이 있네요

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

문제

문제

출처

ICPC

빙산문제 어디가 틀린지 잘 모르겠네요

jasony93 3년 전 0

wbjeon2k 3년 전 0

ckddn1224 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말