(백준 2146번) 다리 만들기
문제 설명
여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다.
이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북으로 육지가 붙어있는 덩어리를 말한다. 다음은 세 개의 섬으로 이루어진 나라의 지도이다.
위의 그림에서 색이 있는 부분이 육지이고, 색이 없는 부분이 바다이다. 이 바다에 가장 짧은 다리를 놓아 두 대륙을 연결하고자 한다. 가장 짧은 다리란, 다리가 격자에서 차지하는 칸의 수가 가장 작은 다리를 말한다. 다음 그림에서 두 대륙을 연결하는 다리를 볼 수 있다.
물론 위의 방법 외에도 다리를 놓는 방법이 여러 가지 있으나, 위의 경우가 놓는 다리의 길이가 3으로 가장 짧다(물론 길이가 3인 다른 다리를 놓을 수 있는 방법도 몇 가지 있다).
지도가 주어질 때, 가장 짧은 다리 하나를 놓아 두 대륙을 연결하는 방법을 찾으시오.
입력
첫 줄에는 지도의 크기 N(100이하의 자연수)가 주어진다. 그 다음 N줄에는 N개의 숫자가 빈칸을 사이에 두고 주어지며, 0은 바다, 1은 육지를 나타낸다. 항상 두 개 이상의 섬이 있는 데이터만 입력으로 주어진다.
출력
첫째 줄에 가장 짧은 다리의 길이를 출력한다.
문제 풀이
굉장히 오랜만에 풀어본 알고리즘 문제이다. 그리고 처음으로 java로 풀어본 알고리즘 문제이다. 자바의 정석 책으로 공부하며 개념은 어느정도 터득했지만 실제로 사용하는 것은 역시 큰 차이가 있었다. C++과 많이 비슷하면서도 조금 다르고 조금 뭐가 없고 하다보니 좀 짜증이 나긴 했다.
그래도 역시 이론만 계속 보다가 오랜만에 직접 코드를 보니 나는 코드를 보며 씨름하는 쪽이 좀 더 맞는 느낌이 든다.
문제 자체는 간단한 bfs 문제이다. 먼저 bfs를 한번 돌려 섬들을 구분한 뒤, 각 섬에서 bfs를 한번 더 돌려 다른 섬에 도착할 때까지의 최단 거리를 구하면 된다.
나는 처음 bfs를 돌릴 때 visited에 1 대신 섬의 번호를 넣는 식으로 구현하였다. bfs가 브루트포스로 한번 돈 후 다시 한번 브루트포스로 다른 섬까지의 최단 거리를 구하는 bfs2를 실행하여 정답을 도출하였다. 내륙에 있는 좌표는 금방 연산이 종료되기에 이렇게 구현했다.
문제를 풀면서 풀이 방법은 둘째치고 자바의 문법이 아직 익숙하지 않아 시간이 많이 들었는데, 일단 struct가 없다. class가 중심인 java이니 그건 그럴 수 있지만 pair도 없다. 그래서 class로 따로 만들어주어야 했다. main이 static 메서드이다 보니 사용하는 모든 변수와 메서드에도 static을 붙여줘야 했기에 귀찮았다. queue도 용법이 달라 add, remove, peek 등을 사용해야 했다. cin cout 대신 Scanner와 println을 사용해야 하는 것도 좀 불편했다. 가장 컸던 것은 java는 프로젝트 단위로 돌아간다는 것이었다. C++와 달리 cpp파일 하나 덩그러니 돌아갈 수가 없고 java 파일 뿐 아니라 프로젝트 전체가 있어야만 컴파일과 구동이 가능했다.
아직 java에 익숙하지 않아서 그런지 객체지향적인 개발에 더 적합하고 코딩 테스트용으론 그다지 적합하지 않은 느낌을 받았다. 좀 더 문제를 풀고 만져봐야 java의 강점을 알 수 있을 것 같다. 코드는 다음과 같다.
코드
import java.util.*;
class pair {
int x; int y; int dist=0;
public pair(int x, int y) {
this.x=x; this.y=y;
}
public pair(int x, int y, int dist) {
this.x=x; this.y=y; this.dist=dist;
}
public int first() {
return x;
}
public int second() {
return y;
}
public int dist() {
return dist;
}
}
public class Main {
static int n;
static int min=1000000;
static int arr[][]=new int[100][100];
static int visited[][]=new int[100][100];
static int count=1;
static int dx[]={1,0,-1,0};
static int dy[]={0,1,0,-1};
public static boolean oob(int x, int y) {
if(x>=0 && x<n && y>=0 && y<n) return true;
else return false;
}
public static void bfs(int x, int y) {
Queue<pair> q=new LinkedList<pair>();
q.add(new pair(x,y)); visited[x][y]=count;
while(!q.isEmpty()) {
pair p=q.peek(); q.remove();
for(int i=0; i<4; i++) {
int xx=p.first()+dx[i];
int yy=p.second()+dy[i];
if(oob(xx,yy)&&arr[xx][yy]==1 && visited[xx][yy]==0) {
q.add(new pair(xx,yy)); visited[xx][yy]=count;
}
}
}
count++;
}
public static void bfs2(int x, int y, int num) {
Queue<pair> q=new LinkedList<pair>();
q.add(new pair(x,y,0));
int check[][]=new int[100][100];
check[x][y]=1;
while(!q.isEmpty()) {
pair p=q.peek(); q.remove();
for(int i=0; i<4; i++) {
int xx=p.first()+dx[i];
int yy=p.second()+dy[i];
int dist=p.dist();
if(oob(xx,yy)&&arr[xx][yy]==0 && check[xx][yy]==0) {
q.add(new pair(xx,yy,dist+1)); check[xx][yy]=1;
}
else if(oob(xx,yy)&&arr[xx][yy]==1 && visited[xx][yy]!=num) {
if(min>dist) min=dist;
return;
}
}
}
}
public static void main(String args[]) {
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
arr[i][j]=sc.nextInt();
}
}
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
if(arr[i][j]!=0 && visited[i][j]==0) bfs(i,j);
}
}
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
if(arr[i][j]!=0) bfs2(i,j,visited[i][j]);
}
}
System.out.println(min);
}
}