[BFS] 1726번 로봇

1726번 로봇

 

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

 

문제

많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 다음과 같이 두 가지이다.

명령 1. Go k - k는 1, 2 또는 3일 수 있다. 현재 향하고 있는 방향으로 k칸 만큼 움직인다.

명령 2. Turn dir - dir은 left 또는 right 이며, 각각 왼쪽 또는 오른쪽으로 90° 회전한다.

공장 내 궤도가 설치되어 있는 상태가 아래와 같이 0과 1로 이루어진 직사각형 모양으로 로봇에게 입력된다. 0은 궤도가 깔려 있어 로봇이 갈 수 있는 지점이고, 1은 궤도가 없어 로봇이 갈 수 없는 지점이다. 로봇이 (4, 2) 지점에서 남쪽을 향하고 있을 때, 이 로봇을 (2, 4) 지점에서 동쪽으로 향하도록 이동시키는 것은 아래와 같이 9번의 명령으로 가능하다.

로봇의 현재 위치와 바라보는 방향이 주어졌을 때, 로봇을 원하는 위치로 이동시키고, 원하는 방향으로 바라보도록 하는데 최소 몇 번의 명령이 필요한지 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 공장 내 궤도 설치 상태를 나타내는 직사각형의 세로 길이 M과 가로 길이 N이 빈칸을 사이에 두고 주어진다. 이때 M과 N은 둘 다 100이하의 자연수이다. 이어 M줄에 걸쳐 한 줄에 N개씩 각 지점의 궤도 설치 상태를 나타내는 숫자 0 또는 1이 빈칸을 사이에 두고 주어진다. 다음 줄에는 로봇의 출발 지점의 위치 (행과 열의 번호)와 바라보는 방향이 빈칸을 사이에 두고 주어진다. 마지막 줄에는 로봇의 도착 지점의 위치 (행과 열의 번호)와 바라보는 방향이 빈칸을 사이에 두고 주어진다. 방향은 동쪽이 1, 서쪽이 2, 남쪽이 3, 북쪽이 4로 주어진다. 출발지점에서 도착지점까지는 항상 이동이 가능하다.

 

출력

첫째 줄에 로봇을 도착 지점에 원하는 방향으로 이동시키는데 필요한 최소 명령 횟수를 출력한다.

 

예제 입력

5 6
0 0 0 0 0 0
0 1 1 0 1 0
0 1 0 0 0 0
0 0 1 1 1 0
1 0 0 0 0 0
4 2 3
2 4 1

 

예제 출력

9

 

해결방법

2시간 가까이 문제를 해결하지 못하다 블로그의 도움을 조금받아서 해결하였다

 

요즘 BFS 문제인지 DFS + 백트래킹 문제인지 시간복잡도를 보는 연습을 하는데 이 문제는 잘모르겠었다..

BFS 탐색으로 생각을 해보니 100x100 배열에 각각 4개의 방향이 존재한다

따라서 시간복잡도는 O(4 * 100^2) 이라고 생각하여 BFS 탐색을 수행했다

 

한 노드에는 동 서 남 북 의 방향이 각자 존재한다

따라서 bool visited[MAX][MAX][5] 로 방문 여부를 체크해야한다

 

이제 한 노드에서 상태 변화를 각각 처리해줘야한다

먼저 앞으로 1칸, 2칸, 3칸 이동하는 상태 변화를 처리해준다

여기서 중요한 점은 만약 n-1칸 이동에서 맵 밖을 나갔거나 이동할 수 없는 영역을 만났다면 n칸은 탐색을 진행하지 않아도 된다는 점이다. 따라서 이 부분은 continue 가 아닌 break 로 처리를 해준다

// 앞으로 1,2,3 만큼 이동하는 경우
for(int i=1; i<=3; i++){
    int nx = x + dx[dir] * i;
    int ny = y + dy[dir] * i;
    
    // 만약 맵 밖을 나가거나 이동경로에 1이 있다면 더이상 나아갈 수 없음
    if(nx<=0 || ny<=0 || nx>n || ny>m) break;
    if(map[nx][ny] == 1) break;
    
    if(!visited[nx][ny][dir]){
        q.push(robot(nx,ny,dir,cnt+1));
        visited[nx][ny][dir] = true;
    }
}

 

 

이제 -90도, 90도 방향 전환을 처리해야 한다

방향 전환은 2가지의 경우가 존재한다

// 방향을 -90도, 90도 회전하는 경우
for(int i=1; i<=2; i++){
    int nDir = changeDir(i,dir);
    
    if(!visited[x][y][nDir]){
        q.push(robot(x,y,nDir,cnt+1));
        visited[x][y][nDir] = true;
    }
}

 

방향 전환은 아래와 같이 진행된다. 그러기 위해서 changeDir 이라는 함수를 만들었다

-90도 : 동 → 북 → 서 → 남

90도 : 동 → 남 → 서 → 북

int changeDir(int ind,int dir){
    int d = 0;
    // -90도 회전하는 경우
    if(ind == 1){
        if(dir == 1) d = 4;
        else if(dir == 4) d = 2;
        else if(dir == 2) d = 3;
        else if(dir == 3) d = 1;
    }
    // 90도 회전하는 경우
    else if(ind == 2){
        if(dir == 1) d = 3;
        else if(dir == 3) d = 2;
        else if(dir == 2) d = 4;
        else if(dir == 4) d = 1;
    }
    return d;
}

 

 

소스코드

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

struct robot {
    int x, y, dir, cnt;
    
    robot() { }
    robot(int _x,int _y,int _dir,int _cnt) : x(_x), y(_y), dir(_dir), cnt(_cnt) { }
};

int n,m;
int map[MAX][MAX];
bool visited[MAX][MAX][5];

robot s,e;

// 동 서 남 북
int dx[5] = {0,0,0,1,-1};
int dy[5] = {0,1,-1,0,0};

int changeDir(int ind,int dir){
    int d = 0;
    // -90도 회전하는 경우
    if(ind == 1){
        if(dir == 1) d = 4;
        else if(dir == 4) d = 2;
        else if(dir == 2) d = 3;
        else if(dir == 3) d = 1;
    }
    // 90도 회전하는 경우
    else if(ind == 2){
        if(dir == 1) d = 3;
        else if(dir == 3) d = 2;
        else if(dir == 2) d = 4;
        else if(dir == 4) d = 1;
    }
    return d;
}

void bfs(){
    queue<robot> q;
    q.push(s);
    visited[s.x][s.y][s.dir] = true;
    
    while(!q.empty()){
        int x = q.front().x;
        int y = q.front().y;
        int dir = q.front().dir;
        int cnt = q.front().cnt;
        q.pop();
        
        // 종료 지점에 도달했을 경우
        if(x==e.x && y==e.y && dir==e.dir){
            cout << cnt << "\n";
            return;
        }
        
        // 앞으로 1,2,3 만큼 이동하는 경우
        for(int i=1; i<=3; i++){
            int nx = x + dx[dir] * i;
            int ny = y + dy[dir] * i;
            
            // 만약 맵 밖을 나가거나 이동경로에 1이 있다면 더이상 나아갈 수 없음
            if(nx<=0 || ny<=0 || nx>n || ny>m) break;
            if(map[nx][ny] == 1) break;
            
            if(!visited[nx][ny][dir]){
                q.push(robot(nx,ny,dir,cnt+1));
                visited[nx][ny][dir] = true;
            }
        }
        
        // 방향을 -90도, 90도 회전하는 경우
        for(int i=1; i<=2; i++){
            int nDir = changeDir(i,dir);
            
            if(!visited[x][y][nDir]){
                q.push(robot(x,y,nDir,cnt+1));
                visited[x][y][nDir] = true;
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cin >> map[i][j];
        }
    }
    
    // 로봇의 시작상태와 종료상태 입력
    cin >> s.x >> s.y >> s.dir;
    cin >> e.x >> e.y >> e.dir;
    
    // BFS 탐색
    memset(visited, false, sizeof(visited));
    bfs();
    
    return 0;
}