[백준/C++]#2146 - 다리 만들기

풀이

#include <cstdio>
#include <queue>
using namespace std;
 
int N;
int a[101][101];
int g[101][101];
int d[101][101];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
 
int main() {
	scanf("%d", &N);
	for (int i=0; i<N; i++) {
		for (int j=0; j<N; j++) {
			scanf("%d", &a[i][j]);
		}
	}
	int cnt = 0;	
	for (int i=0; i<N; i++) {
		for (int j=0; j<N; j++) {
			if (a[i][j] == 1 && g[i][j] == 0) {		// 그룹별 분류
				queue<pair<int,int>> q;
				q.push(make_pair(i, j));
				g[i][j] = ++cnt;
				while (!q.empty()) {
					int n = q.front().first;
					int m = q.front().second;
					q.pop();
					for (int k=0; k<4; k++) {
						int nx = n + dx[k];
						int my = m + dy[k];
						if (0<=nx && nx<N && 0<=my && my<N) {
							if (a[nx][my]==1 && g[nx][my]==0) {
								g[nx][my] = cnt;
								q.push(make_pair(nx, my));
							}
						}
					}
				}
			}
		}
	}
	queue<pair<int,int>> q;		// a 배열의 값이 1일 때 큐에 대입
	for (int i=0; i<N; i++) {
		for (int j=0; j<N; j++) {
			d[i][j] = -1;
			if (a[i][j] == 1) {
				q.push(make_pair(i, j));
				d[i][j] = 0;
			}
		}
	}
	while (!q.empty()) {		// 길이에 해당하는 bfs
				int n = q.front().first;
				int m = q.front().second;
				q.pop();
				for (int k=0; k<4; k++) {
					int nx = n + dx[k];
					int my = m + dy[k];
					if (0<=nx && nx<N && 0<=my && my<N) {
						if (d[nx][my]==-1) {
							d[nx][my] = d[n][m] + 1;
							g[nx][my] = g[n][m];
							q.push(make_pair(nx, my));
						}
					}
				}
	}
	int ans = -1;
	for (int i=0; i<N; i++) {	// 최소값 찾기
		for (int j=0; j<N; j++) {
			for (int k=0; k<4; k++) {
				int nx = i + dx[k];
				int my = j + dy[k];
					if (0<=nx && nx<N && 0<=my && my<N) {
						if (g[i][j] != g[nx][my]) {
							if (ans == -1 || ans > d[i][j] + d[nx][my]) {
								ans = d[i][j] + d[nx][my];
							}
						}
					}
			}
		}	
	}
	printf("%d", ans);
	return 0;
}

개념

ans 즉 구하는 값은 길이 중 최솟값이다. (ex. 3, 4, 5 ... -> 3)

for문을 통해 모든 경우를 비교해서 가장 작은 길이 값을 찾아야한다.

 

ans의 초기화 값에 따라 값의 제대로 된 비교가 안될 수도 있다. (ex. -1(초기화값), 3, 4, 5 ... -> -1)

따라서 if 문에서 ans = -1일 때를 OR (||) 연산한다.

무조건 처음 연산을 진행하게 되면, 초기값을 신경 쓸 필요 없다.

---

+a

이번 문제는 ans 값의 최대값이 200도 안되는 작은 수이다.

따라서 ans = 200 등으로 초기화 하는 방법도 있다.

그러면 굳이 OR 연산 없이 바로 ans의 최솟값을 찾을 수 있다.

---

풀이

 

섬 내부의 bfs와 섬 외부의 bfs를 구분해야한다.

각각 in-bfs, out-bfs 라고 부르겠다.

 

이전처럼 모든 a 배열 값이 1인 구간에 out-bfs 방식을 사용해본다.

out-bfs 사용시

 

섬과 섬이 만날 때 bfs는 종료될 것이다.

각 이동마다 +1 하면 서로 만나는 부분의 d 배열 합으로 최소 길이가 예상된다.

 

하지만 이것만으로는 부족하다.

 

우리가 원하는 것은 섬과 섬이 만나는 값 사이의 최소 값이다.

 

하지만 bfs 도중의 값 사이의 최소 값도 존재한다.

이 두 값을 구분하기 위해 문제를 해결하기 위해 중요한 조건이 충족되어야 한다.

섬들은 각각 구분되어야 한다

 

섬의 구분 (in-bfs)

in-bfs를 섬 내부에서 사용하면 섬 안의 모든 수를 왼쪽 그림과 같이 초기화 할 수 있다.

이중 for문을 사용해서, main 함수 내의 bfs 실행마다 cnt를 +1 하며 증가시키면 된다.

 

그리고 이 섬들을 out-bfs하면 오른쪽 그림처럼 된다.

이는 섬들이 만나는 부분과 그렇지 않은 부분을 구분해준다.

 

결과는 다음과 같은 과정을 거치면 된다.

서로 다른 두 섬이 만나는 경우 -> 만나는 두 점에 해당하는 길이 값을 더한다