BOJ : BFS – 로봇

Problem code : 1726


The source of this problem is http://www.acmicpc.net/

Problem Link


My Answer

  • Lang : C++
  • Time : 0
  • Memory 1724
  • Code :
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

class ele{
public:
    int x, y, dir, cmd;
    ele(){}; ele(int _x, int _y, int _dir, int _cmd) :x(_x), y(_y), dir(_dir), cmd(_cmd){};
};

int m[101][101];
int vis[101][101][5];//방향추가
int di[] = { 0, 0, 0, 1, -1 };
int dj[] = { 0, 1, -1, 0, 0 };

int getnum(int n){//반대방향 리턴
    if (n == 1)return 2;
    if (n == 2)return 1;
    if (n == 3)return 4;
    if (n == 4)return 3;
}

int main(){
    int R, C; cin >> R >> C;
    for (int i = 1; i <= R; ++i)for (int j = 1; j <= C; ++j)scanf("%d", &m[i][j]);
    int si, sj, sdir, ei, ej, edir;
    cin >> si >> sj >> sdir >> ei >> ej >> edir;
    queue<ele> q;
    memset(vis, -1, sizeof(vis));
    //시작점 넣기
    q.push(ele(si, sj, sdir, 0));
    vis[si][sj][sdir] = 1;

    while (!q.empty()){
        ele h = q.front(); q.pop();
        int hi = h.x; int hj = h.y; int hdir = h.dir;int hc = h.cmd;
        int ni, nj;
        if (hi == ei&&hj == ej&&hdir == edir){
            cout << hc << endl;
            break;
        }

        //각 위치에서 할 수 있는 명령만 한다.이래야 레벨순환구조 (5가지명령)

        //방향대로 1~3칸가기
        for (int i = 1; i <= 3; ++i){
            ni = hi+di[hdir] * i;
            nj = hj+dj[hdir] * i;
            if (ni < 1 || ni > R || nj < 1 || nj > C || m[ni][nj] == 1)break;
            if (vis[ni][nj][hdir]==1)continue;
            vis[ni][nj][hdir] = 1;
            q.push(ele(ni, nj, hdir, hc+1));
        }
        //좌로 회전 , 우로 회전
        for (int i = 1; i <= 4; ++i){
            if (i == hdir || i == getnum(hdir))continue;
            if (vis[hi][hj][i]==1)continue;
            vis[hi][hj][i] = 1;//ni가 아니라 hj임을 유의.
            q.push(ele(hi, hj, i, hc + 1));
        }
    }
    return 0;
}

Check point

  • 처음엔 아래 코드처럼 풀었다. 각 위치에서 조작가능한 것을 다 해버리는 것이다. 70점이 나왔다. 어디서 문제인지는 못찾겠으나 이런식으로 풀면 BFS 레벨 순환구조로 푸는 것이 아니다. 분명 어디서 꼬이는 것이 나온다. 위의 답처럼 푸는 것이 레벨 순환구조이다. 즉 각 레벨에서 할 수 있는 처리를 큐에서 하나씩 다 해주는 것이다. 위의 경우 각 지점 및 그 방향에서, 5가지 명령을 할 수 있다. 그 방향대로 1,2,3칸 가기와 우회전,좌회전이다. 주의할것은 좌회전 시에는 ni가 아니라 hi hj그대로 이용한 다는 것이다. 그리고 이 문제의 경우 모든 경우라해봣자 100x100x4방향x5명령이니까 20만이라 0ms가 나와야 정상이다. 처음에 메모리,시간초과가 떴는데 내가 hi대신 ni를 썼고, 또 vis체크를 하지 않았었다.. 밑에는 처음 푼 잘못 된 코드

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#define INF 87654321
using namespace std;
class ele{
public:
    int x, y, dir, cmd;
    ele(){};
    ele(int _x, int _y, int _dir, int _cmd) :x(_x), y(_y), dir(_dir), cmd(_cmd){};
};

int m[101][101];
int vis[101][101][5];//방향추가
typedef pair<int, int> mv;
int di[] = {0, 0, 0, 1, -1 };
int dj[] = {0, 1, -1, 0, 0 };

int getnum(int n){
    if (n == 1)return 2;
    if (n == 2)return 1;
    if (n == 3)return 4;
    if (n == 4)return 3;
}

int main(){
    int R, C; cin >> R >> C;
    for (int i = 1; i <= R; ++i)for (int j = 1; j <= C; ++j)scanf("%d", &m[i][j]);
    int si, sj, sdir, ei, ej, edir;
    cin >> si >> sj >> sdir >> ei >> ej >> edir;
    queue<ele> q;
    for (int i = 1; i <= R; ++i)for (int j = 1; j <= C; ++j)for (int k = 1; k <= 4; ++k)vis[i][j][k] = INF;
    for (int i = 1; i <= 4; ++i){
        if (i == sdir){
            //기존 방향이동
            q.push(ele(si, sj, i, 0));
            vis[si][sj][i] = 0;
        }
        else if (i == getnum(sdir)){
            //뒷면 이동
            q.push(ele(si, sj, i, 2));
            vis[si][sj][i] = 2;
        }
        else{
            //나머지 좌우
            q.push(ele(si, sj, i, 1));
            vis[si][sj][i] = 1;
        }
    }

    while (!q.empty()){
        ele h = q.front(); q.pop();
        int hi = h.x; int hj = h.y; int hd = h.dir;
        int hc = h.cmd;
        int ni, nj, ndir, ncmd;
        //cout << "hi hj hdir hc" << hi << " " << hj << " " << hd << " " << hc << endl;
        if (hi == ei&&hj == ej&&hd == edir){
            cout << hc << endl;
            break;
        }
        //최대세칸
        for (int i = 1; i <= 3; ++i){
            ni = hi + di[hd] * i;
            nj = hj + dj[hd] * i;
            ndir = hd;
            if (ni<1 || ni>R || nj<1 || nj>C)break;
            if (m[ni][nj] == 1)break;
            if (vis[ni][nj][ndir] > hc+1 ){
                //회전시켜서 남은 방향 채우기
                for (int j = 1; j <= 4; ++j){
                    if (j == ndir){
                        vis[ni][nj][j] = hc + 1;
                        q.push(ele(ni, nj, j, hc + 1));
                    }
                    else if (j == getnum(ndir) && (vis[ni][nj][j] >hc+3)){
                        vis[ni][nj][j] = hc + 3;
                        q.push(ele(ni, nj, j, hc + 3));
                    }
                    else if ((vis[ni][nj][j] >hc + 2)){
                        vis[ni][nj][j] = hc + 2;
                        q.push(ele(ni, nj, j, hc + 2));
                    }
                }
            }
        }
    }


    return 0;
}
Musicals, Travel, Photo, Coding