Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- Priority Queue
- Data Structure
- GitHub
- django
- Trie
- aws
- JavaScript
- SQL
- 코딩테스트
- gpdb
- 알고리듬
- 알고리즘
- Linked list
- Bruth Force
- 코테
- 모의SW역량테스트
- spring boot
- Back tracking
- Algorithm
- 구현
- SWEA
- hash table
- CSV
- 시뮬레이션
- programmers
- Vue.js
- boj
- DFS
- Python
- BFS
Archives
- Today
- Total
hotamul의 개발 이야기
[Algorithm][C++] BOJ 3190: 뱀 (Double Linked List) 본문
myt-algorithm-practice/Samsung SW Certi Pro
[Algorithm][C++] BOJ 3190: 뱀 (Double Linked List)
hotamul 2021. 11. 21. 23:35url: https://www.acmicpc.net/problem/3190
3190번: 뱀
'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임
www.acmicpc.net
풀이 핵심
1. 기존에는 stack + queue 로 풀이했다면 이번에는 double linked list를 이용해 풀이해보고자 한다. double linked list를 사용하는 이유는 꼬리를 자르는 경우 (꼬리를 잘라야 하는 경우 꼬리의 이전(post)이 꼬리가 되게 하고 꼬리를 잘라야 한다) 때문에 그렇다.
2. SNAKE 구조체와 make, cut_tail 함수를 다음과 같이 만들어 준다.
struct SNAKE {
int y, x;
SNAKE* next;
SNAKE* post;
};
SNAKE HEAD;
SNAKE TAIL;
SNAKE POOL[MAXN * MAXN];
int pcnt;
void move(int y, int x) {
SNAKE* nd = &POOL[pcnt++];
nd->y = y, nd->x = x;
nd->post = NULL;
if (HEAD.next == NULL) {
HEAD.next = TAIL.next = nd;
}
else {
nd->next = HEAD.next;
HEAD.next->post = nd;
HEAD.next = nd;
}
map[y][x] = 2;
}
void cut_tail() {
SNAKE* tmp = TAIL.next->post;
map[TAIL.next->y][TAIL.next->x] = 0;
tmp->next = NULL;
TAIL.next = tmp;
}
3. 사과가 있다면 move만 해주고 사과가 없다면 move, cut_tail 함수를 실행하도록 loop를 만든다.
코드
#include <cstdio>
#define MAXN 100
#define MAXL 10001
int N, K, L;
int map[MAXN][MAXN];
int dir;
const int dy[] = { 0,1,0,-1 };
const int dx[] = { 1,0,-1,0 };
struct SNAKE {
int y, x;
SNAKE* next;
SNAKE* post;
};
SNAKE HEAD;
SNAKE TAIL;
SNAKE POOL[MAXN * MAXN];
int pcnt;
void move(int y, int x) {
SNAKE* nd = &POOL[pcnt++];
nd->y = y, nd->x = x;
nd->post = NULL;
if (HEAD.next == NULL) {
HEAD.next = TAIL.next = nd;
}
else {
nd->next = HEAD.next;
HEAD.next->post = nd;
HEAD.next = nd;
}
map[y][x] = 2;
}
void cut_tail() {
SNAKE* tmp = TAIL.next->post;
map[TAIL.next->y][TAIL.next->x] = 0;
tmp->next = NULL;
TAIL.next = tmp;
}
int DIR[MAXL];
int solve() {
int time = 0;
move(0, 0);
dir = 0;
while (1) {
++time;
int ny = HEAD.next->y + dy[dir];
int nx = HEAD.next->x + dx[dir];
if (ny < 0 || ny >= N || nx < 0 || nx >= N || \
map[ny][nx] == 2) {
break;
}
if (map[ny][nx] == 0) {
move(ny, nx);
cut_tail();
}
else {
move(ny, nx);
}
if (DIR[time]) {
dir = (dir + DIR[time]) % 4;
}
}
return time;
}
int main() {
int ans;
scanf("%d %d", &N, &K);
for (int i = 0; i < K; i++) {
int y, x;
scanf("%d %d", &y, &x);
--y, --x;
map[y][x] = 1;
}
scanf("%d", &L);
for (int i = 0; i < L; i++) {
int t; char d;
scanf("%d %c", &t, &d);
DIR[t] = (d == 'D' ? +1 : 3);
}
ans = solve();
printf("%d", ans);
return 0;
}
'myt-algorithm-practice > Samsung SW Certi Pro' 카테고리의 다른 글
[Data Structure][C++] Hash Table (0) | 2021.11.22 |
---|---|
[Algorithm][C++] BOJ 1620: 나는야 포켓몬 마스터 이다솜 (Hash Table - Chaining (Single Linked List) (0) | 2021.11.22 |
[Algorithm][C++] BOJ 2606: 바이러스 (head, tail Linked List) (0) | 2021.11.20 |
[Data Structure][C++] Linked List (0) | 2021.11.19 |
[Algorithm][C++] BOJ 1707: 이분 그래프 (0) | 2021.11.19 |