글 읽기 - 테스트와 반례는 전부 통과하는데 어디서 4%를 못넘깁니다 ㅜ

jinho6442 2년 전 0

다른분들이 해결한 방법과는 조금 다르게 map에 번호로 labeling을 하지 않고

Island라는 클래스를 만들어서 클래스안에 index와 섬을 이루는 좌표들을 list로 저장했습니다.

그리고 섬과 섬 사이의 다리를 만들 때

x좌표가 같거나 y좌표가 같아야지만 가로 또는 세로로 섬이 연결될 수 있기 때문에 이를 이용했고

x좌표가 같다면 y좌표를 이용해서 거리를 계산했습니다. (좌표를 확인하며 두 섬 사이에 다른 섬이 있다면 0을 리턴하도록 했어요)

문제의 테스트와 질문글들의 반례들은 전부 통과하는것 같은데

실행해보면 4%를 못넘기네요 ㅜㅜ

알려주신다면 감사하겠습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.StringTokenizer;

 class Main {

  private static final BufferedReader READER = new BufferedReader(new InputStreamReader(System.in));
  private static StringTokenizer tokenizer;
  private static int[][] map;
  private static boolean[][] visit;
  private static List<Island> islands;
  private static int[] parent;

  public static void main(String[] args) throws IOException {
    tokenizer = new StringTokenizer(READER.readLine());
    int y = Integer.parseInt(tokenizer.nextToken());
    int x = Integer.parseInt(tokenizer.nextToken());
    map = new int[y][x];
    visit = new boolean[y][x];

    for (int i = 0; i < y; i++) {
      tokenizer = new StringTokenizer(READER.readLine());
      for (int j = 0; j < x; j++) {
        map[i][j] = Integer.parseInt(tokenizer.nextToken());
      }
    }

    islands = new ArrayList<>();
    int index = 0;
    for (int i = 0; i < y; i++) {
      for (int j = 0; j < x; j++) {
        if (!visit[i][j] && map[i][j] == 1) {
          islands.add(index, new Island(index));
          buildIsland(i, j, index);
          index++;
        }
      }
    }

    List<Edge> edges = new ArrayList<>();
    for (int i = 0; i < islands.size(); i++) {
      for (int j = i + 1; j < islands.size(); j++) {
        List<int[]> current = islands.get(i).points;
        List<int[]> target = islands.get(j).points;

        for (int k = 0; k < current.size(); k++) {
          for (int l = 0; l < target.size(); l++) {
            int[] pointA = current.get(k);
            int[] pointB = target.get(l);
            int bridgeLength = 0;

            if (isSameRow(pointA, pointB)) {
              bridgeLength = calculateLength(pointA, pointB);
            } else if (isSameCol(pointA, pointB)) {
              bridgeLength = calculateLength(pointA, pointB);
            }

            if (bridgeLength != 0) {
              edges.add(new Edge(i, j, bridgeLength));
            }
          }
        }

      }
    }
    parent = new int[islands.size()];
    for (int i = 0; i < parent.length; i++) {
      parent[i] = i;
    }

    edges.sort(Comparator.comparingInt(o -> o.weight));
    int minWeight = 0;
    for (int i = 0; i < edges.size(); i++) {
      Edge current = edges.get(i);
      int from = current.from;
      int to = current.to;
      int weight = current.weight;
      if (find(from) != find(to)) {
        minWeight += weight;
        union(from, to);
      }
    }

    System.out.println(minWeight == 0 ? -1 : minWeight);
  }

  private static int calculateLength(int[] pointA, int[] pointB) {
    int aY = pointA[0];
    int aX = pointA[1];
    int bY = pointB[0];
    int bX = pointB[1];

    int length = 0;
    if (aY == bY) {
      for (int i = Math.min(aX, bX) + 1; i < Math.max(aX, bX); i++) {
        if (map[aY][i] != 0) {
          return 0;
        }
        length++;
      }
    } else {
      for (int i = Math.min(aY, bY) + 1; i < Math.max(aY, bY); i++) {
        if (map[i][aX] != 0) {
          return 0;
        }
        length++;
      }
    }
    return length == 1 ? 0 : length;
  }

  private static boolean isSameCol(int[] pointA, int[] pointB) {
    return pointA[1] == pointB[1];
  }

  private static boolean isSameRow(int[] pointA, int[] pointB) {
    return pointA[0] == pointB[0];
  }

  private static void union(int from, int to) {
    from = find(from);
    to = find(to);

    if (from != to) {
      parent[to] = from;
    }
  }

  private static int find(int x) {
    if (parent[x] == x) {
      return x;
    }
    return parent[x] = find(parent[x]);
  }

  private static void buildIsland(int y, int x, int index) {
    if (y < 0 || y >= map.length) {
      return;
    }
    if (x < 0 || x >= map[y].length) {
      return;
    }
    if (map[y][x] == 0) {
      return;
    }
    if (visit[y][x]) {
      return;
    }

    visit[y][x] = true;
    islands.get(index).size += 1;
    islands.get(index).points.add(new int[]{y, x});

    buildIsland(y + 1, x, index);
    buildIsland(y - 1, x, index);
    buildIsland(y, x + 1, index);
    buildIsland(y, x - 1, index);
  }
}

class Island {

  List<int[]> points;
  int index;
  int size;

  public Island(int index) {
    this.points = new ArrayList<>();
    this.index = index;
    this.size = 0;
  }
}

class Edge {

  int from;
  int to;
  int weight;

  public Edge(int from, int to, int weight) {
    this.from = from;
    this.to = to;
    this.weight = weight;
  }
}

jinho6442 2년 전 1

잘못 된 곳을 잘못 알고 있었네요

union - find 후에 모든 섬이 연결되어있는지 검사하는 코드를 빼먹어서 틀린거였습니다 ㅜㅜ

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

문제

문제

출처

ICPC

테스트와 반례는 전부 통과하는데 어디서 4%를 못넘깁니다 ㅜ

jinho6442 2년 전 0

jinho6442 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말