[Baekjoon]2146.다리만들기

2146.다리만들기 

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

2146번: 다리 만들기

---

dfs와 bfs를 모두 사용하여 풀 수 있는 문제였다. 크게 두 부분으로 나누어서 풀었다.

 

1. 섬을 구분짓는다.(dfs)
2. 서로 다른 섬을 잇는 다리의 최솟값을 구한다.(bfs)

먼저 섬을 구분짓기 위해서 육지인 부분을 -1로 모두 바꾼다. (섬 라벨링을 1부터 하기 위해서)

dfs를 수행하면서 -1인 부분을 라벨링할 인덱스 idx값으로 바꿔주고 dfs가 끝나면 idx++ 을 해서 다음 섬의 라벨링을 하도록 한다. 이 부분은 기존에 풀었던 dfs 문제들과 거의 같아서 어렵지 않게 풀었다. 

 

다음은 섬의 각 지점에서 bfs를 수행하여 다른 섬으로 가는 최단거리를 구한다. dist배열에 거리를 저장하면서 최솟값을 갱신한다. bfs를 시작한 지점의 섬 라벨과 도착한 지점의 섬 라벨이 다르고 바다가 아니면 탐색을 멈추고 최솟값을 갱신한다. 

 

처음에는 bfs가 끝나면  dist, visited, min값을 초기화해줬더니 답이 계속 0이 나왔다. 그래서 bfs를 하기 전에 초기화를 해줬더니 답이 제대로 나왔다. 이거 고치는데만 1시간 넘게 쓴거 같다.. 

 

다른 사람들의 풀이에 비해 메모리를 많이쓰고 시간도 훨씬 많이 걸리긴 하지만 직관적으로 이해하기는 내 풀이가 쉬웠다.(내가 생각한 풀이라서 그럴수도..) 

 

private static void explore() { // 섬 라벨링. 
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] == -1 && !visited[i][j]) {
					map[i][j] = idx;
					visited[i][j] = true;
					dfs(j, i);
					idx++;
				}
			}
		}
	}
    
private static void dfs(int x, int y) {
		for (int i = 0; i < 4; i++) {
			int nextX = x + dx[i];
			int nextY = y + dy[i];
			if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= N) {
				continue;
			}
			if (visited[nextY][nextX] || map[nextY][nextX] == 0) {
				continue;
			}
			map[nextY][nextX] = idx;
			visited[nextY][nextX] = true;
			dfs(nextX, nextY);
		}
	}

dfs를 통해 섬을 라벨링.

 

private static void buildBrg() {  // 다리 놓기. 
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				min = Integer.MAX_VALUE;
				for (boolean[] row : visited) {
					Arrays.fill(row, false);
				}
				for (int[] row : dist) {
					Arrays.fill(row, 0);
				}
				if (map[i][j] != 0 && !visited[i][j]) {
					visited[i][j] = true;
					bfs(j, i);
					ans = Math.min(ans, min);
				}
			}
		}
	}
private static void bfs(int x, int y) {
		Queue q = new LinkedList<>();
		q.add(new Point(x, y));

		while (!q.isEmpty()) {
			Point p = q.poll();
			int curX = p.x;
			int curY = p.y;
			for (int i = 0; i < 4; i++) {
				int nextX = curX + dx[i];
				int nextY = curY + dy[i];
				if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= N) {
					continue;
				}
				if (visited[nextY][nextX] || map[nextY][nextX] == map[y][x]) {	
					continue;
				}
				if (map[y][x] != map[nextY][nextX] && map[nextY][nextX] != 0) {
					min = Math.min(min, dist[curY][curX]);
					break;
				}
				visited[nextY][nextX] = true;
				dist[nextY][nextX] = dist[curY][curX] + 1;
				q.add(new Point(nextX, nextY));
			}
		}
	}

bfs로 다리길이의 최솟값 갱신.

 

<전체코드>