[도전 22일차] 로봇 - KOI 고등부 풀이

※복습 : 

문제 : BOJ 2633 로봇

문제 링크

 

3연속 BFS 문제!

 

사용 알고리즘 : BFS

 

풀이: 

이번엔 시작점에서 목표점까지 가는데 꺾어야 하는 횟수를 묻는다. 좌표값의 범위가 작으므로 지난 문제  미로  만들기처럼 관심있는 값(꺾은 횟수)를 들고 다니면서 BFS를 수행해주면 된다.

장애물의 경계에 놓인 경우 강제적으로 꺾어주면 된다. (방향이 2개로 정해진다.)

 

장애물의 경계에 놓인 것을 판정하는 것이 핵심인데 필자는 각각의 점에 대해 (최대 10000개)  가능한 방향을 체크해주는 것으로 해결했다.

 

장애물의 가능한 모양은 다음과 같다.

 출처 : KOI

이제 p1을 기준으로 장애물을 구분하고, 각각의 경계의 점에 대하여 가능한 방향을 정해주면 된다.

이때 각 경계선에 있는 점마다 탐색이 불가능한 방향이 있는 것을 알 수 있다.

먼저 모든 방향이 가능하다고 초기화한다.

그 다음 각각의 장애물에 대해 일반성을 잃지 않고 첫번째(왼쪽 위) 모양이라 하자. 

또한 방향들을 0-오른쪽, 1 -위쪽,  2-왼쪽, 3-아래쪽이라 하자.

그러면 선분 p1-p2 에 있는 점은 0번이 안되고, p2-p3 에 있는 점은 1번 방향이 안되고 p3 - (p4와 p3과 연관된 점) 위에 있는 점은 2번 방향이 안되고, 이런 식으로 둘레를 돌아가면서 안되는 방향을 정해줄 수 있다.

 

이때 우리가 첫번째 모양이라고 가정했으므로 각각의 모양에 대해 방향을 rotate 하여 쉽게 변환할 수 있다.

ex) 왼쪽 아래 모양은 p1-p2은 2번이 안되고, p2-p3 은 3번이 안되고 p3 - (p4,p3) 은 0번이 안된다. 관찰해보면 예시에 살펴보았던 방향에서 정확히 2가 더해진 것을 알 수 있다. 이처럼 rotate 해주면 된다.

 

bfs를 돌릴 때 다익스트라처럼 꺾은 횟수가 더 적은 경우만 갱신하면서 큐에 추가해주면 된다.

 

어떤 점을 예전에 방문했었다고 할 때, 그 점을 어느 방향에서 방문했는지도 중요하다. 만약 예전에 방문했었을 때 2의 꺾인 횟수를 가졌다고 하자. 그런데 다른 방향에서  2의 꺾인 횟수를 가진 채 탐색이 들어왔다고 하자. 큐에 또 집어넣을 것인가? 큐에 만약 집어넣지 않는다면 방향을 유지했을 때 꺾인 횟수를 2로 한 채 쭉 탐색하는 경우를 생각하지 못한다. 그러므로 2가지 해법이 가능하다.

1. 꺾인 횟수가 예전에 방문했을 때보다 크거나 같을 때 큐에 넣기.

2. 점들에 대해 각각의 방향에서 왔을 때 꺾인 횟수를 저장하여 예전에 방문했을 때보다 클 때 큐에 넣기.

 

2번이 더 직관적이므로 본 글의 코드는 2번 방법을 사용했다. 더불어 중복 계산이 적으므로 빠르다.

코드

//pentagon@sasa.hs.kr
//https://howtoliveworldnice.tistory.com/88
#include<bits/stdc++.h>
using namespace std;
#define M 101
const int INF = 1e9;
struct Point{
    int x,y;
};
typedef struct Search{
    Point p; int cnt,id;
    Search(){}
    Search(int x,int y,int a,int b){
        p.x=x; p.y=y; cnt=a; id=b;
    }
}S;
Point s,e;
int v[M][M][4],dx[4]={1,0,-1,0},dy[4]={0,1,0,-1}; // 0:우 1:상 2:좌 3: 하 
inline bool safe(int a,int b){return a>0 && a<M && b>0 && b<M;}
bool dir[M][M][4];
inline void check(int a1,int b1,int a2,int b2,int id){
    int i;
    if(a1==a2){
        if(b1>b2) b1^=b2^=b1^=b2;
        for(i=b1+1;i<b2;i++)
            dir[a1][i][id]=false;
    }
    else if(b1==b2){
        if(a1>a2) a1^=a2^=a1^=a2;
        for(i=a1+1;i<a2;i++)
            dir[i][b1][id]=false;
    }
}
void input(){
    int m,x,y; Point p1,p2,p3,p4;
    cin>>s.x>>s.y>>e.x>>e.y>>m;
    fill(&dir[0][0][0],&dir[100][100][4],true);
    while(m--){
        cin>>p1.x>>p1.y>>p2.x>>p2.y>>p3.x>>p3.y>>p4.x>>p4.y;
        int i,id[8]={0,1,2,3,3,2,2,3},chg;
        if(p1.x==p2.x){
            if(p1.y>p2.y) chg=0;
            else chg=2;
        }
        else{
            if(p1.x>p2.x) chg=3;
            else chg=1;
        }
        for(int i=0;i<8;i++)
            id[i]=(id[i]+chg)%4;
        if(p1.x==p2.x){
            check(p1.x,p1.y,p2.x,p2.y,id[0]);
            check(p2.x,p2.y,p3.x,p3.y,id[1]);
            check(p3.x,p3.y,p3.x,p4.y,id[2]);
            check(p3.x,p4.y,p4.x,p4.y,id[3]);
            dir[p4.x][p4.y][id[4]]=dir[p4.x][p4.y][id[5]]=false;
            check(p4.x,p4.y,p4.x,p1.y,id[6]);
            check(p4.x,p1.y,p1.x,p1.y,id[7]);
        }
        else{
            check(p1.x,p1.y,p2.x,p2.y,id[0]);
            check(p2.x,p2.y,p3.x,p3.y,id[1]);
            check(p3.x,p3.y,p4.x,p3.y,id[2]);
            check(p4.x,p3.y,p4.x,p4.y,id[3]);
            dir[p4.x][p4.y][id[4]]=dir[p4.x][p4.y][id[5]]=false;
            check(p4.x,p4.y,p1.x,p4.y,id[6]);
            check(p1.x,p4.y,p1.x,p1.y,id[7]);
        }
    }
}
int bfs(){
    queue<S> q;
    fill(&v[0][0][0],&v[100][100][4],INF);
    for(int i=0;i<4;i++){
        v[s.x][s.y][i]=0;
        int a=s.x+dx[i],b=s.y+dy[i];
        if(safe(a,b))
            q.push(S(a,b,0,i)),v[a][b][i]=0;
    }
    while(!q.empty()){
        S cur=q.front(); q.pop();
        for(int i=0;i<4;i++){
            if(dir[cur.p.x][cur.p.y][i]==false) continue;
            int a=cur.p.x+dx[i],b=cur.p.y+dy[i],c=cur.cnt+(cur.id!=i);
            if(safe(a,b) && c < v[a][b][i]){
                v[a][b][i]=c;
                q.push(S(a,b,c,i));
            }
        }
    }
    int ans=INF; for(int i=0;i<4;i++) ans=min(ans,v[e.x][e.y][i]);
    return ans;
}
int main(){
    input();
    cout<<bfs();
}

 

궁금한 점이 있으시다면 질문 남겨주세요 :)