[BFS] 5022번 연결

5022번 연결

 

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

 

문제

전기 회로에서 두 점을 전선으로 이을 때, 길이는 짧을 수록 좋다.

크기가 N×M인 비어있는 회로판에서 두 점 A1과 A2, 그리고 B1와 B2를 전선을 이용해서 이으려고 한다. 전선은 항상 그리드의 수직, 수평선 위에 있어야 한다. 또, 두 직선은 접하면 안된다. 이 경우에 필요한 전선의 길이의 최솟값을 구하는 프로그램을 작성하시오. 전선은 회로판 바깥으로 나갈 수 없다.

 

입력

첫째 줄에 회로판의 크기 N과 M이 주어진다. (2 ≤ N, M ≤ 100)

다음 네 줄에는 A1, A2, B1, B2의 좌표가 주어진다. 점의 좌표는 두 정수의 쌍으로 이루어져 있고, 첫 번째 좌표는 0 이상 N 이하이며 두 번째 좌표는 0 이상 M 이하이다. 어떤 점도 같은 위치에 있지 않다.

 

출력

A1과 A2, 그리고 B1과 B2를 연결하는데 필요한 전선의 길이의 최솟값을 출력한다. 만약, 불가능한 경우에는 "IMPOSSIBLE"을 출력한다.

 

예제 입력

6 6
2 1
5 4
4 0
4 5

 

예제 출력

15

 

 

해결방법

최단거리를 구하는 BFS 탐색 문제이다

 

 

⭐️ 솔루션 ⭐️

다른 문제와는 다르게 두 개의 최단거리를 구해야하는 문제이다

이는 BFS 탐색시 사용하는 visited 배열과 탐색이 끝난 후, 해당 최단거리를 더이상 방문하지 못하도록 하는 done 배열을 사용하면 간단히 해결될거라 생각했다

탐색을 수행할 때, 큐에 구조체를 활용해 지나왔던 노드의 좌표를 저장하는 벡터를 넣었다

그리고 탐색이 끝나면 벡터를 돌며 done 배열을 체크해줬다

 

 

[ 이슈 ]

결과가 올바르게 나오길래 사이트에 제출을 했는데 틀렸습니다 가 나왔다

다른 TC 를 찾을 수 없어 구글링을 하다가 한 솔루션을 보게되었다

두개의 최단경로가 존재하는데 각 순서를 다르게 하면 최단경로가 달라지게 된다

즉, 1번 최단경로를 설정하고 2번 최단경로를 설정하는 것과 2번 최단경로를 설정하고 1번 최단경로를 설정하는 것의 결과는 다르다는 뜻이었다

따라서 2번의 최단경로 탐색을 한번은 순서대로 다음은 역순으로 총 4번 수행하여 결과를 비교하여 출력하였다

 

 

 

소스코드

문제 해결 시간 : 1h

메모리 : 2144 KB

시간 : 136 ms

#include <iostream>
#include <cstring>
#include <math.h>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 101
#define INF 987654321
using namespace std;

typedef pair<int, int> pos;

struct node {
    int x,y;
    vector<pos> path;
    
    node() { }
    node(int _x,int _y,vector<pos> v) : x(_x),y(_y),path(v) { }
};

int n,m,ans,cnt;
int rx1,ry1,rx2,ry2;
int bx1,by1,bx2,by2;
bool r_end,b_end;

bool visited[MAX][MAX];
bool done[MAX][MAX];

int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

node a,b;

// turn = 1 : 첫번째 전선의 최단거리를 연결하는 경우
// turn = 2 : 두번째 전선의 최단거리를 연결하는 경우
void bfs(int x1,int y1,int x2,int y2,int turn){
    queue<node> q;
    vector<pos> v;
    v.push_back(pos(x1,y1));
    q.push(node(x1,y1,v));
    visited[x1][y1] = true;
    done[x1][y1] = true;
    
    while(!q.empty()){
        int x = q.front().x;
        int y = q.front().y;
        vector<pos> path = q.front().path;
        q.pop();
        
        // 두 전선을 최단거리로 연결했다면
        if(x == x2 && y == y2){
            // A 전선의 최단거리는 다른 전선의 연결에서 사용할 수 없음
            for(int i=0; i<path.size(); i++){
                int xx = path[i].first;
                int yy = path[i].second;
                
                done[xx][yy] = true;
            }
            
            // 전선연결이 무사히 완료됨을 체크
            if(turn == 1) r_end = true;
            else b_end = true;
            
            break;
        }
        
        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            vector<pos> nv;
            
            for(int j=0; j<path.size(); j++){
                nv.push_back(path[j]);
            }
            
            // 맵을 벗어나거나 다른 전선의 시작점과 끝점에 도달한 경우 제외
            if(nx<0 || ny<0 || nx>n || ny>m) continue;
            if(turn == 1 && ((nx==bx1 && ny==by1) || (nx==bx2 && ny==by2))) continue;
            if(turn == 2 && ((nx==rx1 && ny==ry1) || (nx==rx2 && ny==ry2))) continue;
            
            if(!visited[nx][ny] && !done[nx][ny]){
                nv.push_back(pos(nx,ny));
                q.push(node(nx,ny,nv));
                visited[nx][ny] = true;
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> m >> n;
    
    cin >> ry1 >> rx1;
    cin >> ry2 >> rx2;
    cin >> by1 >> bx1;
    cin >> by2 >> bx2;
    
    ans = INF;
    
    /*
     첫번째 전선의 최단거리를 연결하고,
     그다음에 두번째 전선의 최단거리를 연결하는 경우
    */
    
    // 첫번째 전선 연결
    memset(visited, false, sizeof(visited));
    memset(done, false, sizeof(done));
    r_end = false;
    bfs(rx1,ry1,rx2,ry2,1);
    
    // 두번째 전선 연결
    memset(visited, false, sizeof(visited));
    b_end = false;
    bfs(bx1,by1,bx2,by2,2);
    
    // 전선의 길이를 구함
    cnt = 0;
    for(int i=0; i<=n; i++){
        for(int j=0; j<=m; j++){
            if(done[i][j])
                cnt++;
        }
    }
    
    // 시작점을 제외한 길이가 전체 전선의 길이
    if(r_end && b_end)
        ans = min(ans,cnt-2);
    
    /*
     두번째 전선의 최단거리를 연결하고,
     그다음에 첫번째 전선의 최단거리를 연결하는 경우
     */
    
    // 두번째 전선 연결
    memset(visited, false, sizeof(visited));
    memset(done, false, sizeof(done));
    b_end = false;
    bfs(bx1,by1,bx2,by2,2);
    
    // 첫번째 전선 연결
    memset(visited, false, sizeof(visited));
    r_end = false;
    bfs(rx1,ry1,rx2,ry2,1);
    
    // 전선의 길이를 구함
    cnt = 0;
    for(int i=0; i<=n; i++){
        for(int j=0; j<=m; j++){
            if(done[i][j])
                cnt++;
        }
    }
    
    // 시작점을 제외한 길이가 전체 전선의 길이
    if(r_end && b_end)
        ans = min(ans,cnt-2);
    
    // 최종 결과 출력
    if(ans == INF)
        cout << "IMPOSSIBLE" << "\n";
    else
        cout << ans << "\n";
    
    return 0;
}