요약하면 땅따먹기 게임이다.
이동하면 발판이 사라지고 이동할 자리가 없으면 패배
A플레이어는 선공으로 최대한 빨리 끝내는 방향으로 이동하며
B플레이어는 최대한 질질끄는 방향으로 이동한다.
기본 코드
1 2 3 4 5 6 7 8 9 | #include <string> #include <vector> using namespace std; int solution(vector<vector<int>> board, vector<int> aloc, vector<int> bloc) { int answer = -1; return answer; } | cs |
이전에 한번 속은 적이 있으니
무시하고 다 바꾸기로 하였음
answer 변수가 -1로 돼있는걸 보니 아마 재귀함수로
노드 탐색을 하라는것 같으므로
A 플레이어는 가장 빨리 게임이 끝나는 모든 경우의 수를 찾아서
그 방향으로 이동하기로 함
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 | struct Point { int x; int y; Point(int x, int y) { this->x = x; this->y = y; } }; enum Direction//m_compare 알아보기 쉽게 { UP, DOWN, LEFT, RIGHT }; //가장 턴수가 적게 드는 경우 탐색 int solution(vector<vector<int>>& m_beforeboard, Point& m_first, Point m_last, int m_level) { int answer = m_level;//진행된 턴 수 vector<vector<int>> m_newboard; Point m_nextposition = m_first; int m_compare[4] = {0,0,0,0}; m_newboard = m_beforeboard;//보드판 복사 m_newboard[m_first.y][m_first.x] = 0;//원래 있던 자리는 0으로 만들고 이동하고 다음 패턴 예측 answer++; if (m_first.x == m_last.x && m_first.y == m_last.y)//패배 확정일 경우 쓸데없는 연산 무시하고 0리턴 { return 0; } if (0 <= m_first.y - 1)//위쪽으로 이동했을 경우 턴 예측 { if (m_newboard[m_first.y - 1][m_first.x] != 0) { m_nextposition = Point(m_first.x, m_first.y - 1); m_compare[0] = solution(m_newboard, m_last, m_nextposition, answer); } } if (m_newboard.size() > m_first.y + 1)//아래쪽으로 이동했을 경우 턴 예측 { if (m_newboard[m_first.y + 1][m_first.x] != 0) { m_nextposition = Point(m_first.x, m_first.y + 1); m_compare[1] = solution(m_newboard, m_last, m_nextposition, answer); } } if (0 <= m_first.x - 1)//왼쪽으로 이동했을 경우 턴 예측 { if (m_newboard[m_first.y][m_first.x - 1] != 0) { m_nextposition = Point(m_first.x - 1, m_first.y); m_compare[2] = solution(m_newboard, m_last, m_nextposition, answer); } } if (m_newboard[0].size() > m_first.x + 1)//오른쪽으로 이동했을 경우 턴 예측 { if (m_newboard[m_first.y][m_first.x + 1] != 0) { m_nextposition = Point(m_first.x + 1, m_first.y); m_compare[3] = solution(m_newboard, m_last, m_nextposition, answer); } } int min = INT_MAX; for (int obj : m_compare) { if (obj < min && obj != 0) min = obj; } if (answer == 1)//최상위 노드일 경우 { int m_direction = 5; for (int i = 0; i < 4; i++)//어느 방향으로 이동해야 하는지 찾기 { if (m_compare[i]==min) { m_direction = i; } } m_beforeboard[m_first.y][m_first.x] = 0;//이전 위치는 0으로 만들고 이동 switch (m_direction)//이동 { case UP: m_nextposition = Point(m_first.x, m_first.y - 1); m_first = m_nextposition; break; case DOWN: m_nextposition = Point(m_first.x, m_first.y + 1); m_first = m_nextposition; break; case LEFT: m_nextposition = Point(m_first.x - 1, m_first.y); m_first = m_nextposition; break; case RIGHT: m_nextposition = Point(m_first.x + 1, m_first.y); m_first = m_nextposition; break; default: cout << "이동할 곳이 없습니다." << endl; return 0; break; } } if (min != INT_MAX) answer = min;//가장 작은 턴수를 리턴 m_newboard.clear(); vector<vector<int>>().swap(m_newboard); return answer; } | cs |
A플레이어의 경로 탐색 알고리즘
결과
이런 식으로 이동하고
B플레이어는 최대한 오래 살아남기 위해
노드 중 레벨이 가장 낮은 방향으로 이동하기로 함
A플레이어 알고리즘에서 부등호랑 몇개만 바꾸면 됨
하자가 조금 있긴 한데 나중에 시간되면 수정할 생각이다.
전체 코드
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 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 | #include <string> #include <vector> #include <algorithm> #include <iostream> using namespace std; struct Point { int x; int y; Point(int x, int y) { this->x = x; this->y = y; } }; enum Direction//m_compare 알아보기 쉽게 { UP, DOWN, LEFT, RIGHT }; //가장 턴수가 적게 드는 경우 탐색 int solution(vector<vector<int>>& m_beforeboard, Point& m_first, Point m_last, int m_level) { int answer = m_level;//진행된 턴 수 vector<vector<int>> m_newboard; Point m_nextposition = m_first; int m_compare[4] = {0,0,0,0}; m_newboard = m_beforeboard;//보드판 복사 m_newboard[m_first.y][m_first.x] = 0;//원래 있던 자리는 0으로 만들고 이동하고 다음 패턴 예측 answer++; if (m_first.x == m_last.x && m_first.y == m_last.y)//패배 확정일 경우 쓸데없는 연산 무시하고 0리턴 { return 0; } if (0 <= m_first.y - 1)//위쪽으로 이동했을 경우 턴 예측 { if (m_newboard[m_first.y - 1][m_first.x] != 0) { m_nextposition = Point(m_first.x, m_first.y - 1); m_compare[UP] = solution(m_newboard, m_last, m_nextposition, answer); } } if (m_newboard.size() > m_first.y + 1)//아래쪽으로 이동했을 경우 턴 예측 { if (m_newboard[m_first.y + 1][m_first.x] != 0) { m_nextposition = Point(m_first.x, m_first.y + 1); m_compare[DOWN] = solution(m_newboard, m_last, m_nextposition, answer); } } if (0 <= m_first.x - 1)//왼쪽으로 이동했을 경우 턴 예측 { if (m_newboard[m_first.y][m_first.x - 1] != 0) { m_nextposition = Point(m_first.x - 1, m_first.y); m_compare[LEFT] = solution(m_newboard, m_last, m_nextposition, answer); } } if (m_newboard[0].size() > m_first.x + 1)//오른쪽으로 이동했을 경우 턴 예측 { if (m_newboard[m_first.y][m_first.x + 1] != 0) { m_nextposition = Point(m_first.x + 1, m_first.y); m_compare[RIGHT] = solution(m_newboard, m_last, m_nextposition, answer); } } int min = INT_MAX; for (int obj : m_compare) { if (obj < min && obj != 0) min = obj; } if (answer == 1)//최상위 노드일 경우 { int m_direction = 5; for (int i = 0; i < 4; i++)//어느 방향으로 이동해야 하는지 찾기 { if (m_compare[i]==min) { m_direction = i; } } m_beforeboard[m_first.y][m_first.x] = 0;//이전 위치는 0으로 만들고 이동 switch (m_direction)//이동 { case UP: m_nextposition = Point(m_first.x, m_first.y - 1); m_first = m_nextposition; break; case DOWN: m_nextposition = Point(m_first.x, m_first.y + 1); m_first = m_nextposition; break; case LEFT: m_nextposition = Point(m_first.x - 1, m_first.y); m_first = m_nextposition; break; case RIGHT: m_nextposition = Point(m_first.x + 1, m_first.y); m_first = m_nextposition; break; default: cout << "이동할 곳이 없습니다." << endl; return 0; break; } } if (min != INT_MAX) answer = min;//가장 작은 턴수를 리턴 m_newboard.clear(); vector<vector<int>>().swap(m_newboard); return answer; } int solution2(vector<vector<int>>& m_beforeboard, Point& m_first, Point m_last, int m_level) { int answer = m_level;//진행된 턴 수 vector<vector<int>> m_newboard; Point m_nextposition = m_first; int m_compare[4] = { 0,0,0,0 }; m_newboard = m_beforeboard;//보드판 복사 m_newboard[m_first.y][m_first.x] = 0;//원래 있던 자리는 0으로 만들고 이동하고 다음 패턴 예측 answer++; if (m_first.x == m_last.x && m_first.y == m_last.y)//패배 확정일 경우 쓸데없는 연산 무시하고 0리턴 { return 0; } if (0 <= m_first.y - 1)//위쪽으로 이동했을 경우 턴 예측 { if (m_newboard[m_first.y - 1][m_first.x] != 0) { m_nextposition = Point(m_first.x, m_first.y - 1); m_compare[UP] = solution2(m_newboard, m_last, m_nextposition, answer); } } if (m_newboard.size() > m_first.y + 1)//아래쪽으로 이동했을 경우 턴 예측 { if (m_newboard[m_first.y + 1][m_first.x] != 0) { m_nextposition = Point(m_first.x, m_first.y + 1); m_compare[DOWN] = solution2(m_newboard, m_last, m_nextposition, answer); } } if (0 <= m_first.x - 1)//왼쪽으로 이동했을 경우 턴 예측 { if (m_newboard[m_first.y][m_first.x - 1] != 0) { m_nextposition = Point(m_first.x - 1, m_first.y); m_compare[LEFT] = solution2(m_newboard, m_last, m_nextposition, answer); } } if (m_newboard[0].size() > m_first.x + 1)//오른쪽으로 이동했을 경우 턴 예측 { if (m_newboard[m_first.y][m_first.x + 1] != 0) { m_nextposition = Point(m_first.x + 1, m_first.y); m_compare[RIGHT] = solution2(m_newboard, m_last, m_nextposition, answer); } } int max = 0; for (int obj : m_compare) { if (obj > max) max = obj; } if (answer == 1)//최상위 노드일 경우 { int m_direction; for (int i = 0; i < 4; i++)//어느 방향으로 이동해야 하는지 찾기 { if (m_compare[i] == max) { m_direction = i; } if (max == 0)//이동할 곳이 없으면 m_direction = 5; //default로 } m_beforeboard[m_first.y][m_first.x] = 0;//이전 위치는 0으로 만들고 이동 switch (m_direction)//이동 { case UP: m_nextposition = Point(m_first.x, m_first.y - 1); m_first = m_nextposition; break; case DOWN: m_nextposition = Point(m_first.x, m_first.y + 1); m_first = m_nextposition; break; case LEFT: m_nextposition = Point(m_first.x - 1, m_first.y); m_first = m_nextposition; break; case RIGHT: m_nextposition = Point(m_first.x + 1, m_first.y); m_first = m_nextposition; break; default: cout << "이동할 곳이 없습니다." << endl; break; } } if (max != 0) answer = max;//가장 작은 턴수를 리턴 m_newboard.clear(); vector<vector<int>>().swap(m_newboard); return answer; } void ShowBoard(vector<vector<int>> m_board, Point m_player1, Point m_player2) { for (int i = 0; i < m_board.size(); i++) { for (int j = 0; j < m_board[0].size(); j++) { cout.width(2); if (m_player1.x == j && m_player1.y == i) { cout << "■"; }else if (m_player2.x == j && m_player2.y == i) { cout << "□"; } else { cout << m_board[i][j]; } } cout << endl; } cout << endl; } //대각선 이동 불가능 //땅따먹기 일종의 게임 void main() { vector<vector<int>> m_board;//보드 원본 Point m_player1(0, 2), m_player2(4, 2);//두 플레이어의 초기 위치 m_board = { {1,1,1,1,1},{1,1,1,1,1},{1,1,1,1,1},{1,1,1,1,1},{1,1,1,1,1} }; //5x5 보드 solution(m_board, m_player1, m_player2, 0);//가장 적게 걸리는 턴만 계산 ShowBoard(m_board, m_player1, m_player2);//보드판 출력 solution2(m_board, m_player2, m_player1, 0);//가장 오래 걸리는 턴만 계산 ShowBoard(m_board, m_player1, m_player2);//보드판 출력 solution(m_board, m_player1, m_player2, 0);//가장 적게 걸리는 턴만 계산 ShowBoard(m_board, m_player1, m_player2);//보드판 출력 solution2(m_board, m_player2, m_player1, 0);//가장 오래 걸리는 턴만 계산 ShowBoard(m_board, m_player1, m_player2);//보드판 출력 solution(m_board, m_player1, m_player2, 0);//가장 적게 걸리는 턴만 계산 ShowBoard(m_board, m_player1, m_player2);//보드판 출력 solution2(m_board, m_player2, m_player1, 0);//가장 오래 걸리는 턴만 계산 ShowBoard(m_board, m_player1, m_player2);//보드판 출력 solution(m_board, m_player1, m_player2, 0);//가장 적게 걸리는 턴만 계산 ShowBoard(m_board, m_player1, m_player2);//보드판 출력 solution2(m_board, m_player2, m_player1, 0);//가장 오래 걸리는 턴만 계산 ShowBoard(m_board, m_player1, m_player2);//보드판 출력 solution(m_board, m_player1, m_player2, 0);//가장 적게 걸리는 턴만 계산 ShowBoard(m_board, m_player1, m_player2);//보드판 출력 solution2(m_board, m_player2, m_player1, 0);//가장 오래 걸리는 턴만 계산 ShowBoard(m_board, m_player1, m_player2);//보드판 출력 solution(m_board, m_player1, m_player2, 0);//가장 적게 걸리는 턴만 계산 ShowBoard(m_board, m_player1, m_player2);//보드판 출력 solution2(m_board, m_player2, m_player1, 0);//가장 오래 걸리는 턴만 계산 ShowBoard(m_board, m_player1, m_player2);//보드판 출력 solution(m_board, m_player1, m_player2, 0);//가장 적게 걸리는 턴만 계산 ShowBoard(m_board, m_player1, m_player2);//보드판 출력 solution2(m_board, m_player2, m_player1, 0);//가장 오래 걸리는 턴만 계산 ShowBoard(m_board, m_player1, m_player2);//보드판 출력 solution(m_board, m_player1, m_player2, 0);//가장 적게 걸리는 턴만 계산 ShowBoard(m_board, m_player1, m_player2);//보드판 출력 solution2(m_board, m_player2, m_player1, 0);//가장 오래 걸리는 턴만 계산 ShowBoard(m_board, m_player1, m_player2);//보드판 출력 } | cs |
뭔가 A가 더 질질 끄는 듯 하다.
A 알고리즘에서는 두 플레이어 모두 최단으로 이동했을 모든 경우를
탐색해버려서 이런 결과가 나온것 같다.
solution에서는 solution을 호출하고, solution2에서는 2를 호출하고 있어서
상대방의 경로를 제대로 예측 못하고 있다.
홀수 레벨에서는 solution을, 짝수 레벨에서는 solution2를 호출하면 해결될듯 하다.
댓글 없음:
댓글 쓰기