🔗문제 링크
🔒 문제 설명
위 그림과 같이 섬으로 이루어진 나라가 주어졌을 때, 다리를 놓아 각 섬을 연결하려고 한다. (파란색 : 섬, 흰색 : 바다)
다리는 바다위에만 놓을 수 있으며, 다리는 길이가 2 이상이어야 하고 중간에 방향이 바뀌면 안된다.
또한 다리가 지나가는 길에 인접한 섬이 있다면 해당 섬은 연결되어있는 것이 아니다. 다리와 다리는 교차가 가능하고 해당 경우의 다리길이를 게산할 때는 교차 지점이 두 다리 모두에 포함되어야 한다.
-예시1)
-예시2)
-예시3)
🧾 입력 예시
7 8
0 0 0 0 0 0 1 1
1 1 0 0 0 0 1 1
1 1 0 0 0 0 0 0
1 1 0 0 0 1 1 0
0 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1첫번째 줄에는 지도의 크기N, M이 주어진다.
두번째 줄부터 N개의 줄에는 지도의 정보가 주어진다.
🔎 출력 예시
9
🔑 문제 풀이
-
지도의 정보를 받는 map 2차원배열을 생성한다. 땅의 값을 -1로 저장하도록 변경한다. (후에 Island 객체화를 위하여)
1-2. Island 자료형은 섬의 값과 땅 위치 좌표들을 담은 arrList를 가지고 있다. 또한 다른 섬과의 거리를 잴 수 있는 distance메소드도 있다.
- changeMap()메소드를 통하여 섬마다 값을 다르게 주고 Island로 객체화하여 islandList에 추가한 후, 섬의 갯수를 반환한다.
- 입력 예시값에 대한 changeMap() 이후 map 상태
0 0 0 0 0 0 1 1
2 2 0 0 0 0 1 1
2 2 0 0 0 0 0 0
2 2 0 0 0 3 3 0
0 0 0 0 0 3 3 0
0 0 0 0 0 0 0 0
4 4 4 4 4 4 4 4 - 섬끼리의 거리를 담을 dist 2차원 배열을 생성하여 Island의 distance메소드를 사용하여 섬간의 거리를 담아준다.
ex)
dist[1][2]=4 : 섬1과 섬2 사이의 거리는 4
dist[1][3]=3 : 섬1과 섬3은 연결할 수 없음- makeBridge메소드에서 각 섬의 방문기록을 담은 visited 배열을 생성하여 모든 섬을 연결할 때 까지 while문을 반복한다.
최초, 가장 거리가 가까운 두 섬을 연결한 후 연결된 섬에서 가장 가까운 섬을 찾아 연결하는 과정을 반복한다.
💻 전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
Main z = new Main();
z.solution();
}
int N;
int M;
int[][] map;
List<Island> islandList;
class Island{
int idx;
List<int[]> arrList;
public Island(int idx, List<int[]> arrList) {
this.idx = idx;
this.arrList = arrList;
}
private int distance(Island island) {
int dist = Integer.MAX_VALUE;
for(int[] arr1 : this.arrList) {
for(int[] arr2 : island.arrList) {
if(arr1[0]==arr2[0]) {
// 행이 같은 경우
int start = Math.min(arr1[1], arr2[1]);
int end = Math.max(arr1[1], arr2[1]);
int len = 0;
for(int j=start+1 ; j<end ; j++) {
if(map[arr1[0]][j]!=0) {
len = 0;
// 바다가 아닌 부분 존재
break;
}else {
len++;
}
}
if(len>1) {
dist = Math.min(dist, len);
}
}else if(arr1[1]==arr2[1]) {
int start = Math.min(arr1[0], arr2[0]);
int end = Math.max(arr1[0], arr2[0]);
int len = 0;
for(int i=start+1 ; i<end ; i++) {
if(map[i][arr1[1]]!=0) {
len = 0;
break;
}else {
len++;
}
}
if(len>1) {
dist = Math.min(dist, len);
}
}
}
}
return dist;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("<");
for(int[]arr : arrList) {
sb.append("("+arr[0]+","+arr[1]+")_");
}
sb.append(">");
return "[ idx="+idx+", arr="+sb.toString()+" ]";
}
}
private void solution() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
islandList = new ArrayList<>();
map = new int[N][M];
int[][] dist;
for(int i=0 ; i<N ; i++) {
st = new StringTokenizer(br.readLine());
for(int j=0 ; j<M ; j++) {
int num = Integer.parseInt(st.nextToken());
if(num==1) {
map[i][j] = -1;
}else {
map[i][j] = num;
}
}
}
int islandCnt = changeMap();
dist = new int[islandCnt+1][islandCnt+1];
// printArr(map,0);
// 섬별 거리 arr
int tempMin = Integer.MAX_VALUE;
int[] tempMinArr = new int[2];
for(int i=0 ; i<islandCnt ; i++) {
for(int j=i+1 ; j<islandCnt; j++) {
int len = islandList.get(i).distance(islandList.get(j));
if(len<tempMin) {
tempMin = len;
tempMinArr = new int[] {i+1,j+1};
}
if(len==Integer.MAX_VALUE) {
dist[i+1][j+1] = -1;
dist[j+1][i+1] = -1;
}else {
dist[i+1][j+1] = len;
dist[j+1][i+1] = len;
}
}
}
int sum = makeBridge(dist, tempMinArr);
System.out.println(sum);
}
private int changeMap() {
int idx = 1;
for(int i=0 ; i<N ; i++) {
for(int j=0 ; j<M ; j++) {
if(map[i][j]==-1) {
bfs(i,j,idx);
idx++;
}
}
}
return idx-1;
}
int[][] dirs = {{1,0},{0,1},{-1,0},{0,-1}}; // 하, 우, 상, 좌
private void bfs(int row, int col,int idx) {
List<int[]> arrList = new ArrayList<>();
Queue<int[]> q = new LinkedList<>();
q.offer(new int[] {row,col});
while(!q.isEmpty()) {
int[] pos = q.poll();
if(map[pos[0]][pos[1]]==-1) {
map[pos[0]][pos[1]] = idx;
arrList.add(pos);
for(int[] dir : dirs) {
int nRow = pos[0] + dir[0];
int nCol = pos[1] + dir[1];
int[] arr = {nRow,nCol};
if(inRange(arr)) {
q.offer(arr);
}
}
}
}
Island island = new Island(idx,arrList);
islandList.add(island);
}
private boolean inRange(int[] arr) {
int row = arr[0];
int col = arr[1];
if(row>=0 && row<N && col>=0 && col<M)
return true;
return false;
}
private int makeBridge(int[][] dist, int[] start) {
int sum = 0;
boolean[] visited = new boolean[dist.length];
sum += dist[start[0]][start[1]];
visited[start[0]] = true;
visited[start[1]] = true;
while(!allTrue(visited)) {
int tempMin = Integer.MAX_VALUE;
int[] tempMinArr = new int[2];
for(int i=1 ; i<dist.length ; i++) {
for(int j=1 ; j<dist.length ; j++) {
if((visited[i]&&visited[j]) || (!visited[i]&&!visited[j])) {
// 둘다 방문 or 둘다 미방문 시
continue;
}
int len = dist[i][j];
if(len>1 && len<tempMin) {
tempMin = len;
tempMinArr[0] = i;
tempMinArr[1] = j;
}
}
}
visited[tempMinArr[0]] = true;
visited[tempMinArr[1]] = true;
// System.out.println(Arrays.toString(tempMinArr)+" : "+tempMin);
if(tempMin!=Integer.MAX_VALUE) {
sum+=tempMin;
}else {
return -1;
}
}
return sum;
}
private boolean allTrue(boolean[] visited) {
for(int i=1 ; i<visited.length ; i++) {
if(!visited[i])
return false;
}
return true;
}
private void printArr(int[][] arr,int start) {
for(int i=start ; i<arr.length ; i++) {
for(int j=start ; j<arr[0].length ; j++) {
System.out.printf("%2d ",arr[i][j]);
}
System.out.println();
}
}
}📇 결과
