[백준 2146] 다리 만들기 (자바)

https://www.acmicpc.net/problem/2146

2146번: 다리 만들기

 

난이도 : 골드 3

 

매우 간단한 방법으로 풀었기 때문에 시간 복잡도 등은 최적화되지 않은 풀이입니다.

같은 섬은 DFS로 같은 번호로 묶었습니다. 그 후 모든 섬의 좌표에서 BFS로 다리를 만들었습니다.

이 경우 스택을 통해 모든 좌표를 저장했으며 큐, 리스트, 배열 등 아무 자료 구조를 사용해도 무방합니다.

---

전역 변수 

int n = 입력받은 맵의 크기

int map[][], island[][] = 입력받은 맵, 같은 섬끼리 묶은 배열
boolean visit[][] = 섬끼리 묶을 때 방문 체크
Stack<Point> start = 모든 섬의 모든 좌표
int dx[], dy[] = 이동을 위한 좌표
int answer = 가장 짧은 길이(답)

메소드

void main 

입력을 받으며 스택에 모든 1의 좌표를 저장합니다. 그 후 1번 섬부터 DFS를 통해 다 같은 번호로 묶습니다.

섬을 모두 묶었다면 스택에 있는 좌표를 하나씩 꺼내 다리를 만듭니다.

(tie, bridge 호출)

 

void tie

같은 섬을 묶습니다. DFS로 방문 좌표에서 상, 하, 좌, 우로 이동하며 1이면 같은 섬이므로 파라미터로 받은 번호로 묶습니다. island에 섬의 번호를 저장합니다.

(tie 호출)

 

void bridge

스택에 있던 좌표를 기준으로 다리를 세웁니다. 이 과정은 BFS로 진행됩니다.

현재 좌표에서 상, 하, 좌, 우로 이동하며 현재 섬과 다른 번호의 섬을 만날 때까지 진행됩니다.

다른 섬에 도착했다면 answer를 갱신하여 최솟값을 찾습니다.

(check 호출)

 

boolean check

현재 좌표가 유효한 좌표인지 확인합니다.

 

class Point

x, y 좌표와 다리의 길이 count를 저장하는 클래스입니다.

	import java.io.BufferedReader;
	import java.io.InputStreamReader;
	import java.util.LinkedList;
	import java.util.Queue;
	import java.util.Stack;
	import java.util.StringTokenizer;
	public class p2146 {
	static int n, map[][], island[][];
	static boolean visit[][];
	static Stack<Point> start;
	static int dx[] = {-1,1,0,0};
	static int dy[] = {0,0,-1,1};
	static int answer = Integer.MAX_VALUE;
	public static void main(String[] args) throws Exception {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer stz;
	n = Integer.parseInt(br.readLine());
	map = new int[n][n];
	island = new int[n][n];
	visit = new boolean[n][n];
	start = new Stack<>();
	for(int i = 0; i < n; i++) {
	stz = new StringTokenizer(br.readLine());
	for(int j = 0; j < n; j++) {
	map[i][j] = Integer.parseInt(stz.nextToken());
	if(map[i][j] == 1)
	start.push(new Point(i, j, 0));
	}
	}
	int number = 1;
	for(int i = 0; i < n; i++) {
	for(int j = 0; j < n; j++) {
	if(map[i][j] == 1 && !visit[i][j]) {
	island[i][j] = number;
	visit[i][j] = true;
	tie(i, j, number);
	number++;
	}
	}
	}
	while(!start.isEmpty()) {
	Point now = start.pop();
	bridge(now.x, now.y);
	}
	System.out.println(answer-1);
	}
	public static void tie(int x, int y, int number) {
	for(int i = 0; i < 4; i++) {
	int nx = x + dx[i];
	int ny = y + dy[i];
	if(check(nx, ny) && !visit[nx][ny] && map[nx][ny] == 1) {
	island[nx][ny] = number;
	visit[nx][ny] = true;
	tie(nx, ny, number);
	}
	}
	}
	public static void bridge(int x, int y) {
	Queue<Point> q = new LinkedList<>();
	q.offer(new Point(x, y, 0));
	int number = island[x][y];
	visit = new boolean[n][n];
	visit[x][y] = true;
	while(!q.isEmpty()) {
	Point now = q.poll();
	if(now.count >= answer)
	return;
	if(island[now.x][now.y] != 0 && island[now.x][now.y] != number) {
	answer = Math.min(answer, now.count);
	return;
	}
	for(int i = 0; i < 4; i++) {
	int nx = now.x + dx[i];
	int ny = now.y + dy[i];
	if(check(nx, ny) && !visit[nx][ny] && island[nx][ny] != number) {
	visit[nx][ny] = true;
	q.offer(new Point(nx, ny, now.count + 1));
	}
	}
	}
	}
	public static boolean check(int x, int y) {
	return x >= 0 && y >= 0 && x < n && y < n;
	}
	static class Point{
	int x, y, count;
	Point(int x, int y, int count) {
	this.x = x;
	this.y = y;
	this.count = count;
	}
	}
	}

view raw p2146.java hosted with ❤ by GitHub