백준 2146 (다리 만들기) java

문제

입력

 

코드

import java.util.*;
import java.io.*;
class Main {

    static int n = 0;
    static int[][] board = new int[101][101];
    static int[][] visit = new int[101][101];
    static int[][] visit2 = new int[101][101];
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] line;
        n = Integer.parseInt(bf.readLine());
        for(int i=1;i<=n;i++)
        {
            line = bf.readLine().split(" ");

            for(int j=1;j<=n;j++)
            {
                board[i][j] = Integer.parseInt(line[j-1]);
            }
        } //입력
        
        int min = 100001; // 최소 거리값
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(visit[i][j]==0&&board[i][j]==1)
                {
                    int result = bfs(i,j);
                    if(min>result)
                        min = result;
                    visit2 = new int[101][101];
                }
            }
        } // 섬의 부분을 찾은 경우 bfs 수행하고 거리 좌표계 초기화
        System.out.println(min);


        bf.close();
    }

    static int bfs(int x,int y)
    {
        int result =100001;

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

        Queue<pair> q = new LinkedList<>();
        Queue<pair> q2 = new LinkedList<>();
        visit[x][y] =1;
        q.add(new pair(x,y));

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

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

                if(nx>=1&&nx<=n&&ny>=1&&ny<=n)
                {
                    if(visit[nx][ny]==0&&board[nx][ny]==1) // 방문한적없는 섬의 부분을 찾은 경우
                    {
                        visit[nx][ny]=1;
                        q.add(new pair(nx,ny));
                    }
                    else if(visit[nx][ny]==0&&board[nx][ny]==0) // 가장 가까운 물을 찾은 경우
                    {
                        visit2[nx][ny]=1; // 거리 좌표계 값 1로 초기화
                        q2.add(new pair(nx,ny)); // !!!!
                    }
                }
            }
        }

        while(!q2.isEmpty()) // 가장자리 물을 기준으로 bfs
        {
            pair now = q2.poll();

            for(int i=0;i<4;i++) {
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];

                if (nx >= 1 && nx <= n && ny >= 1 && ny <= n)
                {
                    if(visit[nx][ny]==0&&board[nx][ny]==1)// 다른 육지의 섬을 발견한 경우
                    {
                        if(result>visit2[now.x][now.y]) {
                            result = visit2[now.x][now.y];
                        } // 거리값 비교하여 값 변경
                    }

                    if(visit2[nx][ny]==0&&board[nx][ny]==0) // 주변의 물을 통해 육지 탐색
                    {
                        visit2[nx][ny]=visit2[now.x][now.y]+1;
                        q2.add(new pair(nx,ny));
                    } 
                }
            }
        }
        return result;
    }
}
class pair
{
    int x;
    int y;
    pair(int x,int y)
    {
        this.x = x;
        this.y = y;
    }
}

 

1. 섬의 부분을 찾은 경우 bfs를 2번 수행해야하는 유형이였다. 자신의 부분과 이어진 모든 섬을 찾는 bfs 한번 , 그를 통해 끝점에 도착했을      때 가장자리 물의 위치를 찾아 따로 큐에 저장한다. 

2. 가장자리 물의 위치가 저장된 큐에서는 방문했던 섬이 아닌 다른 섬에 다다를때까지 bfs 탐색을 진행한다.

3. 그리고 거리 중 최솟값을 찾는다.

 

visit 배열은 방문 여부를 통해 중복적인 bfs가 수행되지 않도록 하고 visit2 배열은 다른 섬까지의 거리를 나타내는 좌표계이다. 한번 bfs가 수행되고 나면 visit2 배열은 초기화해줘야 한다.

 

개인적으로 시간이 조금 맘에 들지 않아서 줄여보는 방안을 탐구해봐야겠다. 그리고 생각보다 수행 조건이 빡세서 문제 파악을 확실히 해야한다.