안녕하세요, 오늘은 백준 5022번 연결 문제를 풀어봤습니다,
문제 파악
우선, 이 문제를 풀기 위해서는 어떤 문제인지부터 파악해보도록 하겠습니다.
이 문제의 경우 전기회로에서 두 전선을 이을 때 최대한 짧게 이어야 하며
전기회로의 두 전선은 절대 겹쳐서는 안되는데요.
즉 이 문제는 다익스트라 알고리즘으로 한 전선의 최단거리를 먼저 탐색한 후
최단거리로 이동한 거리를 prev를 통해 최단거리까지의 거리를 모두 저장한 후
arr를 직접 변경해줌으로써 이 다음 전선을 연결할 때 연결이 가능한지 여부를
체크 가능합니다.
하지만 이때 두 전선중에 어떤 것을 먼저 연결하는지에 따라 연결이 안되는 경우도 존재하며
두가지 방법중에 더 빠르게 연결할 수 있는 방법을 선택해야 합니다 즉,
- a1 -> a2 먼저 연결 후 b1 -> b2 연결
- b1 -> b2 먼저 연결 후 a1 -> a2 연결
- 두개다 안 되는 경우에는 IMPOSSIBLE
여기서 첫 번째꺼가 연결 되는데 두 번째가 연결 안되는 경우는 왜 발생하는 걸까요?
그거부터 알려드리자면, 앞서 말씀드렸다 싶이 최단거리, 다익스트라 알고리즘으로
탐색을 하기 때문에 이후에 연결하는걸 신경쓰지 않고 "일단은 가장 빠르게 연결"
하기에 이후에 연결할 때 연결을 못하는 루트로 연결하는 경우가 생길 수 있습니다.
위 사진처럼 (0, 0) -> (6, 6) 으로 이동할 때 (0, 3) -> (3, 3)으로 연결해야하는 전선의 사이로
이동하는걸 보실 수 있습니다. 때문에 한번씩 초기화해서 각각 순서를 바꿔서 연결을 해주어야 합니다.
코드 작성
전선 좌표 저장 및 갱신
vector<pair<int, int>> p;
for (int i = 0; i < 4; i++) {
int x, y;
cin >> x >> y;
p.push_back({x, y});
}우선 전선의 좌표들을 미리 저장을 해주어야합니다, 이후엔 저장된 좌표들을 arr에 갱신해주어야 합니다.
for (auto &point : p) {
arr[point.second][point.first] = 3;
}전선 연결
이후에는 전선들끼리 다익스트라 알고리즘으로 최단거리로 연결해주어야 합니다.
이때 이미 전선이 연결되어 있는 경우(전선줄), 전선의 좌표인 경우 continue 해주어야 하며
만약 다음으로 이동할 좌표(nextX, nextY)일 경우에는 전선의 좌표일 경우에도 갱신해주어야 합니다.
void dij(int x, int y, int endx, int endy) {
priority_queue<pair<int, pair<int, int>>,
vector<pair<int, pair<int, int>>>,
greater<pair<int, pair<int, int>>>> pq;
pq.push({0, {x, y}});
visited[x][y] = 0;
while (!pq.empty()) {
int distance = pq.top().first;
pair<int, int> current = pq.top().second;
pq.pop();
int cx = current.first;
int cy = current.second;
for (int i = 0; i < 4; i++) {
int nx = cx + dx[i];
int ny = cy + dy[i];
if (nx < 0 || nx >= n + 1 || ny < 0 || ny >= m + 1) continue;
if (arr[nx][ny] == 1) continue;
if(arr[nx][ny] == 0 || (arr[nx][ny] == 3 && nx == endx && ny == endy)) {
if (visited[nx][ny] > distance + 1) {
visited[nx][ny] = distance + 1;
pre[nx][ny] = {cx, cy};
pq.push({visited[nx][ny], {nx, ny}});
}
}
}
}
}최단거리로 연결된 전선줄을 맵에 갱신해주기
이제 최단거리로 전선이 연결되었기 때문에 이전에 다익스트라로 탐색하면서 갱신한
prev를 활용해 실제로 맵에 갱신을 해주어야 합니다. 이때 만약 실제로 맵에 갱신 못할 경우
전선끼리 연결하지 못하는 경우이기에 이 경우를 체크해주어야 합니다.
void prevF(int sx, int sy, int ex, int ey, int num) {
int cx = ex;
int cy = ey;
while (true) {
path.push_back({cx, cy});
arr[cx][cy] = num;
if (cx == sx && cy == sy) {
break;
}
pair<int, int> prev = pre[cx][cy];
if (prev.first < 0 || prev.first >= n + 1 || prev.second < 0 || prev.second >= m + 1) {
flag = false;
return;
}
cx = prev.first;
cy = prev.second;
}
reverse(path.begin(), path.end());
cout << endl;
}이때 prev를 (-1, -1)으로 초기화 함으로써 만약 prev가 갱신되지 않았을 경우 연결이 안되는 상황이니
flag를 false 해줄 수 있습니다.
이번에도 그림을 통해 더 자세히 설명드리도록 하겠습니다.
정상적으로 연결이 되는 회로는 이런식으로 이동하는 동안의 모든 경로를 확인할 수 있습니다, 하지만
위 그림처럼 a 전선을 먼저 연결한 후 b 전선을 연결할 때 b가 연결이 안되는 경우에
마지막으로 방문한 좌표의 pre 값은 (-1, -1)이 되므로 시작점이 (0, 2)역시 (-1, -1)라는 값을 가지게 됨
그래서 실제로 코드를 실행 해보면
경로 2의 경우 바로 끝나는걸 확인할 수 있습니다.
반복 해주기
맵을 갱신했다면 처음에 문제 파악 부분에서 말한대로 순서를 바꿔서 한번씩 연결한 후
a 전선의 연결 거리 + b 전선의 연결 거리 중 더 작은 값을 출력하면 정답입니다.
아래는 전체 코드입니다.
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> arr;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
vector<vector<int>> visited;
vector<vector<pair<int, int>>> pre;
vector<pair<int, int>> path;
vector<pair<int, int>> p;
bool flag = true;
const int INF = 1e9;
int n, m;
void resetArr() {
fill(arr.begin(), arr.end(), vector<int>(m + 1, 0));
for (auto &point : p) {
arr[point.second][point.first] = 3;
}
}
void prevF(int sx, int sy, int ex, int ey, int num) {
int cx = ex;
int cy = ey;
while (true) {
path.push_back({cx, cy});
arr[cx][cy] = num;
if (cx == sx && cy == sy) {
break;
}
pair<int, int> prev = pre[cx][cy];
if (prev.first < 0 || prev.first >= n + 1 || prev.second < 0 || prev.second >= m + 1) {
flag = false;
return;
}
cx = prev.first;
cy = prev.second;
}
reverse(path.begin(), path.end());
}
void dij(int x, int y, int endx, int endy) {
priority_queue<pair<int, pair<int, int>>,
vector<pair<int, pair<int, int>>>,
greater<pair<int, pair<int, int>>>> pq;
pq.push({0, {x, y}});
visited[x][y] = 0;
while (!pq.empty()) {
int distance = pq.top().first;
pair<int, int> current = pq.top().second;
pq.pop();
int cx = current.first;
int cy = current.second;
for (int i = 0; i < 4; i++) {
int nx = cx + dx[i];
int ny = cy + dy[i];
if (nx < 0 || nx >= n + 1 || ny < 0 || ny >= m + 1) continue;
if (arr[nx][ny] == 1) continue;
if(arr[nx][ny] == 0 || (arr[nx][ny] == 3 && nx == endx && ny == endy)) {
if (visited[nx][ny] > distance + 1) {
visited[nx][ny] = distance + 1;
pre[nx][ny] = {cx, cy};
pq.push({visited[nx][ny], {nx, ny}});
}
}
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> m >> n;
arr.resize(n + 1, vector<int>(m + 1, 0));
visited.resize(n + 1, vector<int>(m + 1, INF));
pre.resize(n + 1, vector<pair<int, int>>(m + 1, {-1, -1}));
for (int i = 0; i < 4; i++) {
int x, y;
cin >> x >> y;
p.push_back({x, y});
}
// 초기 arr 설정
resetArr();
// 첫 번째 경로 계산
dij(p[0].second, p[0].first, p[1].second, p[1].first);
prevF(p[0].second, p[0].first, p[1].second, p[1].first, 1);
int a1 = visited[p[1].second][p[1].first];
// path 벡터 초기화
path.clear();
// visited와 pre 배열 재설정
fill(visited.begin(), visited.end(), vector<int>(m + 1, INF));
fill(pre.begin(), pre.end(), vector<pair<int, int>>(m + 1, {-1, -1}));
// pre를 -1으로 초기화하면 만약 end -> start로 갈때 -1 -1이 나옴
// 두 번째 경로 계산
dij(p[2].second, p[2].first, p[3].second, p[3].first);
prevF(p[2].second, p[2].first, p[3].second, p[3].first, 2);
int a2 = visited[p[3].second][p[3].first];
// 두번째 돌리기
bool aflag = true;
if(!flag) {
aflag = false;
}
flag = true;
// 초기 arr 설정
resetArr();
// path 벡터 초기화
path.clear();
// visited와 pre 배열 재설정
fill(visited.begin(), visited.end(), vector<int>(m + 1, INF));
fill(pre.begin(), pre.end(), vector<pair<int, int>>(m + 1, {-1, -1}));
// 두 번째 경로 계산
dij(p[2].second, p[2].first, p[3].second, p[3].first);
prevF(p[2].second, p[2].first, p[3].second, p[3].first, 2);
int b1 = visited[p[3].second][p[3].first];
// path 벡터 초기화
path.clear();
// visited와 pre 배열 재설정
fill(visited.begin(), visited.end(), vector<int>(m + 1, INF));
fill(pre.begin(), pre.end(), vector<pair<int, int>>(m + 1, {-1, -1}));
// 첫 번째 경로 계산
dij(p[0].second, p[0].first, p[1].second, p[1].first);
prevF(p[0].second, p[0].first, p[1].second, p[1].first, 1);
int b2 = visited[p[1].second][p[1].first];
// 불가능한 경우 체크
if (!flag && !aflag) {
cout << "IMPOSSIBLE" << '\n';
} else {
cout << min(a1 + a2, b1 + b2) << '\n';
}
return 0;
}
