(11) [C++, Java] 백준 No.2146 : 다리 만들기

문제

풀이

자세한 풀이 : https://ldgeao99.tistory.com/400

 

# C++(효율적이 떨어지는 방법)

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

int place[101][101]; // 0 : 바다, 1: 땅
int group[101][101]; // 0 : 방문안함, 1이상 : 그룹번호
int dist[101][101];  // -1 : 방문안함, 0이상 : 방문했으며, 거리를 의미
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};

int main()
{
    //데이터 입력받기 및 초기화
    int n;
    cin >> n;

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin >> place[i][j];
            group[i][j] = 0;
        }
    }

    //BFS를 이용해서 각 섬에 그룹번호 매기기(place와 group사용)
    int cnt = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(place[i][j] == 1 && group[i][j] == 0){
                ++cnt;
                queue<pair<int, int>> q;
                q.push(make_pair(i, j));
                group[i][j] = cnt;
                
                while(!q.empty()){
                    pair<int, int> p;
                    p = q.front();
                    q.pop();
                    int cx = p.first;
                    int cy = p.second;

                    for(int k = 0; k < 4; k++){
                        int nx = cx + dx[k];
                        int ny = cy + dy[k];
                        if(nx >= 1 && nx <= n && ny >= 1 && ny <= n){
                            if (place[nx][ny] == 1 && group[nx][ny] == 0){
                                q.push(make_pair(nx,ny));
                                group[nx][ny] = cnt;
                            }
                        }
                    } 
                }
            }
        }
    }

    //각 섬이 다른 섬과 얼마나 떨어져있나 dist를 구하고 그 중 최소값을 찾음(place와 dist사용)
    int ans = -1;
    for(int g = 1; g < cnt; g++){
        //탐색이 시작되는 지점들을 모두 큐에 넣어줌.
        queue<pair<int, int>> q;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                dist[i][j] = -1;
                if(group[i][j] == g){
                    dist[i][j] = 0;
                    q.push(make_pair(i, j));
                }
            }
        }

        //시작점들로부터 탐색을 진행하여 dist를 구함
        while(!q.empty()){
            pair<int, int> p;
            p = q.front();
            q.pop();
            int cx = p.first;
            int cy = p.second;

            for(int k = 0; k < 4; k++){
                int nx = cx + dx[k];
                int ny = cy + dy[k];
                if(nx >= 1 && nx <= n && ny >= 1 && ny <= n){
                    if(dist[nx][ny] == -1){
                        q.push(make_pair(nx, ny));
                        dist[nx][ny] = dist[cx][cy] + 1;
                    }
                }
            }
        }

        // 구한 dist 배열 값에서 다른 그룹번호를 가진 섬들과의 거리중, 가장 짧은 거리를 찾음
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(g != group[i][j] && place[i][j] == 1){
                    if(ans == -1 || ans > dist[i][j] - 1){
                        ans = dist[i][j] - 1;
                    }
                }
            }
        }
    }

    cout << ans << "\n";
}

# C++(효율적인 방법)

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

int place[101][101]; // 0 : 바다, 1: 땅
int group[101][101]; // 0 : 방문안함, 1이상 : 그룹번호
int dist[101][101];  // -1 : 방문안함, 0이상 : 방문했으며, 거리를 의미
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};

int main()
{
    //데이터 입력받기 및 초기화
    int n;
    cin >> n;

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin >> place[i][j];
            group[i][j] = 0;
        }
    }

    //BFS를 이용해서 각 섬에 그룹번호 매기기
    int cnt = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(place[i][j] == 1 && group[i][j] == 0){
                ++cnt;
                queue<pair<int, int>> q;
                q.push(make_pair(i, j));
                group[i][j] = cnt;
                
                while(!q.empty()){
                    pair<int, int> p;
                    p = q.front();
                    q.pop();
                    int cx = p.first;
                    int cy = p.second;

                    for(int k = 0; k < 4; k++){
                        int nx = cx + dx[k];
                        int ny = cy + dy[k];
                        if(nx >= 1 && nx <= n && ny >= 1 && ny <= n){
                            if (place[nx][ny] == 1 && group[nx][ny] == 0){
                                q.push(make_pair(nx,ny));
                                group[nx][ny] = cnt;
                            }
                        }
                    } 
                }
            }
        }
    }

    //group과 dist를 확장시킴
    //탐색이 시작되는 지점들을 모두 큐에 넣어줌.
    queue<pair<int, int>> q;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            dist[i][j] = -1;
            if(place[i][j] == 1){
                dist[i][j] = 0;
                q.push(make_pair(i, j));
            }
        }
    }

    //group, dist 확장시키기
    while(!q.empty()){
        pair<int, int> p;
        p = q.front();
        q.pop();
        int cx = p.first;
        int cy = p.second;

        for(int k = 0; k < 4; k++){
            int nx = cx + dx[k];
            int ny = cy + dy[k];
            if(nx >= 1 && nx <= n && ny >= 1 && ny <= n){
                if(dist[nx][ny] == -1){
                    q.push(make_pair(nx, ny));
                    dist[nx][ny] = dist[cx][cy] + 1;
                    group[nx][ny] = group[cx][cy];
                }
            }
        }
    }

    //다리가 놓일 수 있는 위치를 찾아내고, 그 다리 길이의 최소값을 구함.
    int ans = -1;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            int cx = i;
            int cy = j;
            for(int k = 0; k < 4; k++){
                int nx = i + dx[k];
                int ny = j + dy[k];
                if(nx >= 1 && nx <= n && ny >= 1 && ny <= n){
                    if(group[cx][cy] != group[nx][ny]){
                        if(ans == -1 || ans > dist[cx][cy] + dist[nx][ny]){
                            ans = dist[cx][cy] + dist[nx][ny];
                        }
                    }
                }
            }
        }
    }

    cout << ans << "\n";
}

# Java(효율이 떨어지는 방법)

import java.util.*;

class Pair {
    int x;
    int y;
    Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class Main {
    public static final int[] dx = {0, 0, 1, -1};
    public static final int[] dy = {1, -1, 0, 0};
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] a = new int[n][n];
        int[][] d = new int[n][n];
        int[][] g = new int[n][n];
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        int cnt = 0;
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                if (a[i][j] == 1 && g[i][j] == 0) {
                    Queue<Pair> q = new LinkedList<Pair>();
                    g[i][j] = ++cnt;
                    q.add(new Pair(i, j));
                    while (!q.isEmpty()) {
                        Pair p = q.remove();
                        int x = p.x;
                        int y = p.y;
                        for (int k=0; k<4; k++) {
                            int nx = x+dx[k];
                            int ny = y+dy[k];
                            if (0 <= nx && nx < n && 0 <= ny && ny < n) {
                                if (a[nx][ny] == 1 && g[nx][ny] == 0) {
                                    q.add(new Pair(nx, ny));
                                    g[nx][ny] = cnt;
                                }
                            }
                        }
                    }
                }
            }
        }
        int ans = -1;
        for (int l=1; l<=cnt; l++) {
            Queue<Pair> q = new LinkedList<Pair>();
            for (int i=0; i<n; i++) {
                for (int j=0; j<n; j++) {
                    d[i][j] = -1;
                    if (g[i][j] == l) {
                        q.add(new Pair(i,j));
                        d[i][j] = 0;
                    }
                }
            }
            while (!q.isEmpty()) {
                Pair p = q.remove();
                int x = p.x;
                int y = p.y;
                for (int k=0; k<4; k++) {
                    int nx = x+dx[k];
                    int ny = y+dy[k];
                    if (0 <= nx && nx < n && 0 <= ny && ny < n) {
                        if (d[nx][ny] == -1) {
                            d[nx][ny] = d[x][y] + 1;
                            q.add(new Pair(nx,ny));
                        }
                    }
                }
            }
            for (int i=0; i<n; i++) {
                for (int j=0; j<n; j++) {
                    if (a[i][j] == 1 && g[i][j] != l) {
                        if (ans == -1 || d[i][j]-1 < ans) {
                            ans = d[i][j]-1;
                        }
                    }
                }
            }
        }
        System.out.println(ans);
    }
}

# Java(효율적인 방법)

import java.util.*;

class Pair {
    int x;
    int y;
    Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class Main {
    public static final int[] dx = {0, 0, 1, -1};
    public static final int[] dy = {1, -1, 0, 0};
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] a = new int[n][n];
        int[][] d = new int[n][n];
        int[][] g = new int[n][n];
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        int cnt = 0;
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                if (a[i][j] == 1 && g[i][j] == 0) {
                    Queue<Pair> q = new LinkedList<Pair>();
                    g[i][j] = ++cnt;
                    q.add(new Pair(i, j));
                    while (!q.isEmpty()) {
                        Pair p = q.remove();
                        int x = p.x;
                        int y = p.y;
                        for (int k=0; k<4; k++) {
                            int nx = x+dx[k];
                            int ny = y+dy[k];
                            if (0 <= nx && nx < n && 0 <= ny && ny < n) {
                                if (a[nx][ny] == 1 && g[nx][ny] == 0) {
                                    q.add(new Pair(nx, ny));
                                    g[nx][ny] = cnt;
                                }
                            }
                        }
                    }
                }
            }
        }
        Queue<Pair> q = new LinkedList<Pair>();
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                d[i][j] = -1;
                if (a[i][j] == 1) {
                    q.add(new Pair(i,j));
                    d[i][j] = 0;
                }
            }
        }
        while (!q.isEmpty()) {
            Pair p = q.remove();
            int x = p.x;
            int y = p.y;
            for (int k=0; k<4; k++) {
                int nx = x+dx[k];
                int ny = y+dy[k];
                if (0 <= nx && nx < n && 0 <= ny && ny < n) {
                    if (d[nx][ny] == -1) {
                        d[nx][ny] = d[x][y] + 1;
                        g[nx][ny] = g[x][y];
                        q.add(new Pair(nx,ny));
                    }
                }
            }
        }
        int ans = -1;
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                for (int k=0; k<4; k++) {
                    int x = i+dx[k];
                    int y = j+dy[k];
                    if (0 <= x && x < n && 0 <= y && y < n) {
                        if (g[i][j] != g[x][y]) {
                            if (ans == -1 || ans > d[i][j] + d[x][y]) {
                                ans = d[i][j] + d[x][y];
                            }
                        }
                    }
                }
            }
        }
        System.out.println(ans);
    }
}