백준 2146 : 다리 만들기

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

1.접근

• 다리를 만들기 위해서는, 다리의 시작점(대륙)과 다리의 끝점(대륙)을 알아야 한다.
  => 대륙을 구분하기 위한 그래프 탐색 1회를 진행한다 (연결요소 문제 참고) DFS를 사용했다.
• 하나의 대륙을 정하고, 그 대륙으로부터 다른 대륙까지의 거리를 카운트하여 가장 짧은 곳을 다리로 만든다.
  => 가장 짧은 길이를 구하기 위해 2번째 그래프 탐색을 진행한다. 최소 길이이므로 BFS를 사용한다.

• 대륙의 숫자를 1부터 하나씩 늘려가면서 저장해준다. (가장 처음에는 -1값을 넣어 강(0)과 구분시킨다)
• ★ BFS에서 distance 값을 늘려가면서 대륙간의 거리를 구하는데, 계속해서 반복문을 돌릴 경우, distance값이 이상하게 설정된다. 따라서, for문을 하나 더 만들어서, 대륙으로부터 거리가 같은 지점들끼리 반복하도록 한다. q는 뒤에서 넣어서 앞에서부터 꺼내므로, 거리가 같은 지점들을 넣은 후 그 개수를 저장한 다음, 그 개수만큼만 읽도록 한다.

2. 나의 풀이

#include <iostream>
#include <queue>
#include <cstring>
#define MAX 101
using namespace std;

int n;
int graph[MAX][MAX];
bool visited[MAX][MAX];

int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0, - 1,1 };

int min(int x, int y) { if (x > y) return y; else return x; }
void dfs(int x,int y,int num) {
	int nx, ny;

	graph[x][y] = num;
	visited[x][y] = true;

	for (int i = 0; i < 4; i++) {
		nx = x + dx[i];
		ny = y + dy[i];
		if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
			if (graph[nx][ny]!=0&&!visited[nx][ny]) { //강이 아닌데, 아직 밟지 않았다면 같은 대륙임
				visited[nx][ny] = true;
				dfs(nx, ny, num);
			}
		}
	}
	return;
}

int bfs(int num) {
	queue<pair<int, int>> q;
	int x,y, nx, ny;
	int distance = 0; //대륙부터 시작하므로 초기값은 0
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (graph[i][j] == num) { //대륙으로부터의 거리를 구하기 위해, 대륙부터 q에 넣고 시작
				q.push(make_pair(i, j));
				visited[i][j] = true;
			}
		}
	}

	while (!q.empty()) {
		int s = q.size();
		for (int t = 0; t < s; t++) { //대륙으로부터 거리가 같은 지점만큼만 q에서 꺼내기
			x = q.front().first;
			y = q.front().second;
			q.pop();

			for (int i = 0; i < 4; i++) {
				nx = x + dx[i];
				ny = y + dy[i];
				if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
					if (graph[nx][ny] != 0 && graph[nx][ny] != num) { //새로운 대륙 도착
						//cout << "(" << nx << "," << ny << ") 리턴값 : " << distance << "\n";
						return distance;
					}
					if (graph[nx][ny] == 0 && !visited[nx][ny]) { //강
						visited[nx][ny] = true;
						q.push(make_pair(nx, ny));
					}
				}
			}
		}
		distance++; //한 칸 넘어가기
	}
	return 0;
}

int main() {
	cin >> n;
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> graph[i][j];
			if (graph[i][j] == 1) graph[i][j] = -1; //대륙들을 구분해주기 위해 처음엔 -1을 넣어주고 이후에 1,2,3 ... 의 값으로 채워줌
		}
	}

	int num = 1;
	for (int i = 0; i < n; i++) { //대륙 나누기
		for (int j = 0; j < n; j++) {
			if (graph[i][j] == -1&&!visited[i][j]) {
				dfs(i, j, num);
				num++;
			}
		}
	}

	int ret = -1;
	for (int i = 1; i < num; i++) {
		memset(visited, false, sizeof(visited));
		if (ret == -1) ret = bfs(i); //가장 첫값은 그냥 넣기
		else ret = min(ret, bfs(i)); // 최솟값
	}
	
	cout << ret << "\n";
}