[백준] 3190번 뱀

문제 정의

매초마다 이동하는 뱀을 계산하는 문제이다. 이동한 칸에 사과가 있을 경우에는 한칸 몸을 늘리고, 아닐 경우는 늘어나지 않고 주어진 초마다 주어진 방향으로 이동해서 벽 또는 자기자신의 몸과 부딫힐 때까지 이동한다.

문제 출처 : 백준 온라인 저지(https://www.acmicpc.net/problem/3190)

문제 풀이

문제를 읽자마자 난해하고 어렵다고 생각했다. 뱀은 1초마다 이동을 하고 주어진 초가 되면 방향을 바꿔야 한다. 뱀의 길이를 저장하기 위한 변수가 필요하다. 오른쪽으로 향하는 함수와 왼쪽으로 향하는 함수를 통해서 초마다 이동시키면서 문제를 풀면될 것 같다. 문제가 충격적이다. 설명이 너무 부족하게 되어있다. 방향은 오른쪽과 왼쪽으로 주어져서 한 행안에 머무는건가 생각했는데, 진행방향에서 오른쪽, 왼쪽으로 가는 거라서 모든 방향을 돌 수 있다는 말이었다. 조건에 보면 자기 몸과 부딪힐경우에도 게임이 멈춰지기때문에 지나가는 곳들을 체크해주고 꼬리가 길어질 경우에도 큐로 체크해줘야겠다. 

이 문제도 6일만에 다시 푼다. 매 초마다 뱀이 이동하므로, 이동하는 방향으로 한칸씩 간다. 방향을 변경해야하는 초는 저장을 해뒀다가 그 초에 이동한 후에 방향을 바꿔서 다음 방향으로 이동하도록 한다. 뱀이 이동한 칸들을 큐에 넣어서 만약 사과가 있다면 큐에서 pop을 하지 않고 사과가 없다면 pop을 통해서 뱀의 꼬리를 이동시켜줘야한다.

코드

#include<iostream>

#include<deque>

using namespace std;

int idx[4]={0, 1,0,-1};

int idy[4]={1, 0, -1, 0};

int N;

int map[101][101];

int visited[101][101];

pair<int, char>change[101];

deque<pair<int, int>> q;

int dir; //현재 방향

int main()

{

int K, L;

int a, b;

char c;

int i, j;

int sec=0; //초정보

int x, y;

int tmpx, tmpy;

pair<int, int> tmp;

scanf("%d", &N);

for(i=0; i<N; i++)

for(j=0; j<N; j++)

map[i][j]=0;

scanf("%d", &K);

for(i=0; i<K; i++){

scanf("%d %d", &a, &b);

map[a-1][b-1]=1; //사과위치, 0부터 index사용하면서 [a][b]로 해둬서 틀렸었다.

}

scanf("%d", &L);

for(i=0; i<L; i++)

{

scanf("%d %c", &a, &c);

change[i].first = a;

change[i].second = c; //바꿀 방향과 초 정보

}

dir = 0; //처음 방향은 오른쪽

x = 0; 

y = 0;

q.push_back(make_pair(x, y));

a=0;

while(q.size() > 0)

{

sec++;  //1초가 지났음 

tmp = q.back(); //젤 마지막에 들어갔던거 나옴

x = tmp.first+idx[dir];

y = tmp.second+idy[dir];

if(visited[x][y] == 1 || 

x < 0 || x >=N ||

y < 0 || y >=N)

break; //벽을 박아서 종료

q.push_back(make_pair(x, y));

visited[x][y]=1;

if(map[x][y] == 1){

map[x][y]=0;

}

else{

tmp = q.front();

visited[tmp.first][tmp.second] = 0;

q.pop_front();

}

if(a < L && sec == change[a].first) //방향바꿔야하면

{

if(change[a++].second == 'D')

dir = (dir+1+4)%4;

else

dir = (dir-1+4)%4;

}

}

printf("%d\n", sec);

}