1. 문제 링크 및 문제
문제링크 : https://www.acmicpc.net/problem/2146
1-1 문제 요약
:N*N크기의 맵에 바다와 여러개의 육지정보가 담겨져있음. 바다=0, 육지=1
육지와 육지 사이의 최단거리를 구하는 문제 (각 육지: 상하좌우로 연결된 1)
2. 해결 방법 생각해보자 ...
1. 육지 구분 : 연결된 섬들끼리 다른 수로 표시해주고, 가장자리 좌표들을 구함.
1-1. 반복문을 돌려서 각 육지의 번호를 다르게 표시
1-2. 가장자리가 아니라면 최단거리가 아니므로 , 가장자리에 있는 좌표들을 구함.
2. 가장자리 좌표들 사이의 최단거리를 구함
ex ) 백준 예시1
0,0 ~ N,N 방문 중 ...
1. (0,0) 에서 1이 나오면 BFS를 돌려 연결된 육지를 1 로 표시
2. 한 번 BFS 가 끝나면 다른 섬이므로 육지번호 ++
3. 다시 이어서 방문하다 (0,7)에서 1이 나오면 연결된 육지를 2 으로 표시 ...
3. 코드
해결방법순 코드
- 좌표와 거리 저장할 클래스 생성
static class Point{
int x;
int y;
int dist;
Point(int x, int y, int dist){
this.x = x;
this.y = y;
this.dist = dist;
}
}1. 육지 구분
- (0,0) ~ (N,N) 까지 방문, 육지나오면 DivideLand()
DivideLand() : (i,j)에 연결된 육지를 전부 방문 (BFS)
int LandNum = 1;
for (int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(map[i][j] == 1 && !visited[i][j]){
DivideLand(i,j,LandNum++);
}
}
}- (i,j)의 상하좌우로 움직이며 연결된 육지를 방문하여 LandNum으로 섬 표시,
가장자리에 있다면 edges 에 추가
public static void DivideLand(int x, int y,int LandNum){
Queue<Point> que = new LinkedList<>();
que.offer(new Point(x,y,0));
visited[x][y] = true;
while(!que.isEmpty()){
Point now = que.poll();
map[now.x][now.y] = LandNum;
boolean FindEdge = false;
for (int i=0;i<4;i++){
int xx = now.x + dx[i];
int yy = now.y + dy[i];
if (xx <0 || xx>=N || yy<0 || yy>=N)continue;
if(!FindEdge && map[xx][yy] == 0){
edges.add(now);
FindEdge = true;
}
if (map[xx][yy] == 1 && !visited[xx][yy]){
visited[xx][yy] = true;
que.offer(new Point(xx,yy,0));
}
}
}
}2. 가장자리에 있는 좌표들의 최단거리 구하기
- 가장자리 좌표 ~ 다른섬까지의 거리 계산 (*가장자리 좌표 개수만큼 계산)
for(Point edge : edges){
MakeBridge(edge.x, edge.y, map[edge.x][edge.y]);
}- BFS 돌리며 최단거리 계산
public static void MakeBridge(int x, int y, int NowNum){
visited = new boolean[N][N];
Queue<Point> que = new LinkedList<>();
que.offer(new Point(x,y,0));
visited[x][y] = true;
while(!que.isEmpty()){
Point now = que.poll();
if(now.dist >= minDistance) return;
for (int i=0;i<4;i++){
int xx = now.x + dx[i];
int yy = now.y + dy[i];
if (xx <0 || xx>=N || yy<0 || yy>=N)continue;
if(map[xx][yy] != NowNum && map[xx][yy] != 0){
minDistance = Math.min(minDistance, now.dist);
return;
}
if (map[xx][yy] == 0 && !visited[xx][yy]){
visited[xx][yy] = true;
que.offer(new Point(xx,yy,now.dist+1));
}
}
}
}- 전체코드
import java.util.*;
import java.io.*;
public class Main {
static int minDistance = Integer.MAX_VALUE;
static int[][] map ;
static ArrayList<Point> edges = new ArrayList<>();
static boolean[][] visited;
static int N;
static int[] dx = {-1,0,1,0};
static int[] dy = {0,1,0,-1};
static Queue<Point> que = new LinkedList<>();
public static void main(String[] args) throws Exception{
// 값 입력받기 -- >
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
map = new int[N][N];
visited = new boolean[N][N];
for(int i=0; i<N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for(int j=0; j<N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
// <-- 값 입력받기
// 섬 구분하기 -->
int LandNum = 1;
for (int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(map[i][j] == 1 && !visited[i][j]){
DivideLand(i,j,LandNum++);
}
}
}
// <-- 섬 구분하기
// 섬 사이 최단거리 구하기
for(Point edge : edges){
MakeBridge(edge.x, edge.y, map[edge.x][edge.y]);
}
System.out.println(minDistance);
}
// 연결된 육지들을 LandNum 으로 표시 ( LandNum = 1,2,3, ... )
public static void DivideLand(int x, int y,int LandNum){
Queue<Point> que = new LinkedList<>();
que.offer(new Point(x,y,0));
visited[x][y] = true;
while(!que.isEmpty()){
Point now = que.poll();
map[now.x][now.y] = LandNum;
boolean FindEdge = false;
for (int i=0;i<4;i++){
int xx = now.x + dx[i];
int yy = now.y + dy[i];
if (xx <0 || xx>=N || yy<0 || yy>=N)continue;
if(!FindEdge && map[xx][yy] == 0){
edges.add(now);
FindEdge = true;
}
if (map[xx][yy] == 1 && !visited[xx][yy]){
visited[xx][yy] = true;
que.offer(new Point(xx,yy,0));
}
}
}
}
// 가장자리 좌표부터 다른 섬까지의 최단거리를 구함
public static void MakeBridge(int x, int y, int NowNum){
visited = new boolean[N][N];
Queue<Point> que = new LinkedList<>();
que.offer(new Point(x,y,0));
visited[x][y] = true;
while(!que.isEmpty()){
Point now = que.poll();
if(now.dist >= minDistance) return;
for (int i=0;i<4;i++){
int xx = now.x + dx[i];
int yy = now.y + dy[i];
if (xx <0 || xx>=N || yy<0 || yy>=N)continue;
if(map[xx][yy] != NowNum && map[xx][yy] != 0){
minDistance = Math.min(minDistance, now.dist);
return;
}
if (map[xx][yy] == 0 && !visited[xx][yy]){
visited[xx][yy] = true;
que.offer(new Point(xx,yy,now.dist+1));
}
}
}
}
static class Point{
int x;
int y;
int dist;
Point(int x, int y, int dist){
this.x = x;
this.y = y;
this.dist = dist;
}
}
}!
와........ 파이썬으로 풀 땐 1시간 걸렸는데, 자바는 알아도 2시간 걸리네....
자바가 뭔가 코드 작성하는 맛은 더 있어서 재밌었다 ! ㅋㅋㅋ
너무 복잡한 것 같지만.... 굉장히 최적화하려 노력하고 노력했는데..
참고링크 작성자님의 코드를 보고 어메이징깔끔해졌다.👍
