반응형
리뷰
https://www.acmicpc.net/problem/2146
섬을 그룹화 한 뒤 섬끼리 이을 수 있는 가장 짧은 경로를 구하는 문제
그룹화 후 거리를 구하는 함수에서 일반 큐를 사용했더니 AC를 받지 못했다.
디버깅 후 우선순위 큐를 사용하여 AC를 받은 문제, 디버깅의 중요성을 새삼 깨달았다.
함수를 나누어 구현을 하다 보니 생각보다 로직이 길어진 문제, 100줄까지 갈지는 몰랐다.
전역 변수
- n : 맵의 한 변의 길이를 저장할 정수형 변수
- g : 각 섬을 그룹화 하기 위해 사용할 정수형 변수
- ans : 각 섬을 잇기 위한 최소한의 거리를 저장할 정수형 변수
- lst : 맵 정보를 저장하기 위한 정수형 2차 배열
- v : 그룹화 및 거리를 구할 때 사용할 방문 배열
- vg : 그룹 번호로 방문 표시를 하기 위한 배열
- dx, dy : 4방향 탐색을 위한 방향 배열
- Pos : 거리를 구할 때 최소 값을 그리디하게 구하기 위한 구조체, 거리를 기준으로 오름차순 정렬한다.
함수
1. input
void input()
입력을 받기 위한 함수
- 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);
}
}
}
각 섬들을 그룹화 해주기 위한 함수
- n * n크기의 맵 정보를 순회하며 방문처리 되지 않았고 0이 아니라면 그룹화를 진행한다.
- floodfill함수에 시작 좌표 i, j와 그룹 번호를 전위 증가시켜 전달해 준다.
- 모든 섬에 대해 그룹화를 진행할 때 까지 해당 탐색을 진행해 준다.
3. floodfill
void floodfill(int sx, int sy, int g)
플러드 필을 통해 섬 내에서 갈 수 있는 육지를 모두 그룹화 해주는 함수
- 매개변수로 시작 좌표 sx, sy와 마킹할 그룹의 번호 g를 입력 받는다.
- Pos타입의 큐 q에 sx, sy좌표를 push해준다.
- sx, sy좌표에 방문처리를 해주고, 맵 상에서 sx, sy좌표의 값을 g로 변경해 준다.
- 큐가 빌 때 까지 while루프를 실행하고, 매 루프 시마다 큐에서 요소를 하나씩 빼준다.
- 4방향 탐색을 진행하며 맵의 범위 안에 있으며 방문처리를 하지 않았고 0이 아니라면 이동을 진행해 준다.
- 이동한 좌표에 방문 처리를 해주고, 맵에서 해당 좌표의 값을 g로 변경해 준다.
- 큐에 이동한 좌표를 push해주고 while 루프가 종료될 때 까지 그룹화를 진행해 준다.
4. getDist
void getDist()
각 섬끼리의 거리를 구하기 위한 함수
- vg의 0번 인덱스를 1로 초기화 해준다, 이는 0에서는 탐색을 하지 않기 위함이다.
- n * n크기의 맵을 순회하며 맵에서의 그룹이 이미 방문한 그룹이라면 continue처리해 준다.
- 아직 방문하지 않은 그룹이라면 방문처리 후 탐색을 진행해 주어야 한다.
- 탐색에 앞서 memset메서드를 통해 사용했던 방문 배열 v를 0으로 초기화 해준다.
- conn함수에 시작 좌표인 i, j와 맵 상에서의 i, j좌표의 그룹 번호를 매개변수로 전달한다.
5. conn
void conn(int sx, int sy, int g)
각 섬을 연결하면서 연결을 위한 다리의 최소 길이를 구하기 위한 함수
- Pos타입의 우선순위 큐 q를 초기화 해준 뒤, 시작 좌표 sx, sy와 시작 시간 0을 push해준다.
- 시작 지점인 sx, sy에 방문처리 후 큐가 빌 때 까지 순환하는 루프를 생성해준다.
- 매 루프마다 q에서 요소를 한개씩 빼주어 Pos타입의 변수 pos로 초기화 해준다.
- pos의 x, y, t를 각각 정수형 변수 cx, cy, ct에 초기화 해준다.
- 기저 조건으로 ct가 ans보다 크거나 같을 경우 더 이상 탐색할 필요가 없으므로 continue 처리해준다.
- 4방향 탐색을 하며 맵의 범위를 벗어나지 않았고, 방문처리 되지 않은 부분이라면 이동을 진행한다.
- 이동한 좌표에 방문처리 후 만약 같은 그룹이라면 시간을 증가시키지 않고 큐에 push해준다.
- 0을 만났다면 시간을 증가시킨 후에 큐에 push해준다.
- 0도 아니고 같은 그룹도 아니라면 ans와 ct중 더 작은 값을 ans에 저장해 준다.
문제풀이
- input함수를 통해 n과 맵 정보를 입력 받아준다.
- grouping함수를 통해 각 섬을 1부터 번호를 받아 그룹화를 진행해 준다.
- getDist함수를 통해 섬 간의 가장 짧은 거리를 구해 ans에 저장해 준다.
- 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
반응형
'알고리즘 공부 > C++' 카테고리의 다른 글
[G3] 백준 2638번 치즈 C++ 너비 우선 탐색, 해시맵, 구현, 시뮬레이션 (0) | 2024.12.19 |
---|---|
[G3] 백준 1600번 말이 되고픈 원숭이 C++ 너비 우선 탐색, 우선순위 큐, 시뮬레이션 (0) | 2024.12.17 |
[G4] 백준 1963번 소수 경로 C++ 너비 우선 탐색, 에라토스테네스의 체 (2) | 2024.12.14 |
[G4] 백준 11559번 Puyo Puyo C++ 너비 우선 탐색, 시뮬레이션, 구현 (3) | 2024.12.13 |
[G4] 백준 5427번 불 C++ 너비 우선 탐색, BFS, 우선순위 큐 (2) | 2024.12.12 |