Algorithm/BOJ

[백준 1726] 로봇 (c++)

Henu 2021. 11. 20. 14:21
 

1726번: 로봇

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

www.acmicpc.net

 

오랜만에 푼 알고리즘 문제

 

  • 명령 1. Go k: k는 1, 2 또는 3일 수 있다. 현재 향하고 있는 방향으로 k칸 만큼 움직인다.
  • 명령 2. Turn dir: dir은 left 또는 right 이며, 각각 왼쪽 또는 오른쪽으로 90° 회전한다.

 

  두 가지 조건을 만족하며 출발 로봇이 도착지점의 상태와 같아질 때까지 이동시키는 프로그램을 구현하면된다. 나는 K칸 만큼 움직일 때 갈 수 없는 모든 조건에 break를 걸어주어서 많이 틀렸다. 벽에 막혀서 갈 수 없는 경우에만 break를 걸어서 다음 k+1칸을 탐색하지 않아야 했는데 방문한 경우나 맵을 벗어나는 경우에도 break를 걸어서 k+1칸을 탐색하지 않았다. 이 경우에 어떤 문제가 발생하냐면 K=2일때 해당 칸에 이미 방문해서 break가 걸렸다고 하자. 그런데 K=3일때는 아직 방문하지 않았고 맵 내부에 있으며 벽에 막혀있지 않는경우에 해당 칸에 갈 수 없는 경우가 발생하거나 최단 경로를 구하지 못하는 경우가 발생할 것이다. 

 

  방향 전환 같은 경우는 단순하고 직관적으로 짜는게 좋아서 그렇게 구현했다. +47 ~ +59

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define pii pair<int, int>
 
typedef long long ll;
// typedef pair<int, int> pii;
 
using namespace std;
 
 
// 명령 1. Go k: k는 1, 2 또는 3일 수 있다. 현재 향하고 있는 방향으로 k칸 만큼 움직인다.
// 명령 2. Turn dir: dir은 left 또는 right 이며, 각각 왼쪽 또는 오른쪽으로 90° 회전한다.
 
struct State{
    int r, c, dir;
    int cnt = 0;
};
 
bool operator==(State &a, State &b){
    return a.r == b.r && a.c == b.c && a.dir == b.dir;
}
 
int N, M;
int Map[101][101];
State src, dst;
 
int dr[5] = {0, 0, 0, 1, -1};
int dc[5] = {0, 1, -1, 0, 0};
 
void input(){
    cin >> N >> M;
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            cin >> Map[i][j];
        }
    }
    cin >> src.r >> src.c >> src.dir;
    cin >> dst.r >> dst.c >> dst.dir;
}
 
int turn_right(int d){
    if(d == 1) return 3;
    else if(d == 2) return 4;
    else if(d == 3) return 2;
    else return 1;
}
 
int turn_left(int d){
    if(d == 1) return 4;
    else if(d == 2) return 3;
    else if(d == 3) return 1;
    else return 2;
}
 
int bfs(){
    queue<State> que;
    que.push(src);
    
    bool visited[101][101][5];
    memset(visited, 0, sizeof(visited));
    visited[src.r][src.c][src.dir] = true;
    
    while(!que.empty()){
        State now = que.front();
        que.pop();
        
        if(now == dst){
            return now.cnt;
        }
        
        // 명령1
        for(int k = 1; k <= 3; k++){
            // 1, 2, 3 칸만큼 움직임
            int nr = now.r + dr[now.dir] * k;
            int nc = now.c + dc[now.dir] * k;
            // 벽이 있는 경우에만 break시켜준다
            // 조건을 하나로 묶어버리면 벽은 없지만 k칸 이동했을 때 방문한 적이 있다면 
            // 바로 break가 걸리기 때문에 정답을 못구할 수도 있다.
            if(Map[nr][nc]) break;
            if(nr < 1 || nr > N || nc < 1 || nc > M || visited[nr][nc][now.dir]) continue;
            
            // 갈 수 있는 경우
            visited[nr][nc][now.dir] = true;
            que.push({nr, nc, now.dir, now.cnt+1});
        }
        
        // 명령2
        int td = turn_left(now.dir);
        if(!visited[now.r][now.c][td]){
            visited[now.r][now.c][td] = true;
            que.push({now.r, now.c, td, now.cnt+1});
        }
        
        td = turn_right(now.dir);
        if(!visited[now.r][now.c][td]){
            visited[now.r][now.c][td] = true;
            que.push({now.r, now.c, td, now.cnt+1});
        }
    }
    
    return -1;
}
 
 
int main(){
    fastio
    input();
    cout << bfs();
    
    return 0;
}
 
 cs