알고리즘 공부/C++

[G3] 백준 2146번 다리 만들기 C++ 너비 우선 탐색, 플러드 필, 우선순위 큐

마달랭 2024. 12. 16. 14:52
반응형

리뷰

 

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

섬을 그룹화 한 뒤 섬끼리 이을 수 있는 가장 짧은 경로를 구하는 문제

그룹화 후 거리를 구하는 함수에서 일반 큐를 사용했더니 AC를 받지 못했다.

디버깅 후 우선순위 큐를 사용하여 AC를 받은 문제, 디버깅의 중요성을 새삼 깨달았다.

함수를 나누어 구현을 하다 보니 생각보다 로직이 길어진 문제, 100줄까지 갈지는 몰랐다.

 

 

전역 변수

  • n : 맵의 한 변의 길이를 저장할 정수형 변수
  • g : 각 섬을 그룹화 하기 위해 사용할 정수형 변수
  • ans : 각 섬을 잇기 위한 최소한의 거리를 저장할 정수형 변수
  • lst : 맵 정보를 저장하기 위한 정수형 2차 배열
  • v : 그룹화 및 거리를 구할 때 사용할 방문 배열
  • vg : 그룹 번호로 방문 표시를 하기 위한 배열
  • dx, dy : 4방향 탐색을 위한 방향 배열
  • Pos : 거리를 구할 때 최소 값을 그리디하게 구하기 위한 구조체, 거리를 기준으로 오름차순 정렬한다.

 

함수

1. input

void input()

 

입력을 받기 위한 함수

  1. n값을 입력 받고, n * n크기의 맵 정보를 lst배열에 입력 받아준다.

 

2. grouping

void grouping() {
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (v[i][j] || !lst[i][j]) continue;
			floodfill(i, j, ++g);
		}
	}
}

 

각 섬들을 그룹화 해주기 위한 함수

  1. n * n크기의 맵 정보를 순회하며 방문처리 되지 않았고 0이 아니라면 그룹화를 진행한다.
  2. floodfill함수에 시작 좌표 i, j와 그룹 번호를 전위 증가시켜 전달해 준다.
  3. 모든 섬에 대해 그룹화를 진행할 때 까지 해당 탐색을 진행해 준다.

 

3. floodfill

void floodfill(int sx, int sy, int g)

 

플러드 필을 통해 섬 내에서 갈 수 있는 육지를 모두 그룹화 해주는 함수

  1. 매개변수로 시작 좌표 sx, sy와 마킹할 그룹의 번호 g를 입력 받는다.
  2. Pos타입의 큐 q에 sx, sy좌표를 push해준다.
  3. sx, sy좌표에 방문처리를 해주고, 맵 상에서 sx, sy좌표의 값을 g로 변경해 준다.
  4. 큐가 빌 때 까지 while루프를 실행하고, 매 루프 시마다 큐에서 요소를 하나씩 빼준다.
  5. 4방향 탐색을 진행하며 맵의 범위 안에 있으며 방문처리를 하지 않았고 0이 아니라면 이동을 진행해 준다.
  6. 이동한 좌표에 방문 처리를 해주고, 맵에서 해당 좌표의 값을 g로 변경해 준다.
  7. 큐에 이동한 좌표를 push해주고 while 루프가 종료될 때 까지 그룹화를 진행해 준다.

 

4. getDist

void getDist()

 

각 섬끼리의 거리를 구하기 위한 함수

  1. vg의 0번 인덱스를 1로 초기화 해준다, 이는 0에서는 탐색을 하지 않기 위함이다.
  2. n * n크기의 맵을 순회하며 맵에서의 그룹이 이미 방문한 그룹이라면 continue처리해 준다.
  3. 아직 방문하지 않은 그룹이라면 방문처리 후 탐색을 진행해 주어야 한다.
  4. 탐색에 앞서 memset메서드를 통해 사용했던 방문 배열 v를 0으로 초기화 해준다.
  5. conn함수에 시작 좌표인 i, j와 맵 상에서의 i, j좌표의 그룹 번호를 매개변수로 전달한다.

 

5. conn

void conn(int sx, int sy, int g)

 

각 섬을 연결하면서 연결을 위한 다리의 최소 길이를 구하기 위한 함수

  1. Pos타입의 우선순위 큐 q를 초기화 해준 뒤, 시작 좌표 sx, sy와 시작 시간 0을 push해준다.
  2. 시작 지점인 sx, sy에 방문처리 후 큐가 빌 때 까지 순환하는 루프를 생성해준다.
  3. 매 루프마다 q에서 요소를 한개씩 빼주어 Pos타입의 변수 pos로 초기화 해준다.
  4. pos의 x, y, t를 각각 정수형 변수 cx, cy, ct에 초기화 해준다.
  5. 기저 조건으로 ct가 ans보다 크거나 같을 경우 더 이상 탐색할 필요가 없으므로 continue 처리해준다.
  6. 4방향 탐색을 하며 맵의 범위를 벗어나지 않았고, 방문처리 되지 않은 부분이라면 이동을 진행한다.
  7. 이동한 좌표에 방문처리 후 만약 같은 그룹이라면 시간을 증가시키지 않고 큐에 push해준다.
  8. 0을 만났다면 시간을 증가시킨 후에 큐에 push해준다.
  9. 0도 아니고 같은 그룹도 아니라면 ans와 ct중 더 작은 값을 ans에 저장해 준다.

 

문제풀이

  1. input함수를 통해 n과 맵 정보를 입력 받아준다.
  2. grouping함수를 통해 각 섬을 1부터 번호를 받아 그룹화를 진행해 준다.
  3. getDist함수를 통해 섬 간의 가장 짧은 거리를 구해 ans에 저장해 준다.
  4. ans에 저장된 값을 출력해 준다.

 

트러블 슈팅

  • conn함수에서 사용한 큐를 일반 큐로 사용했더니 그리디하게 접근할 수가 없었다.
  • 섬간의 최소 거리를 구할 때에는 우선순위 큐를 통해 거리 순으로 오름차순을 사용했더니 AC를 받게 되었다.

 

참고 사항

  • vg배열을 사용함으로 이미 방문한 그룹은 추가로 방문하지 않게 로직을 설계했다.
  • getDist함수에서 맵을 순회하기 전에 vg배열의 0번 인덱스를 방문처리 함으로 0은 탐색하지 않게했다.
  • ct가 ans보다 크거나 작으면 탐색을 할 필요가 없으므로 해당 가지치기로 시간을 많이 아낄 수 있다.

 

정답 코드

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;

int n, g, ans = 1e9;
int lst[100][100];
bool v[100][100];
bool vg[10000];
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
struct Pos {
	int x, y, t;
	bool operator<(const Pos& other) const {
		return t > other.t;
	}
};

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

void conn(int sx, int sy, int g) {
	priority_queue<Pos> q;
	q.push({ sx, sy, 0 });
	v[sx][sy] = 1;

	while (!q.empty()) {
		Pos pos = q.top(); q.pop();
		int cx = pos.x, cy = pos.y, ct = pos.t;
		if (ct >= ans) continue;

		for (int i = 0; i < 4; ++i) {
			int nx = cx + dx[i], ny = cy + dy[i];
			if (0 <= nx && nx < n && 0 <= ny && ny < n && !v[nx][ny]) {
				v[nx][ny] = 1;
				if (lst[nx][ny] == g) q.push({ nx, ny, ct });
				else if (!lst[nx][ny]) q.push({ nx, ny, ct + 1 });
				else ans = min(ans, ct);
			}
		}
	}
}

void getDist() {
	vg[0] = 1;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (vg[lst[i][j]]) continue;
			vg[lst[i][j]] = 1;
			memset(v, 0, sizeof(v));
			conn(i, j, lst[i][j]);
		}
	}
}

void floodfill(int sx, int sy, int g) {
	queue<Pos> q;
	q.push({ sx, sy });
	v[sx][sy] = 1;
	lst[sx][sy] = g;

	while (!q.empty()) {
		Pos pos = q.front(); q.pop();
		int cx = pos.x, cy = pos.y;

		for (int i = 0; i < 4; ++i) {
			int nx = cx + dx[i], ny = cy + dy[i];
			if (0 <= nx && nx < n && 0 <= ny && ny < n && !v[nx][ny] && lst[nx][ny]) {
				v[nx][ny] = 1;
				lst[nx][ny] = g;
				q.push({ nx, ny });
			}
		}
	}
}

void grouping() {
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (v[i][j] || !lst[i][j]) continue;
			floodfill(i, j, ++g);
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	input();
	grouping();
	getDist();

	cout << ans;
}
728x90
반응형