이코테, 백준 - 3190 뱀

문제

https://www.acmicpc.net/problem/3190

3190번: 뱀

사과를 먹으면 몸이 길어지는 뱀을 이동시키면서 자신의 몸에 닿거나 벽에 닿으면 종료되는 게임의 끝나는 시간을 구하는 문제였다.

 

문제 풀이

뱀의 머리가 먼저 이동하고 꼬리와 닿는지 확인 후에 꼬리를 이동해야 했고, 범위 지정을 N보다 클 때만 break하도록 했는데 이부분을 나중에 깨달아서 시간이 조금 걸렸다.

 

전체 map이 있고, 사과가 있다면 2, 뱀이 있으면 1, 아무것도 없으면 0으로 지정했다. 방향은 dx와 dy로 시계 방향으로 저장해서 왼쪽, 오른쪽 방향으로 90도 회전 시 index를 +- 1씩 해주면 간단하게 해결할 수 있도록 했다. 뱀의 꼬리를 저장하는 queue를 만들어서 뱀이 나아갈 때 꼬리의 위치를 바꿔줄 수 있었다. (map을 1에서 0으로 바꾸기)

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <queue>

using namespace std;

int N, K, L;
int map[101][101]; //사과 있으면 2, 뱀 있으면 1, 아무것도 없으면 0
int direction[101][2]; //뱀 방향 (시간, 방향) 왼쪽 0, 오른쪽 1
// → ↓ ← ↑ 방향
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int nowDir = 0; //처음에 오른쪽 방향부터 시작
int nowTime = 0; //현재 시간

queue<pair<int,int>> snakeQueue; //뱀 꼬리 위치 저장하는 queue

int main() {
    int i, j;
    int x=1, y=1; //뱀의 현재 위치
    int di=0; //direction index

    scanf("%d", &N);
    //사과 위치 입력받기 -> map에 2로 저장하기
    scanf("%d", &K);    
    for (i = 0; i < K; i++) { 
        int a, b;
        scanf("%d %d", &a,&b);
        map[b][a] = 2;
    }
    //뱀 방향 입력받기
    scanf("%d", &L);
    for (i = 0; i < L; i++) {
        char dir;
        scanf("%d %c", &direction[i][0], &dir);
        if (dir == 'L') direction[i][1] = 0;
        else direction[i][1] = 1;
    }    

    //뱀 이동
    snakeQueue.push(make_pair(1, 1));

    while (1) {

        nowTime++;

        //이동
        x = x + dx[nowDir];
        y = y + dy[nowDir];
        snakeQueue.push(make_pair(x, y));

        //사과 확인
        if (map[x][y] == 2) { //사과 있음
            map[x][y] = 1;
        }
        else { //사과 없음
            if (map[x][y] == 1) { //머리, 꼬리 닿음
                break;
            }
            else {
                map[x][y] = 1;
            }
            map[snakeQueue.front().first][snakeQueue.front().second] = 0;
            snakeQueue.pop();
        }

        //회전 여부 체크
        if (nowTime == direction[di][0] && di < L) { //회전해주기
            if (direction[di][1] == 0) { //왼쪽 회전
                nowDir--;
                if (nowDir == -1) nowDir = 3;
            }
            else { //오른쪽 회전
                nowDir++;
                if (nowDir == 4) nowDir = 0;
            }
            di++;
        }

        //map 벗어나는지 확인
        if (x > N || x < 1 || y > N || y < 1) {
            break;
        }
    }

    printf("%d", nowTime);

    return 0;
}

/*
6 
3 
3 4 
2 5 
5 3 
3 
3 D 
15 L 
17 D

10
4
1 2
1 3
1 4
1 5
4
8 D
10 D
11 D
13 L

10
5
1 5
1 3
1 2
1 6
1 7
4
8 D
10 D
11 D
13 L

*/