BOJ 3190 : 뱀 - C++

김정욱·2021년 3월 30일
0

Algorithm - 문제

목록 보기
189/249
post-custom-banner

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <deque>
#define ll long long
using namespace std;
int N,K,L;
char board[120][120];
vector<pair<int,char>> info;
deque<pair<int,int>> snake;
int dx[4] = {0, 1, 0, -1}; // 상 우 하 좌 (dir증가 = 오른쪽 회전) (dir감소 = 왼쪽 회전)
int dy[4] = {-1, 0, 1, 0};
int DIR = 1;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    cin >> K;
    for(int i=0;i<N;i++)
        fill(board[i], board[i]+N, '.');
    for(int i=0;i<K;i++)
    {
        int a,b;
        cin >> a >> b;
        board[a-1][b-1] = 'A';
    }
    cin >> L;
    for(int i=0;i<L;i++)
    {
        int a;
        char c;
        cin >> a >> c;
        info.push_back({a,c});
    }
    snake.push_back({0,0});
    board[0][0] = 's';
    int idx=0, time=0;
    while(true)
    {
        /* 방향 전환 */
        if((idx < info.size()) and (info[idx].first == time)){
            if(info[idx].second == 'L'){
                DIR--;
                if(DIR < 0) DIR += 4;
            }else{
                DIR++;
                if(DIR > 3) DIR -= 4;
            }
            idx++;
        }
        ++time;
        /* 뱀의 머리 옮기기 */
        auto cur = snake[0];
        int ny = cur.first + dy[DIR];
        int nx = cur.second + dx[DIR];
        if(nx<0 or ny<0 or nx>=N or ny>=N){
            // 벽에 부딛힘 ==> 종료
            goto stop;
            break;
        }
        if(board[ny][nx] == 's'){
            // 자기 몸에 부딛힘 ==> 종료
            goto stop;
            break;
        }
        pair<int,int> pre = cur;
        bool apple = false;
        // 사과 발견하면 머리만 늘어나고, 나머지는 그대로
        if(board[ny][nx] == 'A'){
            board[ny][nx] = 's';
            snake.push_front({ny, nx});
            apple = true;
        }else{
            board[ny][nx] = 's';
            board[cur.first][cur.second] = '.';
            snake[0] = {ny, nx};
        }
        /* 몸통 이동 ==> 사과 먹으면 움직이면 X */
        if(!apple)
        {
            for(int size=1;size<snake.size();size++)
            {
                auto tmp = snake[size];
                board[pre.first][pre.second] = 's';
                board[tmp.first][tmp.second] = '.';
                snake[size] = pre;
                pre = tmp;
            }
        }
    }
    stop:;
    cout << time;
    return 0;
}
  • 로직
    • board[][]판에 사과의 위치'A'로 표시 / 나머지'.'
    • time변수를 늘려가면서 진행하며, DIR변수를 사용해서 방향컨트롤
      (상 우 하 좌 순서로 배치한 뒤 오른쪽 회전 ==>dir증가 / 왼쪽 회전 ==> dir감소)
    • DIR 방향으로 이동한 점이거나 자신의 몸이면 바로 종료!
    • 가장 앞 머리를 옮기는데 사과를 먹으면 몸통은 그대로 두어야 한다!
      : 머리늘어나고 나머지 몸통동일하기 때문
    • 사과를 먹지 않았을 경우 나머지 앞 좌표따라가도록 구현
profile
Developer & PhotoGrapher
post-custom-banner

0개의 댓글