BOJ 3190 뱀
대학교 동기들이 물어봐서 다시 한 번 풀어봤습니다.
문제에서 요구하는데로 그대로 따라하면 해결할 수 있습니다.
저는 map에서 0은 빈 공간, 1은 뱀을 나타내는 값, 2는 사과를 저장합니다.
turnInfo에는 문제에서 주어지는 L의 값들을 구조체로 저장했습니다.
나머지는 주석을 달아놓았습니다.
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 | #include <iostream> #include <queue> #define MAX_SIZE 100 #define mp make_pair using namespace std; typedef pair<int, int> pii; typedef struct { int sec; int dir; }TurnInfo; int n; //보드 크기 int map[MAX_SIZE][MAX_SIZE]; // 사과는 2, 뱀은 1, 맵은 0 TurnInfo turnInfo[MAX_SIZE]; int dx[4] = { -1, 1, 0, 0 }; int dy[4] = { 0, 0, -1, 1 }; //오른쪽 : 위 -> 오, 아래 -> 왼, 오 -> 아, 왼 -> 위 //왼쪽 : 위 -> 왼, 아래 -> 오른, 오 -> 위, 왼 -> 아 //r : 0 -> 3, 1 -> 2, 3 -> 1, 2 -> 0 //l : 0 -> 2, 1 -> 3, 3 -> 0, 2 -> 1 int turn(int now, int next) { if (next == 0) // 왼쪽 { if (now == 0 || now == 1) return (now + 2) % 4; else return 3 - now; } else // 오른쪽 { if (now == 0 || now == 1) return 3 - now; else return (now + 2) % 4; } } bool isDead(pii headPos) { //벽을 박았는지 if (headPos.first < 0 || headPos.second < 0 || headPos.first >= n || headPos.second >= n) { return 1; } //내 몸을 부딪혔는지? else if (map[headPos.first][headPos.second] == 1) { return 1; } //위에 속하지 않으면 살았다. return 0; } int main() { cin >> n; //사과 개수 int k; cin >> k; //사과를 2로 맵에 표시 for (int i = 0; i < k; i++) { int x, y; cin >> x >> y; map[x - 1][y - 1] = 2; } //방향 변환 개수 int l; cin >> l; //방향 변환 x는 시간 c는 방향 for (int i = 0; i < l; i++) { int x; char c; cin >> x >> c; turnInfo[i].sec = x; if (c == 'L') { turnInfo[i].dir = 0; } else { turnInfo[i].dir = 1; } } //위에까지 인풋 queue<pii> snakeTrace; // 뱀 자취 int sec = 0; // 현재 시간은 0 int snakeDir = 3; // 초기 방향 오른쪽 pii headPos;//머리 위치 headPos.first = headPos.second = 0; // 뱀 머리 위치 0, 0으로 //turnInfo 인덱스 int turnInfoIdx = 0; //뱀이 죽지않으면 루프 while (!isDead(headPos)) { //현재시간이 0이 아닌데 map이 0이면 꼬리가 잘려야함 //맵은 0이면 빈공간, 1이면 뱀의 몸, 2이면 사과 //sec != 0 이 조건은 시작점은 무조건 map이 0이기 때문에 시작하자마자 꼬리가 잘릴 순 없음 if (sec != 0 && map[headPos.first][headPos.second] == 0) { map[snakeTrace.front().first][snakeTrace.front().second] = 0;//꼬리의 map을 빈공간으로 만들어줌 즉, 잘라버림 snakeTrace.pop();//내 몸을 보관하고 있는 큐에서 꼬리를 버림 } //머리가 위치한 곳의 맵을 1로만들어줌 map[headPos.first][headPos.second] = 1; snakeTrace.push(headPos);//뱀의 머리를 넣기 //turnInfoIdx가 입력받은 l보다 작아야함 같거나 크다면 방향을 전환할 곳이 없으므로 가던곳으로 가야함 if (turnInfoIdx < l) { if (sec == turnInfo[turnInfoIdx].sec) {//현재시간과 방향전환해야하는 시간이 같으면 snakeDir = turn(snakeDir, turnInfo[turnInfoIdx].dir);//뱀의 방향을 전환해줌 turnInfoIdx++;//턴정보 인덱스 증가 } } //뱀의 머리를 다음 위치로 이동시킴 headPos.first += dx[snakeDir]; headPos.second += dy[snakeDir]; sec++; //시간증가 } cout << sec; return 0; } | cs |
'알고리즘 > 구현' 카테고리의 다른 글
| [2140] 지뢰찾기 (0) | 2017.12.27 |
|---|---|
| [12845] 모두의 마블 (0) | 2017.08.26 |
| [12841] 정보대 등산 (0) | 2017.08.23 |
| [1700] 멀티탭 스케줄링 (0) | 2017.08.01 |
| [1992] 쿼드 트리 (0) | 2017.07.30 |