글 읽기 - 15%에서 틀렸습니다... 반례좀 찾아주세요

apalsl 4년 전 0

질문검색에 있는 반례 전부 돌려봤습니다. 시험장에서도 똑같이 풀어서 틀렸는데

반례가 무엇이였는지 궁금합니다.

dfs로 탐색하고 섬 갯수대로 permutation을 돌리고

나온 모든 결과에서 섬 수 -1로 선이 연결된 얘들 최솟값을 비교했습니다.

만약 1번에서 어느섬이던 가면 1번은 다른애들이 못가게 하였습니다.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class Main {

	static int N, M;
	static int map[][] = new int[15][15];
	static boolean visited[][] = new boolean[15][15];

	static int[] dx = { 0, 1, 0, -1 };
	static int[] dy = { 1, 0, -1, 0 };

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		N = sc.nextInt();
		M = sc.nextInt();

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				map[i][j] = sc.nextInt();
				visited[i][j] = false;
			}
		}

		System.out.println(solve());
	}

	static int dfsCount = 0;
	
	static Queue<Point> que = new LinkedList<Main.Point>();
	static int sn, sm;
	private static int solve() {
		int result = 10000;
		// dfs 탐색
		searchDfs();
//		print();

		// 순열 배열 생성 및 구현
		int[] arr = new int[dfsCount];
		int perConut = 1;
		for (int i = 0; i < dfsCount; i++) {
			arr[i] = perConut++;
		}
		perm(arr, 0, dfsCount, dfsCount);
		
		int shortResult = 0;
		int lineCount= 0;	
		//순열 탐색
		for(int[] list : perList) {
			 lineCount= 0;
			 shortResult = 0;
			 resetChkBoolean();
			
			for(int per=0; per<list.length; per++) {
				resetVisited();
				
				// 탐색한 거리중 최소값.
				int shortNumber = 10000;
				
				for(int i=0; i<N; i++) {
					for(int j=0; j<M; j++) {
						if(map[i][j] != list[per]) continue;
						if(visited[i][j] == true) continue; 
						que.clear();
						tempQue.clear();
						que.add(new Point(i,j,map[i][j]));
						visited[i][j] = true;
						sn = i; sm = j;
						count = 0;

//						System.out.print(list[per] + "  = ");
						int cnt = bfs();
//						System.out.println(cnt);
						if(cnt < shortNumber) {
							shortNumber = cnt;
						}
					}
				}
				
				if(shortNumber != 10000) {
					lineCount++;
					shortResult += shortNumber;
				}
				chkBoolean(list[per]);
				
//				System.out.println();
//				System.out.println();
				
//				printBool();
				
			}
//			System.out.println();
			
			if(lineCount == dfsCount-1) {
				if(result > shortResult) {
					result = shortResult;
				}
			}
//			System.out.println(lineCount);
//			System.out.println("little = " + shortResult);
		}
		

		if(shortResult == 0) {
			return -1;
		} 
		// line을 전부 연결하지 않은놈들
		else if(result == 10000) {
			return -1;
		}
		
		return result;
	}

	private static void resetVisited() {
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				visited[i][j] = false;
			}
		}
		
	}

	private static void resetChkBoolean() {
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				chkBool[i][j] = false;
			}
		}
		
	}

	static boolean[][] chkBool = new boolean[15][15];
	
	private static void chkBoolean(int v) {
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if (map[i][j] == v) {
					chkBool[i][j] = true;
				}
			}
		}
	}

	static class Point {
		int n,m,v;
		public Point(int n, int m, int value) {
			this.n = n;
			this.m = m;
			this.v = value;
		}
	}
	
	static Queue<Point> tempQue = new LinkedList<Main.Point>();
	static int count = 0;
	private static int bfs() {
		
		while(!que.isEmpty()) {
			Point p = que.poll();
			int n = p.n;
			int m = p.m;
			int v = p.v;
//			System.out.println("n = " + n + " m = " + m);
			for(int i=0; i<4; i++) {
				int dn = n + dx[i];
				int dm = m + dy[i];
				
				if (dn >= N || dn < 0 || dm >= M || dm < 0) continue;
				if (map[dn][dm] == v) continue;
				if (visited[dn][dm] == true) continue;
				if (dn != sn && dm != sm) continue;
				if (chkBool[dn][dm] == true) continue;
				if (map[dn][dm] != 0 && map[dn][dm] != v) {
					if(count == 1) {
						continue;
					}
					return count;
				}
				
				Point point = new Point(dn,dm,v);
				visited[dn][dm] = true;
				tempQue.add(point);
			}
			
			if(que.isEmpty()) {
				if(!tempQue.isEmpty()) {
					count++;
					que.addAll(tempQue);
					tempQue.clear();
				}
			}
		}
		
		return 10000;
		
	}


	static List<int[]> perList = new ArrayList<int[]>();

	private static void perm(int[] arr, int arrSize, int n, int r) {
		if (arrSize == r) {
			perList.add(arr.clone());
			return;
		}

		for (int i = arrSize; i < n; i++) {
			swap(arr, i, arrSize);
			perm(arr, arrSize + 1, n, r);
			swap(arr, i, arrSize);
		}

	}

	private static void swap(int[] arr, int i, int j) {
		int temp = arr[j];
		arr[j] = arr[i];
		arr[i] = temp;
	}

	private static void searchDfs() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (visited[i][j] == false && map[i][j] != 0) {
					dfsCount++;
					dfs(i, j);
				}
			}
		}
	}

	private static void print() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				System.out.print(map[i][j]);
			}
			System.out.println();
		}

	}
	
	private static void printBool() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				System.out.print(chkBool[i][j] + " ");
			}
			System.out.println();
		}

	}
	

	private static void dfs(int n, int m) {
		visited[n][m] = true;
		map[n][m] = dfsCount;
		for (int i = 0; i < 4; i++) {
			int dn = n + dx[i];
			int dm = m + dy[i];

			if (dn >= N || dn < 0 || dm >= M || dm < 0) continue;
			if (map[dn][dm] == 0) continue;
			if (visited[dn][dm] == true) continue;
			dfs(dn, dm);
		}

	}

}

apalsl 4년 전 0

아 탐색문제였네요. 감사합니다.

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

문제

문제

출처

ICPC

15%에서 틀렸습니다... 반례좀 찾아주세요

apalsl 4년 전 0

apalsl 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말