[백준] 17472 다리 만들기 2

17472번: 다리 만들기 2

 

boj.kr

풀이

[프로그래머스] 지형 이동과 유사한 문제인데 개인적으로 조금 더 까다로웠다. 상당히 구현할 것이 많은 문제이다. 해당 문제는 완전탐색으로도 해결할 수 있다고 한다. 아래의 코드는 MST를 사용해서 해결하였다.

이 문제에서 MST를 만들어서 문제를 해결하려면 크게 3단계로 나누어서 풀어야한다.

1. 섬들 라벨링 하기
2. 섬들 간의 거리 구하기
3. MST 생성하기

우선 섬 라벨링은 BFS 알고리즘을 통해 할 수 있었다. visited[][] 배열을 선언해 중복 방문을 막아주었다.

// 섬들을 구분하기 위해 bfs 알고리즘 사용
void bfs(int x, int y, int idx) {
    queue<pair<int, int>> q;
    q.push({ x, y });
    visited[y][x] = idx;

    while (!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();

        for (int i = 0; i < 4; i++) {
            int nx = cur.first + dx[i];
            int ny = cur.second + dy[i];

            if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue; // 범위를 벗어나는 경우
            // 방문한 적 없고 육지인 경우
            if (!visited[ny][nx] && board[ny][nx] == board[cur.second][cur.first]) {
                q.push({ nx, ny });
                visited[ny][nx] = idx;
            }
        }
    }
}

그러면 visited[][] 배열에 섬들이 각자 라벨링 되어있게 되는데, 이제는 각 섬들간의 거리를 구해야 한다. 다리를 건설할 때 방향을 꺾으면 안된다는 조건이 있기 때문에 while문을 통해 어렵지 않게 구현할 수 있었다. 이 때 1번 섬에서 4번 섬까지 가는 거리나 4번 섬에서 1번 섬까지 가는 거리는 같은데 중복으로 저장될 수 있기 때문에 set을 통해 중복된 간선을 제거해주었다.

void calculate_distance(int x, int y) {
    for (int i = 0; i < 4; i++) {
        int dist = 0;
        int nx = x;
        int ny = y;
        int idx = visited[y][x];
        while (true) {
            nx += dx[i];
            ny += dy[i];
            int next_idx = visited[ny][nx];
            if (nx < 0 || nx >= m || ny < 0 || ny >= n || next_idx == idx) break;
            if (next_idx != 0 && next_idx != idx) {
                if (idx > next_idx) swap(idx, next_idx); // 섬은 작은 번호부터 큰 번호 순으로 저장
                // 다리 길이가 1보다 길면 저장
                if (dist > 1) s.insert({ dist, {idx, next_idx} });
                break;
            }
            else dist++;
        }
    }
}

이제 섬들간의 거리를 모두 알게 되었으니 kruskal 알고리즘을 사용해서 MST를 생성할 수 있다. MST를 생성한 후, kruskal 알고리즘을 통해 계산한 값을 출력해주면 끝날 것 같지만 한 가지 주의해야할 것이 있다. 바로 모든 섬들이 연결되어있는지 확인해야 하는 것이다. 이는 유니온 파인드 구현할 때 구현한 find() 함수를 사용해 해결해주었다.

코드

C++