반응형
알고리즘 분류 : 시뮬레이션
윷놀이 게임을 프로그래밍해야 하는 문제다. 문제에 주어진 조건 그대로 구현해야 한다. 서브태스크 순서대로 설계하면 도움이 된다.
- 우선 윷놀이 판에 대한 좌표를 분석하는 것이 좋다.
- 말이 놓이는 칸은 일정한 규칙을 가지고 있다. 가장 자리 라인은 6의 배수, 대각선 라인은 5의 배수이다
- 좌표를 (X, Y)라고 했을 때, 규칙은 아래와 같다.
- ↑(X, 30) | ←(0, Y) | ↓(X, 0) | →(30, Y) | ↙(X != Y) | ↘(X == Y)
- 말이 꺾이는 지점인 (0, 30), (0, 0), (15, 15)은 별도로 처리하는 것이 좋다.
- 각 말을 판에 놓을 때는, Aa (X, Y), Bb (X, Y+1), Cc (X+1, Y), Dd (X+1, Y+1)로 두면 된다.
- A, B, C, D, a, b, c, d는 인덱스 0, 1, 2, 3, 4, 5, 6, 7 로 구분했다.
- 같은 팀의 말을 업기 위해서, 이동 전에 해당 칸에 같은 팀이 있는지 확인해야 한다.
- 같은 팀이 있다면 해당 말을 팀원으로 묶고, 팀원과 같이 움직인다.
- 다른 팀의 말을 잡기 위해서, 이동 후에 해당 칸에 다른 팀이 있는지 확인해야 한다.
- 다른 팀이 있다면, 해당 말을 처음으로 보낸다.
- 도착하면, 도착한 말을 초기화하고, 같은 팀이 있다면 팀을 해체하고 팀원 말도 초기화한다.
C++ 소스코드
#include <iostream> using namespace std; struct pos { int x, y, team; }; pos user[8]; char piece, yut[5]; const int dx[] = {0, 0, 1, 1}, dy[] = {0, 1, 0, 1}; const char c[] = {'A', 'B', 'C', 'D', 'a', 'b', 'c', 'd'}; char a[32][33] = { "..----..----..----..----..----..", // (0,0) (0,6) (0,12) (0,18) (0,24) (0,30) ".. .. .. .. .. ..", "| \\ / |", "| \\ / |", "| \\ / |", "| .. .. |", // (5,5) (5,25) ".. .. .. ..", // (6,0) (6,30) ".. \\ / ..", "| \\ / |", "| \\ / |" , "| .. .. |", // (10,10) (10,20) "| .. .. |", ".. \\ / ..",// (12,0) (12,30) ".. \\ / ..", "| \\ / |", "| .. |", // (15,15) "| .. |", "| / \\ |", ".. / \\ ..",// (18,0) (18,30) ".. / \\ ..", "| .. .. |", // (20,10) (20,20) "| .. .. |", "| / \\ |", "| / \\ |", ".. / \\ ..",// (24,0) (24,30) ".. .. .. ..", // (25,5) (25,25) "| .. .. |", "| / \\ |", "| / \\ |", "| / \\ |", ".. .. .. .. .. ..", // (30,0) (30,6) (30,12) (30,18) (30,24) (30,30) "..----..----..----..----..----.."}; void print() { // Place pieces on board. for (int i=0; i<8; i++) { int &x = user[i].x, &y = user[i].y; if (x != -1) { a[x][y] = c[i]; } } // Print yut-nori board. for (int i=0; i<32; i++) cout << a[i] << '\n'; cout << '\n'; } void init() { // Initialize pieces. for (int i=0; i<8; i++) { user[i].x = -1; user[i].y = -1; user[i].team = 0; } } bool create() { int u = (piece-'A')%28; int &x = user[u].x, &y = user[u].y; // Create new user. if (x == -1) { x = 30+dx[u%4]; y = 30+dy[u%4]; return true; } else return false; } int action() { // Count yut number. int move = 0; for (int i=0; i<4; i++) { if (yut[i] == 'F') move++; } return move ? move : 5; } void outside(int *x, int *move, int limit, int d) { // Move along the outside edge line. while (*x != limit && *move) { (*x) += d; (*move)--; } } void inside(int *x, int *y, int *move, int limit, int d1, int d2) { // Move along the inside diagonal line. while (*x != limit && *move) { (*x) += d1; (*y) += d2; (*move)--; } } void finish(int *x, int *y, int *team, int *move, int u) { // User finishes the game. *x = -1; *y = -1; *move = 0; // Teammates finish the game. int k = u < 4 ? 0 : 4; for (int i=k; i<k+4; i++) { if ((*team) & (1<<i)) { user[i].x = -1; user[i].y = -1; user[i].team = 0; } } *team = 0; } void ally() { // Find out if the user has teammates. int u = (piece-'A')%28; int x = user[u].x-dx[u%4], y = user[u].y-dy[u%4]; int k = u < 4 ? 0 : 4; for (int i=k; i<k+4; i++) { if (u == i) continue; if (user[u].team & (1<<i)) continue; if (user[i].x != -1) { for (int j=0; j<4; j++) { // Add teammates on the user. if (user[i].x == x+dx[j] && user[i].y == y+dy[j]) { user[u].team |= (1<<i); } } } } } void together(int x, int y, int u, int team) { // Move together with teammates. int k = u < 4 ? 0 : 4; for (int i=k; i<k+4; i++) { if (team & (1<<i)) { user[i].x = x+dx[i%4]; user[i].y = y+dy[i%4]; user[i].team |= (1<<u); } } } void enemy() { // Find out if there are enemies in user's position. int u = (piece-'A')%28; int x = user[u].x, y = user[u].y; int k = u < 4 ? 4 : 0; for (int i=k; i<k+4; i++) { if (user[i].x != -1) { for (int j=0; j<4; j++) { if (user[i].x == x+dx[j] && user[i].y == y+dy[j]) { // The enemies go back to the starting point. user[i].x = -1; user[i].y = -1; user[i].team = 0; } } } } } void solve() { int u = (piece-'A')%28; int &x = user[u].x, &y = user[u].y, &team = user[u].team; int move = action(); bool finished = false; ally(); if (create()) { // First start. x -= 6; move--; } x -= dx[u%4], y -= dy[u%4]; // Move pieces. if (x == 0 && y == 30) { inside(&x, &y, &move, 30, 5, -5); // ↙ } else if (x == 0 && y == 0) { inside(&x, &y, &move, 30, 5, 5); // ↘ } else if (x == 15 && y == 15) { inside(&x, &y, &move, 30, 5, 5); // ↘ if (move) finish(&x, &y, &team, &move, u), finished = true; } else if (x == 30 && y == 30) { if (move) finish(&x, &y, &team, &move, u), finished = true; } else if (x % 6 == 0 || y % 6 == 0) { while (move) { if (y == 30) outside(&x, &move, 0, -6); // ↑ if (x == 0) outside(&y, &move, 0, -6); // ← if (y == 0) outside(&x, &move, 30, 6); // ↓ if (x == 30) { outside(&y, &move, 30, 6); // → if (move) finish(&x, &y, &team, &move, u), finished = true; } } } else { if (x == y) { inside(&x, &y, &move, 30, 5, 5); // ↘ if (move) finish(&x, &y, &team, &move, u), finished = true; } else { inside(&x, &y, &move, 30, 5, -5); // ↙ if (move) outside(&y, &move, 30, 6); } } if (!finished) { if (team) together(x, y, u, team); enemy(); x += dx[u%4], y += dy[u%4]; } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; cin >> n; init(); while (n--) { cin >> piece >> yut; solve(); } print(); return 0; }
Python 3 소스코드
✓ 다시 짜기 정말 귀찮은 문제라서 파이썬 코드는 생략.
참고
- 백준 온라인 저지 : BOJ 15778
반응형