글 읽기 - 6%에서 틀립니다 도와주세요 자바

jwl2327 2년 전 0

질문계시판에 있는 반례들 다돌려 보았습니다.

6%에서 틀리는거라면 그냥 문제 자체 잘못이해했거나 간단한거를 계속 틀린다는것 같은데

반례를 찾아주세요 ㅜㅜ

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

public class Main {
	static int[][] arr;
	static int[][] visit;
	static int N, M, 
        max=Integer.MIN_VALUE,
        fx=-1,fy=-1,
        time,count=0;
    static int[] arrx = {-1,1,0,0}, arry = {0,0,-1,1};
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
        arr = new int[N][M];
        int temp;
		for(int i=0;i<N;i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<M;j++){
                temp = Integer.parseInt(st.nextToken());
                arr[i][j] = temp;
            } 
        }

        boolean end = false;
        e:
        for(int i=0;;i++){
            if(end){
                break;
            }
            
            time = i;
            count = 0;
            visit = new int[N][M];

            if(0<i){
                if(melt()){
                    System.out.println("\n melt = false!! time => " + time) ;
                    for(int[] a : arr){
                        System.out.println(Arrays.toString(a));
                    }
                    time = 0;
                    break;
                }   
            }


            System.out.println("\n this is after melt ! time => " + time) ;
            for(int[] a : arr){
                System.out.println(Arrays.toString(a));
            }
            for(int j=1;j<N;j++){
                for(int k=1;k<M;k++){
                    if(0<arr[j][k]&&visit[j][k]==0){
                        count ++; 
                        if(1<count){
                            end = true;
                            System.out.println("count => " + count + " end is true");
                            break e;
                        }
                        visit[j][k] = 1;
                        dfs(k,j);
                        System.out.println("\n this is after dfs ! ");

                        for(int[] a : visit){
                            System.out.println(Arrays.toString(a));
                        }
                    }
                }
            }
        }
		bw.write(Integer.toString(time));
        bw.flush();
        bw.close();
        br.close();
	}
    public static boolean melt() {
        int check = 0;
        int[][] coast = new int[N][M];
        for(int j=1;j<N;j++){
            for(int k=1;k<M;k++){
                if(arr[j][k]!=0){
                    int count = 0;
                    for(int i=0;i<4;i++){
                        int nx = k + arrx[i];
                        int ny = j + arry[i];
                        if(nx<0||ny<0||M<=nx||N<=ny){
                            continue;
                        } else {
                            if(arr[ny][nx]==0){
                                count ++;
                            }
                        }
                    }
                    coast[j][k] = count;
                }
            }
        }
        System.out.println("\n this is coast ! ");

        for(int[] a : coast){
            System.out.println(Arrays.toString(a));
        }

        for(int j=1;j<N;j++){
            for(int k=1;k<M;k++){
                if(coast[j][k]!=0){
                    arr[j][k]=coast[j][k]<arr[j][k]?arr[j][k]-coast[j][k]:0;
                }
            }
        }
        for(int j=1;j<N;j++){
            for(int k=1;k<M;k++){
                check = Math.max(arr[j][k],check);
            }
        }
        if(check==0){
            return true;
        }
        return false;
    }
	public static void dfs(int x, int y) {
        for(int i=0;i<4;i++){
            int nx = x + arrx[i];
            int ny = y + arry[i];
            if(check(nx,ny)){
                visit[ny][nx] = 1;
                dfs(nx,ny);
            }
        }
	}
    public static boolean check(int x, int y) {
        if(x<0||y<0||M<=x||N<=y){
            return false;
        }
        if(visit[y][x]==1){
            return false;
        }
        if(arr[y][x]<1){
            return false;
        }
        return true;
    }
	
}

jwl2327 2년 전 9

아래는 테스트 해보았던 반례 중 하나입니다.

20
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0 
10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0 
10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    
Output : 19

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

문제

문제

출처

ICPC

6%에서 틀립니다 도와주세요 자바

jwl2327 2년 전 0

jwl2327 2년 전 9

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말