이번에 풀어본 문제는
백준 2146번 다리 만들기 입니다.

📕 문제 링크

❗️코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Island
{
    int x,y;
    int len;

    public Island(int x, int y) {
        this.x = x;
        this.y = y;
    }
    public Island(int x, int y, int len) {
        this.x = x;
        this.y = y;
        this.len = len;
    }
}
public class Main {
    static int N;
    static int [][] map;
    static boolean [][] visited;
    static int groupNum;
    static int [] dx = {-1,1,0,0};
    static int [] dy = {0,0,-1,1};
    static int minVal = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        map = new int[N][N];

        StringTokenizer st;
        for(int i = 0; i < N; i++)
        {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++)
            {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        visited = new boolean[N][N];

        //섬 구분
        for(int i = 0; i < N; i++)
        {
            for(int j = 0; j < N; j++)
            {
                if(map[i][j] > 0 && !visited[i][j])
                {
                    visited[i][j] = true;
                    map[i][j] += groupNum;
                    setIsland(i,j);
                    groupNum++;
                }
            }
        }

        visited = new boolean[N][N];
        //다리 연결
        for(int i = 0; i < N; i++)
        {
            for(int j = 0; j < N; j++)
            {
                if(map[i][j] > 0 && !visited[i][j])
                {
                    visited[i][j] = true;
                    setBridge(i,j,map[i][j]);
                    visited = new boolean[N][N];
                }
            }
        }
        System.out.print(minVal == Integer.MAX_VALUE ? "0" : minVal);
    }
    static void setBridge(int x, int y,int groupNum)
    {
        Queue<Island> q = new LinkedList<>();
        q.add(new Island(x,y,0));

        while(!q.isEmpty())
        {
            Island cur = q.poll();

            if(cur.len >= minVal) continue;

            for(int idx = 0; idx < 4; idx++)
            {
                int mx = cur.x + dx[idx];
                int my = cur.y + dy[idx];

                if(!isValid(mx,my) || visited[mx][my] || map[mx][my] == groupNum) continue;
                //바다
                if(map[mx][my] == 0)
                {
                    visited[mx][my] = true;
                    q.add(new Island(mx,my,cur.len+1));
                }
                //다른섬 도착
                else minVal = Math.min(minVal,cur.len);
                
            }
        }
    }
    static void setIsland(int x, int y)
    {
        Queue<Island> q = new LinkedList<>();
        q.add(new Island(x,y));

        while(!q.isEmpty())
        {
            Island cur = q.poll();

            for(int idx = 0; idx < 4; idx++)
            {
                int mx = cur.x + dx[idx];
                int my = cur.y + dy[idx];

                if(!isValid(mx,my) || visited[mx][my] || map[mx][my] == 0) continue;
                visited[mx][my] = true;
                map[mx][my] += groupNum;
                q.add(new Island(mx,my));
            }
        }
    }
    static boolean isValid(int x, int y)
    {
        return x >= 0 && y >= 0 && x < N && y < N;
    }
}

📝 풀이

각 섬을 연결할 수 있는 다리를 건설할 때, 최소비용(최단거리)로 만들 수 있는 다리의 길이를 출력하는 문제입니다.
먼저 섬을 나누어 줍니다. 섬들은 기본값으로 1을 가지고 있으므로, groupNum이라는 전역변수를 두어, 각 섬을 bfs로 탐색하며 가장 처음 탐색한 섬부터 값을 더해 1,2,3...번 으로 마킹을 해줍니다.
섬을 구분했으면, 섬의 한 지점을 기준으로 다른 섬을 만날때까지 다시한번 bfs탐색해주면 됩니다. bfs 탐색이기 때문에, 앞선 탐색이 다른 탐색에 영향을 주지 않으려면 방문 배열을 배 반복마다 초기화 시켜주어야 합니다. 다른 섬을 마주칠때마다 minVal값을 최솟값으로 갱신해주면, 해결할 수 있습니다.

📜 후기

매 반복마다 방문배열을 초기화 시키는 것이 너무 찝찝해서, dfs로도 바꿔보고 큐 한방에 해결할 수 있도록 코드도 수정해보았는데 시간초과를 이겨내지 못했습니다.. 나중에 실력이 좀 더 나아진다면 꼭 최적화 시켜보고싶네요,, 맞았지만 씁쓸하네요ㅠㅠ