2146 다리만들기

2146 다리만들기

BFS를 통해서 여러 선택지 중 최단거리를 구하는 문제

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

1. 문제

---

간단 설명

• 다음과 같은 섬 3개가 있을 때, 다른 섬을 잇는 다리 하나만을 놓는다
• 근데, 그 다리가 가장 짧은 다리 하나를 놓아 두 대륙을 연결하는 방법 찾기

이런식으로 3칸 놓으면 두 대륙이 연결된다

2. 문제 분석

---

알고리즘

1. 입력받기
    - 섬 라벨링을 가시성을 위해 1부터 시작함, 육지와 번호가 겹치므로, 육지 번호를 -1로 바꿨음
2. BFS를 통해 연결된 땅들은 번호를 붙인다. 연결된 땅들은 같은 라벨을 가진다. 
    - 바다가 아니고, 방문한 적이 없는 땅이라면 이 땅부터 BFS를 돌려 번호를 붙인다(`Labeling(int y, int x, int label)`)
    2-1. 큐에 현재 좌표를 넣고 현재 좌표를 방문처리한다. 또한 맵에도 이 라벨을 붙여 맵을 갱신한다
    2-2. 큐가 빌때까지 다음을 반복한다
        2-2-1. 큐의 맨 앞을 꺼내 이 노드의 4방향으로 탐색한다. 
        2-2-2. 경계를 벗어났다면 패스
        2-2-3. 바다라면 패스
        2-2-4. 이미 방문했던곳이라면 패스
        2-2-5. 위 조건들을 모두 통과했다면 방문처리 후, 맵에 라벨을 갱신하고, 큐에 넣는다 
    - 2번이 종료되면 각 덩어리별로 번호가 부여되어있을것임.
3. 같은 라벨을 가진 섬의 땅 좌표들을 모두 큐에 넣고 최단경로 탐색을 돌린다.
    3-1. 방문 배열을 초기화한다
    3-2. 큐에 현재 라벨 번호와 같은 땅들을 모두 넣는다
    3-3. 이 큐로 BFS를 돌린다. 2번과 알고리즘은 같으므로 생략함
        - 경계처리와, 방문했던곳은 패스하는 부분은 같지만, 
        map[dy][dx] = 0 인 부분을 탐색해야한다(다리를 놓는 알고리즘이므로)
        - 또한, 큐에서 현재 꺼낸 노드가 
        바다도 아니고, 자기와 같은 라벨의 섬이 아닌 경우 칸 개수를 리턴해줘야한다. 이때 -1 해준다.
        (이미 섬에 올라와있으므로 다리 - 1개)
4. 최단경로를 출력한다

필요변수

맵 크기 N

2차원 맵 배열 map, 방문 여부 체크용 2차원 배열 visited

라벨링용 번호 label, 최소값 체크용 answer

4방향 탐색용 direct[4][2] 배열

y, x좌표와 몇번 이동했는지 기록하기 위한 구조체 node

주의점

• BFS를 두번 돌려야하므로, 방문체크 배열과 맵 갱신을 언제 할 것인지 잘 고려해야한다
• 또한, 경계처리, 맵 조건 확인 등을 잘 고려해야한다.

라벨링할때는 바다인 부분은 패스하지만, 섬을 놓을땐 체크해야한다.(다리를 지어야하므로)

• 방문 배열을 초기화 할 타이밍 고려

3. 소스코드

---

#include <iostream>
#include <queue>
#include <algorithm>
#include <string.h>

using namespace std;

#define MAX 101

int N;
int map[MAX][MAX];
int visited[MAX][MAX];
int label = 1;
int answer = 21e8;

int direct[4][2] = { 1,0,0,1,-1,0,0,-1};

struct node {
	int y;
	int x;
	int level;
};

// BFS를 이용해 같은 덩어리끼리는 같은 번호를 부여하는 함수
void Labeling(int y, int x, int label) {
	queue<node> qu;
	qu.push({ y,x,0 });
	visited[y][x] = 1;
	map[y][x] = label;
	
	while (!qu.empty()) {
		node now = qu.front();
		qu.pop();

		for(int t=0; t<4; t++){
			int dy = direct[t][0] + now.y;
			int dx = direct[t][1] + now.x;
			
			if (dy < 0 || dx < 0 || dy >= N || dx >= N) continue;
			if (map[dy][dx] == 0) continue;
			if (visited[dy][dx] == 1) continue;

			visited[dy][dx] = 1;
			map[dy][dx] = label;
			qu.push({ dy,dx,0 });
		}
	}

}

// label 번호의 섬으로부터 다른 섬까지의 최단거리 계산
int BFS(int label) {
	// 먼저 큐에 현재 번호의 섬의 땅을 모두 넣음
	memset(visited, 0, sizeof(visited));

	queue<node> qu;
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			if (map[y][x] == label) {
				qu.push({ y,x,0 });
				visited[y][x] = 1;
			}
		}
	}
	while (!qu.empty()) {
		node now = qu.front();
		qu.pop();

		// 새로운 땅을 밟았다면
		if (map[now.y][now.x] != 0 && map[now.y][now.x] != label) {
			return now.level - 1; // 이미 섬에 올라와있으므로 다리 - 1개
		}

		for (int t = 0; t < 4; t++) {
			int dy = direct[t][0] + now.y;
			int dx = direct[t][1] + now.x;

			if (dy < 0 || dx < 0 || dy >= N || dx >= N) continue;
			if (visited[dy][dx] == 1) continue;

			visited[dy][dx] = 1;
			qu.push({ dy,dx,now.level+1 });
		}
	}
	return 21e8;
}

int main() {
	// 1. 입력받기
	freopen_s(new FILE*, "input.txt", "r", stdin);

	cin >> N;
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			int tmp; cin >> tmp;
			if (tmp == 1) {
				map[y][x] = -1;
			}
		}
	}

	// 2. 같은 덩어리끼리 묶어 번호를 붙인다
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
		
			if (map[y][x] == -1 && visited[y][x] == 0) {
				Labeling(y, x, label);
				label++; 
			}

		}
	}

	// 섬의 개수만큼 최단거리를 계산
	for (int i = 1; i <= label; i++) {
		answer = min(answer, BFS(i));
	}
	cout << answer;

	return 0;
}