구현이 어려운 문제다.
어떻게 풀지 생각하는데 오래 걸리지 않았는데, 신경써야 할 부분이 많아 풀이하는데 오래걸렸다.
풀이 방법은 다음과 같다.
로봇이 이동할 수 있는 경우는 회전하거나 전체가 움직이는 경우다.
1. 회전의 경우 로봇의 각 좌표를 기준으로 회전했을 때 가능한 경우가 있으면 이동한다.
2. 전체가 움직이는 경우는 2개 좌표에 같은 값을 + 또는 - 연산을 진행해 가능한 위치가 있으면 이동한다.
3. 1,2 번을 통해 이동한 좌표는 다시 방문하지 않도록 visited 배열을 이용해 표시한다.
4, 1,2,3 번을 반복하다 목표 좌표에 도착하면 값을 반환한다.
|
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
|
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
const int MAX = 110;
const int check_dir_y[4] = { -1, -1, 1, 1};
const int check_dir_x[4] = { -1, 1, 1, -1};
const int dir_y[4] = { -1, 0, 1, 0};
const int dir_x[4] = { 0, 1, 0, -1};
const int left_check_dir_y[4] = { -1, -1, 1, 1};
const int left_check_dir_x[4] = { 1, -1, -1, 1};
const int left_dir_y[4] = { -1, 0, 1, 0};
const int left_dir_x[4] = { 0, -1, 0, 1};
bool visited[MAX][MAX][MAX][MAX];
vector<vector<int>> copy_board;
int check_possible(pair<int,int> check, pair<int,int> move, pair<int,int> ori, int board_max) {
if (check.first < 0 || check.first > board_max || check.second < 0 || check.second > board_max) { return 0; }
if (move.first < 0 || move.first > board_max || move.second < 0 || move.second > board_max) { return 0; }
if(copy_board[move.first][move.second] || copy_board[check.first][check.second]) { return 0; }
if(visited[ori.first][ori.second][move.first][move.second]) { return 2; }
return 1;
}
void check_visited(pair<int,int> one, pair<int,int> two) {
visited[one.first][one.second][two.first][two.second] = true;
visited[two.first][two.second][one.first][one.second] = true;
}
int solution(vector<vector<int>> board) {
int answer = 0;
copy_board = board;
int board_max = board.size() - 1;
int dir;
queue<pair<int, pair<pair<int,int>, pair<int,int>>>> que;
que.push({0,{{0,0},{0,1}}});
visited[0][0][0][1] = true;
visited[0][1][0][0] = true;
while(!que.empty()) {
int count = que.front().first;
pair<int,int> one = que.front().second.first;
pair<int,int> two = que.front().second.second;
que.pop();
if((one.first == board_max && one.second == board_max)
|| (two.first == board_max && two.second == board_max)) {
return count;
}
if (one.first > two.first) { dir = 1; }
if (one.second < two.second) { dir = 2; }
if (one.first < two.first) { dir = 3; }
if (one.second > two.second) { dir = 0; }
for (int i = dir; i < dir + 4; i++) {
int move_y = one.first + dir_y[i % 4];
int move_x = one.second + dir_x[i % 4];
int check_y = one.first + check_dir_y[i % 4];
int check_x = one.second + check_dir_x[i % 4];
int check = check_possible({check_y,check_x}, {move_y,move_x}, {one.first,one.second}, board_max);
if(!check) { break; } else if(check == 2) { continue; }
check_visited(one, {move_y, move_x});
que.push({count+1, {one, {move_y,move_x}}});
break;
}
if (one.first < two.first) { dir = 1; }
if (one.second > two.second) { dir = 2; }
if (one.first > two.first) { dir = 3; }
if (one.second < two.second) { dir = 0; }
for (int i = dir; i < dir + 4; i++) {
int move_y = two.first + dir_y[i % 4];
int move_x = two.second + dir_x[i % 4];
int check_y = two.first + check_dir_y[i % 4];
int check_x = two.second + check_dir_x[i % 4];
int check = check_possible({check_y,check_x}, {move_y,move_x}, {two.first,two.second}, board_max);
if(!check) { break; } else if(check == 2) { continue; }
check_visited(two, {move_y, move_x});
que.push({count+1, {{move_y,move_x},two}});
break;
}
if (one.first > two.first) { dir = 1; }
if (one.second > two.second) { dir = 2; }
if (one.first < two.first) { dir = 3; }
if (one.second < two.second) { dir = 0; }
for (int i = dir; i < dir + 4; i++) {
int move_y = one.first + left_dir_y[i % 4];
int move_x = one.second + left_dir_x[i % 4];
int check_y = one.first + left_check_dir_y[i % 4];
int check_x = one.second + left_check_dir_x[i % 4];
int check = check_possible({check_y,check_x}, {move_y,move_x}, {one.first,one.second}, board_max);
if(!check) { break; } else if(check == 2) { continue; }
check_visited(one, {move_y, move_x});
que.push({count+1, {one, {move_y,move_x}}});
break;
}
if (one.first < two.first) { dir = 1; }
if (one.second < two.second) { dir = 2; }
if (one.first > two.first) { dir = 3; }
if (one.second > two.second) { dir = 0; }
for (int i = dir; i < dir + 4; i++) {
int move_y = two.first + left_dir_y[i % 4];
int move_x = two.second + left_dir_x[i % 4];
int check_y = two.first + left_check_dir_y[i % 4];
int check_x = two.second + left_check_dir_x[i % 4];
int check = check_possible({check_y,check_x}, {move_y,move_x}, {two.first,two.second}, board_max);
if(!check) { break; } else if(check == 2) { continue; }
check_visited(two, {move_y, move_x});
que.push({count+1, {{move_y,move_x},two}});
break;
}
for (int i = 0; i < 4; i++) {
int move_y = one.first + dir_y[i];
int move_x = one.second + dir_x[i];
int move_y_2 = two.first + dir_y[i];
int move_x_2 = two.second + dir_x[i];
int check = check_possible({move_y_2,move_x_2}, {move_y,move_x}, {move_y_2,move_x_2}, board_max);
if(check != 1) { continue; }
check_visited({move_y_2,move_x_2}, {move_y, move_x});
que.push({count+1, {{move_y, move_x},{move_y_2, move_x_2}}});
}
}
return answer;
}
|
cs |
'problem solving' 카테고리의 다른 글
| [프로그래머스]불량 사용자 (0) | 2020.09.05 |
|---|---|
| [프로그래머스]외벽 점검 (0) | 2020.09.04 |
| [프로그래머스]기둥과 보 설치 (0) | 2020.08.31 |
| [프로그래머스]자물쇠와 열쇠 (0) | 2020.08.30 |
| [프로그래머스]수식 최대화 (0) | 2020.08.27 |