[백준 BOJ][C++]2146번 다리 만들기 풀이: DFS & BFS

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

2146번: 다리 만들기

 

 

[ 풀이 과정 ]

 

1. 지도 정보를 입력받습니다. 

 

2. 각 대륙을 구분하기 위해 dfs()를 호출하여 대륙에 번호를 부여합니다. 

 

3. 번호 부여가 완료되면, 각 대륙으로부터 다른 대륙으로의 최단 걸이를 구하기 위해 bfs()를 호출합니다. 

 

4. bfs() 인자로 전달받은 대륙 번호에 해당하는 위치를 방문 표시 후 queue에 푸쉬합니다. 

 

5. queue의 현재 노드 curr를 pop 합니다. 

 

6. 현재 노드 curr로부터 동/서/남/북 방향 중 이동 가능한 방향에 대해 다음 노드를 탐색합니다. 

 

6-1. 만약 다음 노드가 아직 방문하지 않은 바다(map[ty][tx] == 0)라면 방문 표시 후, 해당 위치와 현재 노드의 거리 + 1을 거리로 한 노드를 queue에 푸시합니다. 

 

6-2. 만약 다음 노드가 바다가 아니면서 현재 탐색중인 대륙의 번호가 아니라면 최단 거리를 찾은 것이므로 ans를 갱신한 후, bfs()를 종료합니다. 

 

7. queue가 empty이거나 최단 거리를 찾을 때까지 5~6 과정을 반복합니다. 

 

 

 

#include<iostream>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<string>
#include<algorithm>
#include<queue>
#include<stack>

using namespace std;

int n;
int map[101][101];
bool visit[101][101] = { false, };
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
int ans = 987654321;

typedef struct node {
	int x;
	int y;
	int len;
};

void dfs(int x, int y, int set) {
	for (int i = 0; i < 4; i++) {
		int tx = x + dx[i];
		int ty = y + dy[i];

		if (tx < 0 || tx >= n || ty < 0 || ty >= n)
			continue;
		if (visit[ty][tx] || map[ty][tx] == 0)
			continue;
		visit[ty][tx] = true;
		map[ty][tx] = set;
		dfs(tx, ty, set);
	}
}

void bfs(int num) {

	queue<node> q;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (!visit[i][j] && map[i][j] == num) {
				visit[i][j] = true;
				q.push({ j, i , 0 });
			}
		}
	}

	while (!q.empty()) {
		node curr = q.front();
		q.pop();

		for (int i = 0; i < 4; i++) {
			int tx = curr.x + dx[i];
			int ty = curr.y + dy[i];

			if (tx < 0 || tx >= n || ty < 0 || ty >= n)
				continue;

			if (map[ty][tx] == 0 && !visit[ty][tx]) {
				visit[ty][tx] = true;
				q.push({ tx, ty, curr.len + 1 });
			}
			else if (map[ty][tx] != 0 && map[ty][tx] != num) {
				ans = min(ans, curr.len);
				return;
			}
		}
	}
}

void solution() {

	int continent = 1;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (!visit[i][j] && map[i][j] == 1) {
				visit[i][j] = true;
				map[i][j] = continent;
				dfs(j, i, continent);
				continent++;
			}
		}
	}

	for (int i = 1; i < continent; i++) {
		memset(visit, false, sizeof(visit));
		bfs(i);
	}
}

int main(void) {

	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}

	solution();

	cout << ans << endl;

	return 0;
}