728x90
728x90
문제 난이도
GOLD I (링크)
문제 풀이
각각의 독립된 섬들을 최단 거리로 연결하고 싶을 때, 놓을 수 있는 다리의 총 길이의 최소값을 구하는 문제.
역시나 최소 신장 트리를 응용한 문제가 되겠다.
이번에는 각 간선을 구하는 것과 더불어, 이 섬이 어느 정점인지를 구하는 것도 필요하다.
결국엔 두 정점 사이의 간선을 구해서 문제를 풀어야하기 때문이다.
위의 그림처럼 문제에서 요한 3가지 올바르지 않은 방법과 함께, 추가로 두 가지만 주의한다면 쉽게 풀 수 있다.
처음 다른 섬을 만났을 때 만족하지 않는 조건이라면 바로 빠져나올 것.
부끄럽게도 처음 코드를 완성시켰을 때, 다른 섬을 만났을 때, 종료 조건을 부족하게 작성하여 아래 그림처럼 더이상 탐색하지 못함에도 불구하고 탐색을 시켰다.
Union Find가 끝난 후 모두 연결 되어있는지 확인할 것
이 부분은 Find를 한번 더 사용하면 쉽게 해결할 수 있다.
나는 이 두 가지 때문에 40분 정도 계속 틀렸다.
정리하자면
우리는 처음으로 만나는 같은 직선상의 다른 섬에 길이 2 이상의 다리를 놓을 수 있는 경우의 수를 판별하면 된다.
풀이 단계
나는 아래와 같은 순서로 문제를 풀었다.
1. 섬을 식별할 수 있는 번호를 부여해 줄 그래프 탐색(bfs)을 통해 각 정점을 구함
//islandCnt를 통해 정점을 표현하여
// islandsMap이라는 섬 지도에 연결된 섬인지를 표현
//기존 지도 map
int[][] map;
int islandCnt = 0;
int[][] islandsMap = new int[N][M];
boolean[][] isVisit = new boolean[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (map[i][j] == 1 && !isVisit[i][j]) {
islandCnt++;
bfs(map, islandsMap, isVisit, N, M, i, j, islandCnt);
}
}
}
private static void bfs(int[][] map, int[][] islandsMap,
boolean[][] isVisit, int N, int M, int x, int y, int cnt) {
isVisit[x][y] = true;
Queue<int[]> que = new LinkedList<>();
que.offer(new int[] { x, y });
//어느 정점인지를 표현
islandsMap[x][y] = cnt;
while (!que.isEmpty()) {
int[] cur = que.poll();
for (int i = 0; i < 4; i++) {
int newX = cur[0] + dx[i];
int newY = cur[1] + dy[i];
if (isAvailableIdx(newX, newY, N, M) && !isVisit[newX][newY] && map[newX][newY] == 1) {
isVisit[newX][newY] = true;
islandsMap[newX][newY] = cnt;
que.offer(new int[] { newX, newY });
}
}
}
}
2. 연결 가능한 정점들끼리 연결
문제 조건에 맞게, 조건들을 설정하여 탐색을 통해 연결 가능한 섬들을 추출했다.
List<Bridge> bridges = findBridges(map, islandsMap, N, M);
private static List<Bridge> findBridges(int[][] map, int[][] islandsMap, int N, int M) {
List<Bridge> bridges = new ArrayList<>();
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
//1. 섬이 있을 경우에만 탐색
if (islandsMap[i][j] > 0) {
int number = islandsMap[i][j];
//2. bfs와 유사하게 직선 방향으로만 탐색
for (int k = 0; k < 4; k++) {
int length = 0;
int x = i;
int y = j;
while (true) {
x += dx[k];
y += dy[k];
//아래의 경우 탐색하지 않는다
// 3. 같은 정점(섬 그룹)에 속하거나
// 4. 길이가 1인 다른 섬의 경우
if (!isAvailableIdx(x, y, N, M) || islandsMap[x][y] == number
|| (length <= 1 && map[x][y] == 1))
break;
if (islandsMap[x][y] > 0 && length >= 2) {
bridges.add(new Bridge(number, islandsMap[x][y], length));
break;
}
length++;
}
}
}
}
}
return bridges;
}
3. 크루스칼 알고리즘을 통한 최소 신장 트리의 가중치를 구함
Collections.sort(bridges, (o1, o2) -> o1.cost - o2.cost);
int[] parent = new int[islandCnt + 1];
for (int i = 0; i < islandCnt + 1; i++) {
parent[i] = i;
}
int mstCost = 0;
for (Bridge b : bridges) {
int s = b.start;
int e = b.end;
if (find(parent, s) != find(parent, e)) {
union(parent, s, e);
mstCost += b.cost;
}
}
4. 모든 섬이 연결되었는지 확인
루트로 설정할 섬을 하나 정해서 설정한 뒤, Union Find의 Find를 돌려주면 된다.
int root = find(parent, 1);
for (int i = 2; i < islandCnt + 1; i ++) {
if (find(parent, i) != root) {
System.out.println(-1);
return;
}
}
전체 코드
public class Main {
public static class Bridge {
int start;
int end;
int cost;
public Bridge(int start, int end, int cost) {
this.start = start;
this.end = end;
this.cost = cost;
}
}
private static int[] dx = { -1, 1, 0, 0 };
private static int[] dy = { 0, 0, -1, 1 };
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[][] map = new int[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
int islandCnt = 0;
int[][] islandsMap = new int[N][M];
boolean[][] isVisit = new boolean[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (map[i][j] == 1 && !isVisit[i][j]) {
islandCnt++;
bfs(map, islandsMap, isVisit, N, M, i, j, islandCnt);
}
}
}
List<Bridge> bridges = findBridges(map, islandsMap, N, M);
Collections.sort(bridges, (o1, o2) -> o1.cost - o2.cost);
int[] parent = new int[islandCnt + 1];
for (int i = 0; i < islandCnt + 1; i++) {
parent[i] = i;
}
int mstCost = 0;
for (Bridge b : bridges) {
int s = b.start;
int e = b.end;
if (find(parent, s) != find(parent, e)) {
union(parent, s, e);
mstCost += b.cost;
}
}
int root = find(parent, 1);
for (int i = 2; i < islandCnt + 1; i ++) {
if (find(parent, i) != root) {
System.out.println(-1);
return;
}
}
System.out.println(mstCost);
}
private static int find(int[] parent, int x) {
if (x == parent[x]) {
return x;
}
return parent[x] = find(parent, parent[x]);
}
private static void union(int[] parent, int x, int y) {
x = find(parent, x);
y = find(parent, y);
if (x == y)
return;
if (x < y) {
parent[y] = x;
} else {
parent[x] = y;
}
}
private static List<Bridge> findBridges(int[][] map,
int[][] islandsMap, int N, int M) {
List<Bridge> bridges = new ArrayList<>();
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
//1. 섬이 있을 경우에만 탐색
if (islandsMap[i][j] > 0) {
int number = islandsMap[i][j];
//2. bfs와 유사하게 직선 방향으로만 탐색
for (int k = 0; k < 4; k++) {
int length = 0;
int x = i;
int y = j;
while (true) {
x += dx[k];
y += dy[k];
//아래의 경우 탐색하지 않는다
// 3. 같은 정점(섬 그룹)에 속하거나
// 4. 길이가 1인 다른 섬의 경우
if (!isAvailableIdx(x, y, N, M) || islandsMap[x][y] == number
|| (length <= 1 && map[x][y] == 1))
break;
if (islandsMap[x][y] > 0 && length >= 2) {
bridges.add(new Bridge(number, islandsMap[x][y], length));
break;
}
length++;
}
}
}
}
}
return bridges;
}
private static void bfs(int[][] map, int[][] islandsMap,
boolean[][] isVisit, int N, int M, int x, int y, int cnt) {
isVisit[x][y] = true;
Queue<int[]> que = new LinkedList<>();
que.offer(new int[] { x, y });
islandsMap[x][y] = cnt;
while (!que.isEmpty()) {
int[] cur = que.poll();
for (int i = 0; i < 4; i++) {
int newX = cur[0] + dx[i];
int newY = cur[1] + dy[i];
if (isAvailableIdx(newX, newY, N, M) && !isVisit[newX][newY] && map[newX][newY] == 1) {
isVisit[newX][newY] = true;
islandsMap[newX][newY] = cnt;
que.offer(new int[] { newX, newY });
}
}
}
}
private static boolean isAvailableIdx(int x, int y, int N, int M) {
return x >= 0 && x < N && y >= 0 && y < M;
}
}728x90
300x250
