[JAVA] BOJ 백준 17472번 - 다리 만들기 2

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

https://www.acmicpc.net/problem/17472

17472번: 다리 만들기 2

---

2. 내가 푼 방법

다리의 방향이 바뀌면 안 되기 때문에 다른 조건들을 고려할 필요가 있던 BFS 문제였다.

 

크게 3개의 함수로 나누어 문제 풀이를 진행했다.

public static void solution() {
    getIsland();
    linkBridge();
    choiceBridge();
}

 

먼저 getIsland 함수에서 섬들의 번호를 매긴다. 입력값을 담았던 island 배열을 그대로 사용했기 때문에 섬 번호는 2부터 시작한다.

public static void getIsland() {
    islandCnt = 2;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (island[i][j] == 1) {
                getIslandBFS(islandCnt++, i, j);
            }
        }
    }
}

public static void getIslandBFS(int islandIdx, int i, int j) {
    Queue<Tuple> queue = new LinkedList<>();
    int[] dx = {-1, 0, 1, 0};
    int[] dy = {0, -1, 0, 1};

    queue.add(new Tuple(i, j));

    while (!queue.isEmpty()) {
        Tuple t = queue.poll();
        int x = t.x;
        int y = t.y;

        if (x < 0 || y < 0 || x >= N || y >= M) continue;
        if (island[x][y] != 1) continue;

        island[x][y] = islandIdx;

        for (int d = 0; d < dx.length; d++) {
            queue.add(new Tuple(x + dx[d], y + dy[d]));
        }
    }
}

 

 

그 후, linkBridge 함수를 통해 다리를 연결했고, 연결된 다리들은 리스트 배열에 저장했다. 나는 섬의 상하좌우 영역에서 시작해 다리 길이를 0부터 카운팅했다는 점에 주의하면서 코드를 작성했다. 따라서 다른 섬 번호가 나옴과 동시에 다리 길이가 1 이상일 경우, 각각의 좌표에서 도달할 수 있는 최소 다리 길이를 리스트 배열에 넣어주면서 빠져나올 수 있었다.

public static void linkBridge() {
    bridge = new ArrayList[islandCnt];
    for (int i = 2; i < islandCnt; i++) {
        bridge[i] = new ArrayList<>();
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (island[i][j] > 1) {
                linkOneToOne(i, j);
            }
        }
    }
}

public static void linkOneToOne(int i, int j) {
    Queue<Tuple> queue = new LinkedList<>();
    int[] dx = {-1, 0, 1, 0};
    int[] dy = {0, -1, 0, 1};

    for (int d = 0; d < dx.length; d++) {
        queue.add(new Tuple(i+dx[d], j+dy[d], d, 0));
    }

    while (!queue.isEmpty()) {
        Tuple t = queue.poll();
        int x = t.x;
        int y = t.y;
        int d = t.d;
        int cnt = t.cnt;

        if (x < 0 || y < 0 || x >= N || y >= M) continue;
        if (island[i][j] == island[x][y]) continue;


        if (island[x][y] >= 2) {
            if (cnt > 1) {
                bridge[island[x][y]].add(new Tuple(island[i][j], cnt));
                bridge[island[i][j]].add(new Tuple(island[x][y], cnt));
                break;
            }
            continue;
        }

        queue.add(new Tuple(x + dx[d], y + dy[d], d, cnt + 1));
    }
}

 

마지막으로 연결된 다리 중에서 최소 비용으로 모든 나라를 연결해야 한다. 따라서 choiceBridge 함수에서 우선순위 큐를 이용해 각 정점에 연결될 수 있는 최소 가중치를 더해주었다.

public static void choiceBridge() {
    PriorityQueue<Tuple> queue = new PriorityQueue<>();
    boolean[] visit = new boolean[islandCnt];

    queue.add(new Tuple(2, 0));

    while (!queue.isEmpty()) {
        Tuple t = queue.poll();
        int v = t.x;
        int w = t.y;

        if (visit[v]) continue;

        visit[v] = true;
        result += w;

        for (Tuple tuple : bridge[v]) {
            queue.add(tuple);
        }
    }

    for (int i = 2; i < islandCnt; i++) {
        if (!visit[i]) {
            result = -1;
            return;
        }
    }
}

---

4. 결과 및 회고

한번 꼬이면 디버깅하기 귀찮을 거 같아서 열심히 쳐다보면서 풀었던 문제이다. 실제로 linkBridge 함수에서 다리 길이 카운팅할 때 실수했지만, 다행히도 금방 고칠 수 있었다. 요즘 코테 풀 때 어느 부분에서 잘못됐을지 더 쉽게 예상 가능해진 것 같다.