-
[백준] 3190 - 뱀Algorithm 문제 2019. 6. 30. 16:55
https://www.acmicpc.net/problem/3190
간단한 구현 문제. 문제 내에 뱀의 이동, 길이 증가에 대한 알고리즘이 잘 설명되어 있어 그대로 구현하면 된다.
n x n 배열에 사과를 1, 뱀을 2로 표현하고 뱀의 몸을 queue에 저장하여 먼저 지나간 위치의 값을 0으로 초기화하며 이동한다.
<C++ 코드>
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include <cstdio>#include <vector>#include <queue>using namespace std;int arr[101][101];int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};int main(){int n, k, l;vector<pair<int, char> > v;queue<pair<int, int> > snake;scanf("%d %d", &n, &k);for(int i=0; i<k; i++){int a, b;scanf("%d %d", &a, &b);arr[a][b] = 1;}scanf("%d", &l);for(int i=0; i<l; i++){int x;char c;scanf("%d %c", &x, &c);v.push_back(make_pair(x, c));}int re=0, cmd=0, dir=0;pair<int, int> head = make_pair(1, 1);snake.push(head);arr[head.second][head.first] = 2;while(true){int x = head.first, y = head.second;// 전진 및 충돌 확인x += dx[dir];y += dy[dir];head = make_pair(x, y);snake.push(head);if(x < 1 || x > n || y < 1 || y > n || arr[y][x]==2){break;}// 사과 확인 및 축소if(!arr[y][x]==1){int rx = snake.front().first, ry = snake.front().second;arr[ry][rx] = 0;snake.pop();}arr[y][x] = 2;// 시간 증가 및 방향 수정re++;if(cmd < v.size() && re == v[cmd].first){if(v[cmd].second == 'D'){dir++;}else if(v[cmd].second == 'L'){dir--;}dir = (dir + 4) % 4;cmd++;}}printf("%d", re+1);return 0;}cs 'Algorithm 문제' 카테고리의 다른 글
[백준] 15954 - 인형들 (1) 2019.07.02 [백준] 1562 - 계단 수 (0) 2019.06.30 [백준] 17140 - 이차원 배열과 연산 (0) 2019.06.29 [백준] 1238 - 파티 (0) 2019.06.28 [백준] 13306 - 트리 (0) 2019.06.27