글 읽기 - 질문에 있는 반례까지 다돌렸는데 틀린이유를 모르겠습니다.

tjgocks 4년 전 0

반례에 있는 케이스까지 모두 해보았는데 정답이 되지 않습니다. 고수님들 도와주세요 ㅠㅠ

+) 해결했습니다 감사합니다.

//package boj;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	static int[][] map;
	static boolean[][] visited;
	static int num = 1;
	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };
	static int N, M;

	static class Edge implements Comparable<Edge> {
		int v1, v2, weight;

		Edge(int v1, int v2, int weight) {
			this.v1 = v1;
			this.v2 = v2;
			this.weight = weight;
		}

		@Override
		public int compareTo(Edge o) {
			if (this.weight > o.weight)
				return 1;
			else if (this.weight < o.weight)
				return -1;
			else
				return 0;
		}
	}

	static List<Edge> queue = new LinkedList<Edge>();
	static int[] parent;

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(reader.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new int[N][M];
		visited = new boolean[N][M];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(reader.readLine());
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if (map[i][j] == 0)
					visited[i][j] = true;
			}
		}
//		섬 labeling
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map[i][j] != 0 && !visited[i][j]) {
					dfs(i, j);
					num++;
				}

			}
		}
		// 맵 찍기
//		System.out.println();
//		for (int i = 0; i < N; i++) {
//			for (int j = 0; j < M; j++) {
//				System.out.print(map[i][j] + " ");
//			}
//			System.out.println();
//		}

//		간선찾기
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map[i][j] != 0) {
					findEdge(i, j);
				}
			}
		}
//		edge 작은순서대로 정렬
		queue.sort(null);
		parent = new int[num];

//		parent 초기화
		for (int i = 1; i <= num - 1; i++) {
			parent[i] = i;
		}
		int sum = 0;

		int edgeNum = 0;
//		간선 추가(Kruskal)
		for (Edge edge : queue) {
			if (edge.weight <= 1)
				continue;
			if (find(edge.v1) != find(edge.v2)) {
//				System.out.println("v1: "+edge.v1+" v2: "+edge.v2);
				sum += edge.weight;
				union(edge.v1, edge.v2);
//				System.out.println("find v1: "+find(edge.v1)+" find v2: "+find(edge.v2));
				edgeNum++;
//				edge 찍기
//				System.out.println(edge.v1 + " " + edge.v2 + " " + edge.weight);
			}
		}
//		System.out.println("size " + edgeNum);
//		System.out.println("num " + num);

//		num은 섬의 갯수+1이므로 MST에서 간선의 개수는 항상 vertex개수-1
		if (num - 2 != edgeNum)
			sum = -1;
		else if (sum == 0)
			sum = -1;
		System.out.print(sum);
	}

	static int find(int v1) {
		if (parent[v1] == v1)
			return v1;
		else
			return parent[v1] = find(parent[parent[v1]]);
	}

	static void union(int v1, int v2) {
		v1 = find(v1);
		v2 = find(v2);
		if (v1 != v2) {
			parent[v1] = v2;
		}

	}

	static void findEdge(int x, int y) {
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || nx >= N || ny < 0 || ny >= M)
				continue;
			if (map[nx][ny] == 0) {
				int dir = 2;
				int distance = 1;
				while (true) {
					int nnx = x + dir * dx[i];
					int nny = y + dir * dy[i];
					if (nnx < 0 || nnx >= N || nny < 0 || nny >= M)
						break;
					if (map[nnx][nny] != 0) {
						if (map[nnx][nny] == map[x][y])
							break;
//						if()
						queue.add(new Edge(map[x][y], map[nnx][nny], distance));
						break;
					}
					distance++;
					dir++;
				}
			}
		}
	}

	static void dfs(int x, int y) {
		visited[x][y] = true;
		map[x][y] = num;
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || nx >= N || ny < 0 || ny >= M)
				continue;
			if (visited[nx][ny])
				continue;
			if (map[nx][ny] != 0) {
				dfs(nx, ny);
			}

		}
	}
}

danimartinwife 4년 전 1

https://www.acmicpc.net/board/view/41802 여기 반례 읽어보셨나요? 저의 의견인데 이분이 제시하신 반례들은 대체로 "모든 섬이 연결되지 않은 경우" 입니다.

우선 저는 크루스칼로 풀지 않았고 브루트포스 일명 삽질로 해결하긴 했습니다만, 어떤 방법으로 풀든 문제에서 "모든 섬이 연결되어야 한다" 라는 조건을 제시하였기 때문에 먼저 정점들이 모두 연결되었는지 확인을 하셔야 합니다. 저는 유니온 파인드를 많이 연습하지 않아서 잘 모르겠지만, 질문자님께서 모든 정점의 연결 여부를 체크하시는 부분은 어디서 구현하셨는지 여쭤봐도 괜찮을까요?

제 생각이지만, 이번 역량테스트 9월 기출문제 두문제 모두 그래프의 연결요소라는 개념이 핵심이었고 두문제 모두 해당 이론을 모르면(저 같은 경우는 구현할 수 없으면 배경지식은 알아도 모르는 것으로 간주합니다) 풀기 어려운 문제였습니다.

tjgocks 4년 전 0

섬을 라벨링을 하였습니다. 코드에서 섬의 개수가 n이라면 num은 n+1이 됩니다. vertex의 개수가 n인 MST의 edge는 항상 n-1입니다. 그래서 110번 줄 비교가 모든 정점이 연결된것을 확인하는 코드입니다. num은 vertex+1이고 edgeNum은 edge개수 즉,vertex-1 이므로 num-2와 edgeNum의 개수를 비교한 것입니다.

tjgocks 4년 전 0

제 코드에서 find(v1)은 v1의 루트 vertex를 반환합니다. 따라서 98번째 라인에서 이미 두 정점이 연결이 되었는지 아닌지(사이클을 형성하는지 아닌지) 판단할 수 있다고 생각합니다.

(v1과 v2가 연결이 되었다는 것은 v1(v2)에서 v2(v1)로 가는 단순 경로가 항상 존재한다는 것을 의미합니다.)

tjgocks 4년 전 0

탐색하는부분에서 문제가있어서 수정했습니다 감사합니다~

danimartinwife 4년 전 1

저도 union-find 개념만 알고 활용법은 몰랐는데 덕분에 알게됐습니다. 감사합니다!

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

문제

문제

출처

ICPC

질문에 있는 반례까지 다돌렸는데 틀린이유를 모르겠습니다.

tjgocks 4년 전 0

danimartinwife 4년 전 1

tjgocks 4년 전 0

tjgocks 4년 전 0

tjgocks 4년 전 0

danimartinwife 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말