[백준] 2146번 다리만들기 BFS로 빠르게 풀어보기
1. 문제
1) 링크
2) 문제
여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다.
이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북으로 육지가 붙어있는 덩어리를 말한다.
지도가 주어질 때, 가장 짧은 다리 하나를 놓아 두 대륙을 연결하는 방법을 찾으시오.
3) 입력
첫 줄에는 지도의 크기 N(100이하의 자연수)가 주어진다. 그 다음 N줄에는 N개의 숫자가 빈칸을 사이에 두고 주어지며, 0은 바다, 1은 육지를 나타낸다. 항상 두 개 이상의 섬이 있는 데이터만 입력으로 주어진다.
4) 출력
첫째 줄에 가장 짧은 다리의 길이를 출력한다.
위의 링크로 들어가보면 문제의 예시가 그림을 통해 더 자세히 설명되어 있으니 들어가서 확인해보자
2. 풀이
이 문제를 풀기 위해 필요한 요소를 알아보자
- a[][] : 문제에서 해당 자리가 섬인지 아닌지를 배열 a 로 받는 것이다. 0 또는 1
- group[][] : 섬끼리 grouping을 하고 난 뒤에 섬이 어느 섬에 속해 있는 섬인지 group number를 붙여주게 된다
- distance[][]: 거리를 계산하기 위한 배열. 섬인 자리는 0부터 시작하고 인접해있는 자리는 1을 더하는 식으로 계산해준다.
이 문제는 먼저 섬이 있는 곳을 찾아내어 group 번호를 붙어준다. 이는 dfs로 해주어도 되고 bfs로 해주어도 되는데 여기서는 dfs 로 계산해주었다.
public static void dfs(int x, int y, int cnt){
group[x][y]=cnt;
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){
if (a[nx][ny]==1 &&group[nx][ny]==0){
dfs(nx, ny, cnt);
}
}
}
}위와 같이 dfs 함수를 사용하고 나면 섬이 있는 자리에는 그룹 번호를 붙일 수 있게 되었다. 즉, 섬이 있는 자리에 group 배열에는 해당 섬의 그룹 숫자가 적혀있다.
다음으로는 섬이 아닌 부분의 거리도 계산해주고, 섬이 아닌 부분도 나중을 위해 group 번호를 붙여준다. 거리의 경우 인접한 거리에 1을 더해주면 되고 group 번호는 인접한 group의 번호를 그대로 가져다 쓰면 된다. 여기서 섬이 아닌 부분도 group 번호를 붙여주는 이유는 나중에 최종으로 다리를 놓는 경우를 생각할 때 인접한 두 칸의 그룹번호가 다르면 그 두 칸의 거리를 더한 것이 다리를 놓는 최종 거리가 되기 때문이다. 만약 섬이 없는 부분에 그룹번호를 입력해놓지 않으면 이런 방식으로 구할 수 없다.
따라서 queue에 처음 섬인 부분을 넣고 섬인 부분의 distance는 0, 그렇지 않은 부분의 distance는 -1로 초기화하고 시작한다. 이후, 섬이 아닌 부분의 distance는 인접한 것에 1을 더하는 식으로 코드를 구성해보았다.
Queue<Pair> q=new LinkedList<>();
for(int i=0; i<n;i++){
for(int j=0; j<n; j++){
distance[i][j]=-1;
if (a[i][j]==1){
distance[i][j]=0;
q.add(new Pair(i,j));
}
}
}
while(!q.isEmpty()){
Pair a=q.remove();
int x=a.x;
int y=a.y;
for(int i=0; i<4; i++){
int nx=x+dx[i];
int ny=y+dy[i];
if (nx>=0 && ny>=0 && nx<n && ny<n){
if (distance[nx][ny]==-1){
distance[nx][ny]=distance[x][y]+1;
group[nx][ny]=group[x][y];
q.add(new Pair(nx, ny));
}
}
}
}이런식으로 queue에 섬인 부분을 넣어두고, 이후 pop과 add를 하면서 거리와 그룹넘버를 채워넣게 된다.
다음으로는 이제 모든 n*n 칸을 다 돌면서 양 옆칸의 그룹넘버가 다르다면 두 개의 거리를 더해서 ans 에 넣어준다. 이 ans를 최소화시키는 방향으로 코드를 구성해주면 된다.
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 nx = i+dx[k];
int ny = j+dy[k];
if (0 <= nx && nx < n && 0 <= ny && ny < n) {
if (group[i][j] != group[nx][ny]) {
if (ans == -1 || ans > distance[i][j] + distance[nx][ny]) {
ans = distance[i][j] + distance[nx][ny];
}
}
}
}
}
}조건문에 ans==-1이 들어간 이유는 맨 처음 ans 를 업데이트 해주는 경우를 고려해준것이다.
이 문제는 각각의 섬에서 각각 bfs를 사용해도 되지만 그러면 시간이 오래 걸리기 때문에 모든 섬을 queue에 넣어놓고 bfs를 한꺼번에 사용했다.
3. 코드
모든 것을 종합적으로 고려하여, 전체코드는 아래와 같다.
import java.util.*;
class Pair{
int x, 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};
static int group[][];
static int n;
static int a[][];
public static void dfs(int x, int y, int cnt){
group[x][y]=cnt;
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){
if (a[nx][ny]==1 &&group[nx][ny]==0){
dfs(nx, ny, cnt);
}
}
}
}
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
a=new int [n][n];
for (int i=0; i<n; i++){
for(int j=0; j<n; j++){
a[i][j]=sc.nextInt();
}
}
group=new int[n][n];
int cnt=0;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if (a[i][j]==1 &&group[i][j]==0){
dfs(i,j,++cnt );
}
}
}
Queue<Pair> q=new LinkedList<>();
int distance[][]=new int [n][n];
for(int i=0; i<n;i++){
for(int j=0; j<n; j++){
distance[i][j]=-1;
if (a[i][j]==1){
distance[i][j]=0;
q.add(new Pair(i,j));
}
}
}
while(!q.isEmpty()){
Pair a=q.remove();
int x=a.x;
int y=a.y;
for(int i=0; i<4; i++){
int nx=x+dx[i];
int ny=y+dy[i];
if (nx>=0 && ny>=0 && nx<n && ny<n){
if (distance[nx][ny]==-1){
distance[nx][ny]=distance[x][y]+1;
group[nx][ny]=group[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 nx = i+dx[k];
int ny = j+dy[k];
if (0 <= nx && nx < n && 0 <= ny && ny < n) {
if (group[i][j] != group[nx][ny]) {
if (ans == -1 || ans > distance[i][j] + distance[nx][ny]) {
ans = distance[i][j] + distance[nx][ny];
}
}
}
}
}
}
System.out.println(ans);
}
}