반응형

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

 

1726번: 로봇

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

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 로봇의 시작점과 도착점을 입력받아서 저장합니다.

 

2. 로봇의 시작점을 queue에 넣고 bfs를 돌리면서 visited [ y ][ x ][ dir ] 배열에 현재까지의 명령어 입력 횟수를 저장합니다.

 

3. 도착점에 도착하면 방향의 일치 여부를 판단하고 일치하면 cnt를 ans의 값과 비교하여 더 작은 값을 ans에 저장하고, 다르다면 방향에 따라 cnt에 1 ~ 2를 더해주어 ans의 값과 비교하여 더 작은 값을 ans에 저장합니다.

 

4. ans를 출력합니다.

 

[ 소스코드 ]

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
119
120
121
122
123
124
125
126
127
128
#include<iostream>
#include<queue>
 
using namespace std;
 
struct robot {
    int y;
    int x;
    int dir;
    int cnt;
};
 
int N, M;
int arr[101][101];
int visited[101][101][5];
int dy[5] = { 0,0,0,1,-1 };
int dx[5] = { 0,1,-1,0,0 };
int ans = 987654321;
 
int main()
{
    scanf("%d %d", &M, &N);
 
    for (int i = 1; i <= M; i++) {
        for (int j = 1; j <= N; j++) {
            scanf("%d", &arr[i][j]);
            for (int k = 1; k <= 4; k++) {
                visited[i][j][k] = 987654321;
            }
        }
    }
 
    robot start, end;
 
    scanf("%d %d %d", &start.y, &start.x, &start.dir);
    scanf("%d %d %d", &end.y, &end.x, &end.dir);
 
    queue<robot> q;
 
    q.push({ start.y, start.x, start.dir, 0 });
 
    while (!q.empty()) {
        const int y = q.front().y;
        const int x = q.front().x;
        const int dir = q.front().dir;
        int cnt = q.front().cnt;
        q.pop();
        
        if (y == end.y && x == end.x) {
            if (dir != end.dir) {
                if (dir == 1 || dir == 2) {
                    if (end.dir == 3 || end.dir == 4) {
                        cnt += 1;
                    }
                    else {
                        cnt += 2;
                    }
                }
                else {
                    if (end.dir == 1 || end.dir == 2) {
                        cnt += 1;
                    }
                    else {
                        cnt += 2;
                    }
                }
            }
            
            ans = min(ans, cnt);
        }
 
        for (int i = 0; i < 4; i++) {
            for (int j = 1; j <= 3; j++) {
                int temp = dir + i;
                if (temp > 4) {
                    temp -= 4;
                }
                int yy = y + dy[temp]*j;
                int xx = x + dx[temp]*j;
 
                if (yy > 0 && yy <= M && xx > 0 && xx <= N) {
                    if (arr[yy][xx] == 0) {
                        if (i == 0) {
                            if (visited[yy][xx][temp] > cnt + 1) {
                                visited[yy][xx][temp] = cnt + 1;
                                q.push({ yy,xx,temp,cnt + 1 });
                            }
                        }
                        else {
                            if (dir == 1 || dir == 3) {
                                if (i == 1) {
                                    if (visited[yy][xx][temp] > cnt + 3) {
                                        visited[yy][xx][temp] = cnt + 3;
                                        q.push({ yy,xx,temp,cnt + 3 });
                                    }
                                }
                                else if (i == 2 || i == 3) {
                                    if (visited[yy][xx][temp] > cnt + 2) {
                                        visited[yy][xx][temp] = cnt + 2;
                                        q.push({ yy,xx,temp,cnt + 2 });
                                    }
                                }
                            }
                            else {
                                if (i == 3) {
                                    if (visited[yy][xx][temp] > cnt + 3) {
                                        visited[yy][xx][temp] = cnt + 3;
                                        q.push({ yy,xx,temp,cnt + 3 });
                                    }
                                }
                                else if (i == 1 || i == 2) {
                                    if (visited[yy][xx][temp] > cnt + 2) {
                                        visited[yy][xx][temp] = cnt + 2;
                                        q.push({ yy,xx,temp,cnt + 2 });
                                    }
                                }
                            }
                        }
                    }
                    else break;
                }
                else break;
            }
        }
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 9019번 - DSLR (C++)  (0) 2022.12.13
[ 백준 ] 2665번 - 미로만들기 (C++)  (0) 2022.12.12
[ 백준 ] 24042번 - 횡단보도 (C++)  (0) 2022.12.10
[ 백준 ] 1600번 - 말이 되고픈 원숭이 (C++)  (0) 2022.12.09
[ 백준 ] 16393번 - Lost Map (C++)  (0) 2022.12.08

+ Recent posts

티스토리툴바