백준 16973번 직사각형 탈출 (C++)

문제 링크 : https://www.acmicpc.net/problem/16973

16973번: 직사각형 탈출

처음 문제를 접근했을때, Brute Force마냥 시간초과를 피하기 위해 갈 수 없는 영역들은 모조리 방문표시를 했다.

BFS와 Brute Force의 조합으로 어찌저찌해서 정답은 맞췄지만, 시간효율성이 좋지 못하다는 것을 깨닫고 다른 방법을 고안하게 되었다.

 

남들은 100ms가 나올때 나는 1800m가 초과되었는데, 분명 더 좋은 답변이 있으리라 생각했다.

 

그러다 터득한 방안은 다음과 같은데, 우선 가장 첫 번째로 주어지는 사각형의 시작 넓이에는 1이 없다는 사실이다.

그렇다면 이를 토대로 현 위치에서 4방위로 움직일때, 아래 그림과 같이 숫자로 표시된 모서리 구역에 1이 없다면 해당 지역은 큐에 삽입하고 계속 진행을 해도 된다는 것을 뜻한다.

모서리만 잘 판단하면 되는 것이 키포인트이다.

 

문제 풀이는 다음과 같다.

 

1. 필요한 값들을 변수에 저장하고 bfs를 진행한다.

    cin >> n >> m;
    v.resize(n+1,vector<int>(m+1,0));
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cin >> v[i][j];
        }
    }
    cin >> h >> w >> s1 >> s2 >> f1 >> f2;
    cout << bfs() << "\n";

2. 큐에 필요한 값을 넣고 bfs를 진행한다.

truct box{
    int y1, x1, y2, x2, cnt;
};

int bfs(){
    queue<box> q;
    q.push({s1,s2,s1+h-1,s2+w-1,0});
    ch[s1][s2] = true;
    while(!q.empty()){
        y = q.front().y1;
        x = q.front().x1;
        yy = q.front().y2;
        xx = q.front().x2;
        g = q.front().cnt;
        q.pop();
        if(y==f1&&x==f2){
            return g;
        }
        for(int i=0; i<4; i++){
            ny = y+my[i];
            nx = x+mx[i];
            nyy = yy+my[i];
            nxx = xx+mx[i];
            if(ny<1||ny>n||nx<1||nx>m) continue; // 1 
            if(nyy<1||nyy>n||nxx<1||nxx>m) continue; // 2 
            if(ch[ny][nx]||v[ny][nx]==1) continue; // 3
            if(canwego(ny,nx,nyy,nxx,i)) continue; // 4
            ch[ny][nx]= true;
            q.push({ny,nx,nyy,nxx,g+1});
        }
    }
    return -1;
}

1~3은 사각형의 넓이가 범위를 초과하는지, 현재 시작 꼭지점이 이미 방문한 지역인지를 판단한다.

중요한것은 4번의 canwego 함수이다.

 

3. 맨 위의 그림을 토대로, 움직인 사각형의 모서리 위치가

(1) 사각형의 범위를 초과하지 않고

(2) 해당 모서리 구역에 1이 없다면 false를 반환하고 큐에 삽입하면 된다.

 

bool canwego(int y1, int x1, int y2, int x2, int d){
    if(d==0){ // 1,0
        if(x1+w-1<0||x1+w-1>m) return true;
        for(int a=x1; a<x1+w; a++){
            if(v[y2][a]==1) return true;
        }
    }
    else if(d==1){ // -1,0
        if(x1+w-1<0||x1+w-1>m) return true;
        for(int a=x1; a<x1+w; a++){
            if(v[y1][a]==1) return true;
        }
    }
    else if(d==2){ // 0,1
        if(y1+h-1<0||y1+h-1>n) return true;
        for(int a=y1; a<y1+h; a++){
            if(v[a][x2]==1) return true;
        }
    }
    else if(d==3){ // 0,-1
        if(y1+h-1<0||y1+h-1>n) return true;
        for(int a=y1; a<y1+h; a++){
            if(v[a][x1]==1) return true;
        }
    }
    return false;
}

 

4. 큐가 비었다면 정답이 없다는 뜻이므로 1을 반환하면 된다.

만약 현 시작 꼭지점의 위치가 f1, f2와 같다면 움직임 횟수를 반환해주면 된다.

 

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

int ans = 0, g,n,m,y,yy,xx,x,ny,nyy,nxx,nx,my[]={1,-1,0,0},mx[]={0,0,1,-1}, h,w,s1,s2,f1,f2; // s1 -> f1, s2 -> f2;
bool ch[1001][1001];
vector<vector<int>> v;

struct box{
    int y1, x1, y2, x2, cnt;
};

bool canwego(int y1, int x1, int y2, int x2, int d){
    if(d==0){ // 1,0
        if(x1+w-1<0||x1+w-1>m) return true;
        for(int a=x1; a<x1+w; a++){
            if(v[y2][a]==1) return true;
        }
    }
    else if(d==1){ // -1,0
        if(x1+w-1<0||x1+w-1>m) return true;
        for(int a=x1; a<x1+w; a++){
            if(v[y1][a]==1) return true;
        }
    }
    else if(d==2){ // 0,1
        if(y1+h-1<0||y1+h-1>n) return true;
        for(int a=y1; a<y1+h; a++){
            if(v[a][x2]==1) return true;
        }
    }
    else if(d==3){ // 0,-1
        if(y1+h-1<0||y1+h-1>n) return true;
        for(int a=y1; a<y1+h; a++){
            if(v[a][x1]==1) return true;
        }
    }
    return false;
}

int bfs(){
    queue<box> q;
    q.push({s1,s2,s1+h-1,s2+w-1,0});
    ch[s1][s2] = true;
    while(!q.empty()){
        y = q.front().y1;
        x = q.front().x1;
        yy = q.front().y2;
        xx = q.front().x2;
        g = q.front().cnt;
        q.pop();
        if(y==f1&&x==f2){
            return g;
        }
        for(int i=0; i<4; i++){
            ny = y+my[i];
            nx = x+mx[i];
            nyy = yy+my[i];
            nxx = xx+mx[i];
            if(ny<1||ny>n||nx<1||nx>m) continue;
            if(nyy<1||nyy>n||nxx<1||nxx>m) continue;
            if(ch[ny][nx]||v[ny][nx]==1) continue;
            if(canwego(ny,nx,nyy,nxx,i)) continue;
            ch[ny][nx]= true;
            q.push({ny,nx,nyy,nxx,g+1});
        }
    }
    return -1;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m;
    v.resize(n+1,vector<int>(m+1,0));
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cin >> v[i][j];
        }
    }
    cin >> h >> w >> s1 >> s2 >> f1 >> f2;
    cout << bfs() << "\n";
    return 0;
}

1/15 이상으로 시간이 단축된 매직!