백준 3190 : 뱀

문제 링크입니다 https://www.acmicpc.net/problem/3190

3190번: 뱀

문제에서 주어진 순서대로 차근차근 구현하였고, map에서 뱀을 8, 사과를 1로 놓고 풀었습니다.

풀이 방법을 순서대로 나열하면 다음과 같습니다. 

 

1. 뱀의 다음 위치를 Queue에 push 합니다.

   (시작 좌표의 오른쪽 칸)

 

2. Queue에서 pop을 한 후, 게임 경과 시간을 늘리고, 현재 칸을 꼬리 정보 벡터에 push 합니다.

3. 현재 칸에 사과가 없다면 꼬리칸을 0으로 만들고 현재 칸을 8로 만듭니다.

   (사과가 있다면 그냥 현재 칸을 8로 만들면 됩니다)

 

4. 입력으로 주어진 방향 전환 정보를 확인하고, 다음 칸의 방향을 결정한 후 다음 칸의 좌표를 결정합니다.

5. 뱀의 다음 칸의 값이 8이거나, 다음 칸이 벽이라면 경과된 시간을 출력하고, 아니라면 다음 위치를 Queue에 push 합니다.

 

 

[소스코드]

 

// [백준] 삼성 SW 역량 테스트 기출 문제 : 뱀(3190)
 
#include<vector>
#include<cstdio>
#include<queue>
using namespace std;
const int MAX = 100 + 10;
 
// 좌표와 방향을 저장하기 위한 구조체
struct p {
    int y, x, d;
};
vector <p> myTail;    // 꼬리의 위치를 저장하기 위한 벡터
 
// 방향 전환 정보 : rotation[sec] = dir 이면 sec초 후에 dir로 전환하십시오
int n, k, a, b, L, s, rotation[MAX * MAX], map[MAX][MAX];
 
const int dy[] = { -1, 0, 1, 0 };
const int dx[] = { 0, -1, 0, 1 };
 
// 좌표와 방향을 인자로 받아서 p type으로 바꿔주는 함수
p make_p(int y, int x, int d) {
    p temp;
    
    temp.y = y, temp.x = x, temp.d = d;
    return temp;
}
 
void bfs(int y, int x) {
    
    int game_time = 0, tail = 0;         // 게임 시간, 꼬리 벡터 인덱스
    queue <p> q;
 
    map[y][x] = 8;                        // 시작 좌표에 뱀이 있다고 표시
    q.push(make_p(y, x + 1, 3));         // 바로 오른쪽 좌표를 큐에 넣고
    myTail.push_back(make_p(y, x, 0));    // 시작 좌표도 꼬리 벡터에 넣습니다
    
    while (!q.empty()) {
 
        p cur = q.front();
        q.pop();
        game_time++;
 
        // 지금 현재 뱀의 위치를 꼬리 벡터에 계속 push 해줍니다
        myTail.push_back(make_p(cur.y, cur.x, 0));
 
        // 현재 칸에 사과가 없다면 꼬리가 있는 칸을 0으로 만들고
        // 꼬리 벡터 인덱스를 증가시킵니다
        if (map[cur.y][cur.x] == 0)
            map[myTail[tail].y][myTail[tail++].x] = 0;
 
        map[cur.y][cur.x] = 8;    // 현재 칸에 뱀을 넣어줍니다
 
        int yy, xx, dd;
 
        // roatation 배열에 방향 전환 정보를 보고 알맞게 방향을 설정합니다
        if (rotation[game_time] == -1) {
            dd = (cur.d + 3) % 4;
        }
        else if (rotation[game_time] == 1) {
            dd = (cur.d + 1) % 4;
        }
        else dd = cur.d;    // 방향 전환 시간이 아니면 그냥 현재 방향
 
        yy = cur.y + dy[dd], xx = cur.x + dx[dd];    // 다음 칸의 좌표 설정
 
        if (map[yy][xx] == 8 || yy <= 0 || yy > n || xx <= 0 || xx > n) {
            break;    // 다음 칸이 벽이거나 다음 칸에 뱀이 있으면
        }
        q.push(make_p(yy, xx, dd));    // 다음 칸을 Queue에 push
    }
    printf("%d", game_time + 1);
}
 
void solve(void) {
 
    scanf("%d%d", &n, &k);
    for (int i = 0; i < k; i++) {
        scanf("%d%d", &a, &b);
        map[a][b] = 1;
    }
    scanf("%d", &L);
    for (int i = 0; i < L; i++) {
        char w;
        scanf("%d %c", &s, &w);
 
        if (w == 'L') rotation[s] = 1;    // s초 후에 왼쪽(1)으로 90도 전환해라
        else rotation[s] = -1;            // s초 후에 오른쪽(-1)으로 90도 전환해라
    }
    bfs(1, 1);    // (1, 1)부터 시작
}
 
int main(void) {
    solve();
    return 0;
}