백준 2146 ☆

문제

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

2146번: 다리 만들기

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main2146 {

	static int N;
	static int[][] map;
	static boolean[][] visited;
	static int groupNo = 2;
	static int[] ax = {1,-1,0,0};
	static int[] ay = {0,0,1,-1};
	static int min = Integer.MAX_VALUE;
	
	public static void bfs(int x, int y) {
		Queue<Node> q = new LinkedList<Node>();
		q.add(new Node(x,y,0));
		visited[x][y] = true;
		
		while(!q.isEmpty()) {
			Node temp = q.poll();
			
			for (int i=0; i<4; i++) {
				int nx = temp.x + ax[i];
				int ny = temp.y + ay[i];
				
				if (nx>=0 && ny>=0 && nx<N && ny<N && !visited[nx][ny]) {
					
					if (map[x][y] != map[nx][ny] && map[nx][ny] != 0) {
						min = Math.min(min, temp.dist);
						return;
					} else if (map[nx][ny] == 0) {
						visited[nx][ny] = true;
						q.add(new Node(nx, ny, temp.dist+1));
					}
				}
			}
		}
		
	}
	
	public static void grouping(int x, int y) {
		Queue<Node> q = new LinkedList<Node>();
		q.add(new Node(x, y, 0));
		visited[x][y] = true;
		map[x][y] = groupNo;
		
		while(!q.isEmpty()) {
			Node temp = q.poll();
			
			for (int i=0; i<4; i++) {
				int nx = temp.x + ax[i];
				int ny = temp.y + ay[i];
				
				if (nx>=0 && ny>=0 && nx<N && ny<N && !visited[nx][ny] && map[nx][ny] != 0) {
					visited[nx][ny] = true;
					map[nx][ny] = groupNo;
					q.add(new Node(nx, ny, 0));
				}
			}
		}
	}
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		map = new int[N][N];
		
		for (int i=0; i<N; i++) {
			for (int j=0; j<N; j++) {
				map[i][j] = sc.nextInt();
			}
		}
		
		visited = new boolean[N][N];
		for (int i=0; i<N; i++) {
			for (int j=0; j<N; j++) {
				if (map[i][j] == 1 && !visited[i][j]) {
					grouping(i,j);
					groupNo++;
				}
			}
		}
		
		visited = new boolean[N][N];
		for (int i=0; i<N; i++) {
			for (int j=0; j<N; j++) {
				if (map[i][j] != 0 && !visited[i][j]) {
					bfs(i, j);
					visited = new boolean[N][N];
				}
			}
		}
		
		System.out.println(min);
		
	}
	
	private static class Node{
		int x,y,dist;
		
		public Node(int x, int y, int dist) {
			super();
			this.x = x;
			this.y = y;
			this.dist = dist;
		}
	}
}

1. 각각의 섬을 우선적으로 구분해줘야 쉽게 풀수 있는 문제다. 섬구분없이 해내려고만 하다보니 처음에 막혔다.

 

2. 연속된 1이 있는 그룹을 하나의 섬으로 보고 그 그룹을 같은 수로 그룹핑해준다. 그룹핑이 끝나면 bfs로 바다일경우 Node의 dist변수를 1씩 증가하며 큐에 새로 추가해준다. 다른 섬을 만날경우 최소값 비교를 통해 최소값을 min에 넣는다.

 

3. 중요한 포인트인 부분은 visited를 중간에 초기화 해주는것, 섬부터 그룹핑 하는것 두가지다.