[백준 BOJ] 2146번 - 다리 만들기 (C++)

📌 참고

교공 알고리즘 스터디에서 다룬 문제는 19주차부터 벨로그에 기록하고 있습니다 (18주차 이전 문제들을 추후 복습 겸 업로드할 계획도 있습니다 🤗) 그 외 개인적으로 풀어본 백준 및 프로그래머스 문제는 스스로 유의미하다고 여겨진 부분들이 있는 문제만 선별하여 벨로그에 기록하고 있습니다 벨로그에 올라오지 않은 다른 문제와 코드가 궁금하신 분들은 아래의 github에서 추가로 확인하실 수 있습니다 👀 방문해주셔서 감사합니다 🙏

💚 github | dianstar/Algorithm-BOJ
💚 github | dianestar/Algorithm-Programmers

교공 알고리즘 스터디 23주차 탐색문제

2146번: 다리 만들기 | 문제 바로가기

문제풀이 (2022-02-16 WED 💻)

⭐ 풀이의 핵심

아래와 같이 크게 두 함수로 나누어 각각 한번씩 총 두 번의 BFS를 활용하여 문제를 풀었다

1) 섬 구분하기 identifyIsland 함수 + firstBFS 함수
👉 입력 받은 map 행렬을 이중 for문으로 탐색하며 아직 방문하지 않은 육지 칸을 발견하면

• islandId 변수 값을 1부터 늘리고
• firstBFS 함수를 통해 BFS 탐색을 하며
  • 인접한 칸이 육지일 경우 같은 번호(islandId 변수 값)로 넘버링해주고 BFS 큐에 삽입
  • 인접한 칸이 바다일 경우 adjSeaList에 해당 바다 칸의 정보를 담은 AdjSea 구조체 삽입
    (adjSeaList란 육지랑 인접한 바다 칸, 즉 다리를 놓기 시작할 수 있는 칸 후보를 담는 벡터)
    -> adjSeaList를 마련해둘 경우 이후 buildBridge에서 보다 효과적으로 탐색할 수 있다

2) 다리 놓기 buildBridge 함수 + secondBFS 함수
👉 adjSeaList에 담긴 칸들에 대해

• secondBFS 함수를 통해 BFS 탐색을 하되
  • 최단 거리를 구해아하므로 현재 큐의 사이즈만큼만 탐색할 것
  • curBridge는 현재 놓는 다리의 길이
  • 인접한 칸이 바다일 경우 BFS 큐에 삽입하고 동서남북 네 방향에 대해 탐색이 끝나면 curBridge 값 1 증가시키기
  • 인접한 칸이 다른 섬의 육지에 해당할 경우 전역 변수 minBridge 보다 curBridge 값이 작을 경우 minBridge 값 업데이트

최종 minBridge 값을 출력해주면 끝!

➕ 참고

육지 칸의 동서남북 네 방향 중 한 칸만 바다와 인접해있으면
해당 인접한 바다 칸을 adjSeaList에 담은 것인데,
사실상 이처럼 adjSeaList에 담은 바다 칸 중에는
섬의 최외곽 모서리..? 가 아닌 칸들이 있을 수 있다
https://astrid-dm.tistory.com/m/362 👉 이 블로그에서도 비슷한 내용을 그림으로 설명해놔주셨다

어차피 해당 칸들을 포함해서 탐색해도 최단 거리 값을 구하는 데 문제는 없지만
이 칸들을 제외해주었다면 보다 효율적인 코드가 될 수 있을 것이다

🔽 코드 (C++)

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int N; // 지도의 크기 N (100 이하의 자연수)
int islandId= 0; // 섬을 구분하기 위한 id
int minBridge = 10001; // 가장 짧은 다리의 길이
struct AdjSea { // 육지에 인접한 바다 칸의 정보
    int row;
    int col;
    int adjIsland;
};
vector<AdjSea> adjSeaList;
vector<vector<bool>> visited(100, vector<bool>(100));
vector<vector<int>> map(100, vector<int>(100)); // N*N 크기의 지도

// 위쪽 오른쪽 아래쪽 왼쪽
int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};

bool checkRange(int i, int j) {
    if (i<0 || i>=N || j<0 || j>=N) {
        return false;
    }
    return true;
}

/* 섬 구분하기 */ 
void firstBFS(int i, int j, int islandId) {
    queue<pair<int, int>> q;
    q.push({i, j});
    map[i][j] = islandId;
    visited[i][j] = true;
    
    while (!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();
        for (int k=0; k<4; k++) { // 동서남북 네 방향에 대해 탐색
            int nr = cur.first + dr[k];
            int nc = cur.second + dc[k];
            if (!checkRange(nr, nc) || visited[nr][nc]) { // 지도 범위 밖이거나 이미 방문한 칸일 경우
                continue;
            } 
            if (map[nr][nc] != 0) { // 인접한 칸이 육지일 경우
                q.push({nr, nc});
                map[nr][nc] = islandId;
                visited[nr][nc] = true;
            }
            else { // 인접한 칸이 바다일 경우 (map[nr][nc] == 0)
                adjSeaList.push_back({nr, nc, islandId});
                visited[nr][nc] = true;
            }
        }
    }
}

void identifyIsland() {
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            if (map[i][j] != 0 && !visited[i][j]) {
                islandId++;
                firstBFS(i, j, islandId);
            } 
        }
    }
}
/************/

/* 다리 놓기 */ 
void secondBFS(int i, int j, int adjIsland) {
    // visited 벡터 초기화
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            visited[i][j] = false;
        }
    }

    queue<pair<int, int>> q;
    q.push({i, j});
    visited[i][j] = true;
    int curBridge = 1; // 현재 놓는 다리의 길이

    while (!q.empty()) {
        int queueSize = q.size();
        for (int k=0; k<queueSize; k++) { // 최단 거리를 구해야하므로 현재 큐의 사이즈만큼만 탐색
            pair<int, int> cur = q.front();
            q.pop();
            for (int l=0; l<4; l++) { // 동서남북 네 방향에 대해 탐색
                int nr = cur.first + dr[l];
                int nc = cur.second + dc[l];
                if (!checkRange(nr, nc) || visited[nr][nc]) { continue; } // 지도 범위 밖이거나 이미 방문한 칸일 경우
                if (map[nr][nc] == 0) { // 인접한 칸이 바다일 경우
                    q.push({nr, nc});
                    visited[nr][nc] = true;
                }
                else if (map[nr][nc] != adjIsland) { // 인접한 칸이 다른 섬의 육지일 경우
                    if (curBridge < minBridge) { minBridge = curBridge; }
                    return;
                }
            }
        }
        curBridge++;
    }
}

void buildBridge() {
    int len = adjSeaList.size();
    for (int i=0; i<len; i++) {
        secondBFS(adjSeaList[i].row, adjSeaList[i].col, adjSeaList[i].adjIsland);
    }
}
/************/

int main() {
    scanf("%d", &N);
    int num;
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            scanf("%d", &num);
            map[i][j] = num; 
        }
    }

    identifyIsland(); // 섬 구분하기
    buildBridge(); // 다리 놓기

    printf("%d", minBridge);

    return 0;
}

스터디 (2022-02-20 SUN 📚)

✅ 스터디 복기

• 모든 육지 칸에 대해 다리 놓기 탐색을 구현한 스터디원들이 있었다
  인풋 범위 조건으로 인해 큰 차이가 나지는 않을 듯 싶지만
  아무래도 adjSeaList를 마련하는 것이 비교적 효율적인 접근이지 않았나 싶다

• visited 벡터의 영향 범위가 bfs함수 내부로 한정적이며
  firstBFS와 secondBFS에서 같은 visited 벡터를 쓰려면
  secondBFS에서 visited 벡터를 어차피 초기화해서 써야 하기 때문에
  각각의 bfs 함수에 대해 내부적으로 visited 벡터를 선언해주는 것이 보다 깔끔할 수 있다!