글 읽기 - 반례를 도저히 못 찾겠네요

cycho21 7년 전 0

반례를 도저히 못 찾겠습니다
시간도 여유 있게 나오구요
어디가 문제일까요 ㅠㅠ
import java.util.ArrayList;

import java.util.Scanner;
import java.util.Stack;

public class Main {

	private int sizeOfMap;
	private int[][] data;

	private int[][] island;
	private boolean[][] visited;
	private int count;
	
	public static void main(String[] args) {
		new Main();
	}

	
	public Main() {
		init();
		count = 1;
		
		for(int i = 0; i < sizeOfMap; i++) {
			for(int j = 0; j < sizeOfMap; j++){
				dfs(i, j);
			}
		}

		int temp = 0;
		
		for(int i = 0; i < sizeOfMap; i++){
			for(int j = 0; j < sizeOfMap; j++){
				for(int k = 0; k < sizeOfMap; k++){
					for(int l = 0; l < sizeOfMap; l++){
						if(data[i][j] == data[k][l] && island[i][j] != island[k][l]){
							
							int tempR = Math.abs(k-i) + Math.abs(l-j);
								if(tempR < temp || temp == 0){
									temp = tempR;
								}
						}
					}
				}
			}
		}
		
		if(temp == 0){
			System.out.println(0);
		} else {
			System.out.println(temp - 1);
		}
	}

	private void dfs(int i, int j) {
		Stack<ArrayList<Integer>> stack = new Stack<ArrayList<Integer>>();
		ArrayList<Integer> arr = new ArrayList<Integer>();
		arr.add(i);
		arr.add(j);
		stack.push(arr);

		if(data[i][j] == 1 && island[i][j] == 0){
			island[i][j] = count;
		}
		
			while(!stack.isEmpty()){
				ArrayList<Integer> temp = stack.pop();
				int k = temp.get(0);
				int l = temp.get(1);
				visited[k][l] = true;
				
					if(checkIsland(temp)){
						if(checkUp(temp)){
							
							if(island[k-1][l] == island[k][l] && island[k][l] == 0){
								count++;
							}
							
							visited[k-1][l] = true;
							ArrayList<Integer> tempArr = new ArrayList<Integer>();
							tempArr.add(k-1);
							tempArr.add(l);
							island[k-1][l] = count;
							stack.push(tempArr);
						}
					}
					
					if(checkIsland(temp)){
						if(checkDown(temp)){
							
							if(island[k+1][l] == island[k][l] && island[k][l] == 0){
								count++;
							}
							
							visited[k+1][l] = true;
							ArrayList<Integer> tempArr = new ArrayList<Integer>();
							tempArr.add(k+1);
							tempArr.add(l);
							island[k+1][l] = count;
							stack.push(tempArr);
						}
					}
					
					if(checkIsland(temp)){
						if(checkLeft(temp)){
							
							if(island[k][l-1] == island[k][l] && island[k][l] == 0){
								count++;
							}
							
							visited[k][l-1] = true;
							ArrayList<Integer> tempArr = new ArrayList<Integer>();
							tempArr.add(k);
							tempArr.add(l-1);
							island[k][l-1] = count;
							stack.push(tempArr);
						}
					}
					
					if(checkIsland(temp)){
						if(checkRight(temp)){
							
							if(island[k][l+1] == island[k][l] && island[k][l] == 0){
								count++;
							}
							
							visited[k][l+1] = true;
							ArrayList<Integer> tempArr = new ArrayList<Integer>();
							tempArr.add(k);
							tempArr.add(l+1);
							island[k][l+1] = count;
							stack.push(tempArr);
						}
					}
			}
	}
	
	private boolean checkUp(ArrayList<Integer> arr){
		int i = arr.get(0);
		int j = arr.get(1);
		boolean tempBool = false;
		
		if(i-1 >= 0){
			if(!visited[i-1][j] && data[i-1][j] == 1){
				tempBool = true;
			}
		}
		return tempBool;
	}
	
	private boolean checkDown(ArrayList<Integer> arr){
		int i = arr.get(0);
		int j = arr.get(1);
		boolean tempBool = false;
		
		if(i+1 < sizeOfMap){
			if(!visited[i+1][j] && data[i+1][j] == 1){
				tempBool = true;
			}
		}
		
		return tempBool;
	}
	
	private boolean checkLeft(ArrayList<Integer> arr){
		int i = arr.get(0);
		int j = arr.get(1);
		boolean tempBool = false;
		
		if(j-1 >= 0){
			if(!visited[i][j-1] && data[i][j-1] == 1){
				tempBool = true;
			}
		}
		
		return tempBool;
	}
	
	private boolean checkRight(ArrayList<Integer> arr){
		int i = arr.get(0);
		int j = arr.get(1);
		boolean tempBool = false;
		
		if(j+1 < sizeOfMap){
			if(!visited[i][j+1] && data[i][j+1] == 1){
				tempBool = true;
			}
		}
		return tempBool;
	}

	private boolean checkIsland(ArrayList<Integer> arr) {
		int i = arr.get(0);
		int j = arr.get(1);
		
		boolean right = false;
		boolean left = false;
		boolean down = false;
		boolean up = false;
		
		if(i-1 >= 0){
			if(!visited[i-1][j] && data[i-1][j] == 1){
				up = true;
			}
		}
		
		if(i+1 < sizeOfMap){
			if(!visited[i+1][j] && data[i+1][j] == 1){
				down = true;
			}
		}
		
		if(j-1 >= 0){
			if(!visited[i][j-1] && data[i][j-1] == 1){
				left = true;
			}
		}
		
		if(j+1 < sizeOfMap){
			if(!visited[i][j+1] && data[i][j+1] == 1){
				right = true;
			}
		}
		
		if(!right && !left && !up && !down){
			return false;
		} else {
			return true;
		}
	}
	
	private void init() {
		Scanner scanner = new Scanner(System.in);
		sizeOfMap = Integer.parseInt(scanner.nextLine());
		data = new int[sizeOfMap][sizeOfMap];
		island = new int[sizeOfMap][sizeOfMap];
		visited = new boolean[sizeOfMap][sizeOfMap];
		
		for (int i = 0; i < sizeOfMap; i++) {
				for (int j = 0; j < sizeOfMap; j++) {
					data[i][j] = scanner.nextInt();
				}
		}
		
		scanner.close();
	}
	
}
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

반례를 도저히 못 찾겠네요

cycho21 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
