반응형

문제 출처 :


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



알고리즘 분석 :


문제 해결에 필요한 사항

1. 시뮬레이션


일단 아래와 같이 배열을 이용하기 위해 위, 아래 방향을 거꾸로 생각한다.


이렇게 생각한다면 왼쪽으로 돌때 오른쪽으로 돌때도 반대가 돼야한다.


즉, 원래 그림상에서 (1,1) 로봇이 E 방향을 보고있다가 왼쪽을 돌면 N을 봐야하지만, 


이제부터는 E방향을 보다가 왼쪽을 돌면 S를 보게 해야한다.


따라서 E->S->W->N->E ... 방향이 왼쪽이라 생각하고


E->N->W->S->E ... 방향을 오른쪽이라 생각한다.


이유는 y축이 지금 뒤집혔기 때문에(N, S방향도 반대이다.) x축에는 영향이 없지만 나머지를 거꾸로 생각해야 한다.


그렇게 생각하고 시뮬레이션 코드를 작성하면 쉽게 통과 할 수 있다.





소스 코드 : 


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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include <iostream>
#include <cstdio>
 
using namespace std;
 
typedef pair<int, int> pii;
typedef struct _ROBOT_
{
    int x, y;
    char dir;
    pii dirxy;
}ROBOT;
 
int map[111][111];
ROBOT robot[111];
 
int a, b, n, m;
 
int chkRange(int y, int x)
{
    if (y < 1 || x < 1 || y > b || x > a)
        return -1;
    return 1;
}
 
int chkRobot(int idx, int y, int x)
{
    for (int i = 1; i <= n; i++)
    {
        if (i == idx)
            continue;
 
        if (robot[i].y == y && robot[i].x == x)
            return i;
    }
    return 0;
}
 
int main()
{
    scanf("%d %d %d %d", &a, &b, &n, &m);
 
    for (int i = 1; i <= n; i++)
    {
        scanf("%d %d %c", &robot[i].x, &robot[i].y, &robot[i].dir);
        if (robot[i].dir == 'W')
            robot[i].dirxy = { -1,0 };
        else if (robot[i].dir == 'E')
            robot[i].dirxy = { 1,0 };
        else if (robot[i].dir == 'S') // S, N이 아래, 위가 아닌 위, 아래
            robot[i].dirxy = { 0, -1 };
        else if (robot[i].dir == 'N')
            robot[i].dirxy = { 0, 1 };
        
        if (chkRange(robot[i].y, robot[i].x) == -1)
        {
            printf("Robot %d crashes into the wall\n", i);
            return 0;
        }
 
        int crash = chkRobot(i, robot[i].y, robot[i].x);
        if (crash)
        {
            printf("Robot %d crashes into robot %d\n", i, crash);
            return 0;
        }
    }
 
    for (int i = 0; i < m; i++)
    {
        // 로봇 번호, 이동 수
        int idx, cnt;
        char order; // 명령
 
        scanf("%d %c %d", &idx, &order, &cnt);
 
        if (order == 'F')
        {
            int x = robot[idx].dirxy.first;
            int y = robot[idx].dirxy.second;
 
            for (int j = 0; j < cnt; j++)
            {
                robot[idx].x += x;
                robot[idx].y += y;
 
                if (chkRange(robot[idx].y, robot[idx].x) == -1)
                {
                    printf("Robot %d crashes into the wall\n", idx);
                    return 0;
                }
 
                int crash = chkRobot(idx, robot[idx].y, robot[idx].x);
                if (crash)
                {
                    printf("Robot %d crashes into robot %d\n", idx, crash);
                    return 0;
                }
            }
        }
 
        else if (order == 'R')
        {
            int y = robot[idx].dirxy.second;
            int x = robot[idx].dirxy.first;
 
            for (int j = 0; j < cnt; j++)
            {
                if (x == 1 && y == 0)
                    x = 0, y = -1;
                else if (x == 0 && y == -1)
                    x = -1, y = 0;
                else if (x == -1, y == 0)
                    x = 0, y = 1;
                else if (x == 0 && y == 1)
                    x = 1, y = 0;
            }
 
            robot[idx].dirxy.first = x;
            robot[idx].dirxy.second = y;
        }
 
        else if (order == 'L')
        {
            int y = robot[idx].dirxy.second;
            int x = robot[idx].dirxy.first;
 
            for (int j = 0; j < cnt; j++)
            {
                if (x == 1 && y == 0)
                    x = 0, y = 1;
                else if (x == 0 && y == 1)
                    x = -1, y = 0;
                else if (x == -1, y == 0)
                    x = 0, y = -1;
                else if (x == 0 && y == -1)
                    x = 1, y = 0;
            }
 
            robot[idx].dirxy.first = x;
            robot[idx].dirxy.second = y;
        }
    }
 
    printf("OK");
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus


반응형
저작자표시 비영리 변경금지

'Applied > 알고리즘 문제풀이' 카테고리의 다른 글

[9251번] LCS  (0) 2017.04.19
[8983번] 사냥꾼  (0) 2017.04.18
[7578번] 공장  (2) 2017.04.17
[11003번] 최소값 찾기  (0) 2017.04.17
[1966번] 프린터 큐  (0) 2017.04.17

티스토리툴바