[백준] 다리만들기

[hye-on]

🔗 다리 만들기

[hye-on]

📑 댓글 템플릿

• Language : C++
• 성능

코드 풀이

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

int N;
int answer = 1000;
int dy[] = {0,1,0,-1};
int dx[] = {1,0,-1,0};


void bfs(int y, int x, int fill_n, vector<vector<int>>& map) {
    queue<pair<int,int>>q;
    q.push({y,x});
    map[y][x] = fill_n;

    while(!q.empty()) {
        int cur_y = q.front().first;
        int cur_x = q.front().second;
        q.pop();

        for(int i=0; i<4; i++) {
            int ny = cur_y + dy[i];
            int nx = cur_x + dx[i];
            
            if(ny>=N || ny<0 || nx>=N || nx<0)
                continue;
            if(map[ny][nx] == 1) {
                map[ny][nx] = fill_n;
                q.push({ny,nx});
            }
        }
    }
}

void findShortestBridge(int start_num, vector<vector<int>>& map) {
    queue<pair<pair<int,int>, int>> q;  // {{y, x}, dist}
    vector<vector<bool>> visited(N, vector<bool>(N, false));
    
   
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            if(map[i][j] == start_num) {
                // 가장자리 체크
                for(int k=0; k<4; k++) {
                    int ny = i + dy[k];
                    int nx = j + dx[k];
                    if(ny>=0 && ny<N && nx>=0 && nx<N && map[ny][nx] == 0) { //0근처면 가장자리 
                        q.push({{i,j}, 0});
                        visited[i][j] = true;
                        break;
                    }
                }
            }
        }
    }

    while(!q.empty()) {
        int y = q.front().first.first;
        int x = q.front().first.second;
        int dist = q.front().second;
        q.pop();

        for(int i=0; i<4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            
            if(ny<0 || ny>=N || nx<0 || nx>=N || visited[ny][nx])
                continue;
                
            if(map[ny][nx] == 0) {
                visited[ny][nx] = true; //같은 자리에 먼저 도달한것이 최소-> 방문 체크
                q.push({{ny,nx}, dist+1});
            }
            else if(map[ny][nx] != start_num) {
                answer = min(answer, dist);
                return;
            }
        }
    }
}

int main() {
    cin >> N;
    vector<vector<int>> map(N, vector<int>(N));
    
    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++)
            cin >> map[i][j];

    // 섬 라벨링
    int fill_n = 2;
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            if(map[i][j] == 1)
                bfs(i, j, fill_n++, map);
        }
    }

    // 각 섬에서 다른 섬까지의 최단거리 찾기
    for(int num=2; num<fill_n; num++) {
        findShortestBridge(num, map);
    }

    cout << answer;
    return 0;
}

코멘트

-

[uijin-j]

📑 댓글 템플릿

• Language : Java
• 성능

코드 풀이

import java.io.*;
import java.util.*;

// 13:12 시작! 13:42 끗!
public class Main
{
    static int n, min;
    static boolean[][] map;
    static int[][] visit, dist;
    static Queue<int[]> q;
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(bf.readLine());
        map = new boolean[n][n];
        visit = new int[n][n];
        min = Integer.MAX_VALUE;
	    
        StringTokenizer st;
        for(int i = 0; i < n; ++i) {
           st = new StringTokenizer(bf.readLine());
           for(int j = 0; j < n; ++j) {
               map[i][j] = Integer.parseInt(st.nextToken()) == 1;
           }
        }
	    
        int island = 1;
        for(int i = 0; i < n; ++i) {
           for(int j = 0; j < n; ++j) {
                if(map[i][j] && visit[i][j] == 0) { // 새로운 섬 발견!
                    q = new LinkedList<>();
                    dist = new int[n][n];
                    dfs(i, j, island);
                    findMinDist(island);
                }
           }
        }
	    
        System.out.println(min);
    }
	
    static int[] dx = { -1, 0, 1, 0 };
    static int[] dy = { 0, 1, 0, -1 };
    public static void dfs(int x, int y, int island) {
        visit[x][y] = island;
	    
        boolean bound = false;
        for(int i = 0; i < 4; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];
	        
            if(nx >= 0 && nx < n && ny >= 0 && ny < n && visit[nx][ny] == 0) {
                if(map[nx][ny]) {
                    dfs(nx, ny, island);
                    continue;
                }
	            
                bound = true;
            }
        }
	    
        if(bound) {
            q.offer(new int[]{x, y});
            dist[x][y] = 1;
        }
    }
	
    public static void findMinDist(int island) {
        while(!q.isEmpty()) {
            int[] point = q.poll();
            int x = point[0];
            int y = point[1];
	            
            for(int j = 0; j < 4; ++j) {
                int nx = x + dx[j];
                int ny = y + dy[j];
                
                if(nx >= 0 && nx < n && ny >= 0 && ny < n && dist[nx][ny] == 0) {
    	            if(map[nx][ny] && visit[nx][ny] != island) {
    	                min = Math.min(min, dist[x][y] - 1);
    	                return;
    	            }
    	            
    	            if(!map[nx][ny]) {
    	                dist[nx][ny] = dist[x][y] + 1;
    	                q.offer(new int[]{nx, ny});
    	            }
    	        }
            }
        }
    }
}

코멘트

- 섬 갯수 세는 문제는 대표적인 dfs이기 때문에, 문제 유형 파악은 쉬웠습니다! 다만 단순히 섬만 식별하는 것이 아니라 각 섬에서 다른 섬으로의 최단거리도 구해야 하기 때문에 dfs 탐색 시 섬의 테두리를 큐에 넣어서 bfs로 다른 섬과의 최단거리를 구했습니다!