[삼성 SW 역량 기출] 백준 3190 (C++) 뱀

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

3190번: 뱀

 

중간에 실수를 많이해서 한시간 반-두시간을 붙잡고 있었다. ㅠㅠ

 

1. x를 전역변수로 선언해놓고 go()라는 함수에서 지역변수로 또 사용했다.

2. 좌우로 이동하면 y가 증감하도록 해야하는데 내 머릿속 좌우 == 2차평면위의 x축인 나머지 x를 증감하는 실수를 했다. 

 

 

거의 단순 구현이니 못 풀었다해도 이 글을 읽되, 코드는 최대한 나중에 참고하고 풀어보길 바란다!

 

문제를 다 풀고 난 뒤 다른 사람들이 푼 코드도 보니 구현은 다들 비슷하게 한 것 같다.

나름 재밌었다.

 

 

 

 

 

문제 설명

예제 입력1 해설 - 벽 충돌

0초에서 (0,0)좌표에서 시작한다.

(나는 0,0을 시작 좌표로, 보드의 크기를 (n-1) * (n-1)로 가정하겠다)

1은 사과가 있는 부분, 2는 뱀의 모습이다. 0은 빈칸이다.

2차원 배열 아래는 뱀이 위치한 좌표를 보여준다.

 

1초 후의 상황이다.

 

 

 

해당 테케의 종료 상황은 다음과 같다.

 

내가 아래의 코드에 첨부한 debug함수를 사용하여 직접 보길 추천한다. 틀린 부분을 고치기 쉬울 것이다.

 

 

 

다음과 같이 뱀이 머리를 벽에 꽝! 부딪히며 끝난다.

(2 하나가 사라진 건 내가 작성한 코드에선 벽이 있다면 앞으로 이동하고 종료했기 때문이다.)

 

 

 

 

예제 입력3 해설 - 몸통 충돌

다음 테케3 (예제입력3)을 참고해보자.

 

 

맨 윗줄에 있는 사과를 모두 먹으면 뱀은 다음 위치에 있을 것이다.

 

 

 

주어진 입력을 보면 8, D가 있다.

 

 

8초후 오른쪽으로 고개를 꺾은 뱀은 9초 시점에 이렇게 위치한다.

 

종료 직전엔 이렇게 위치하며,

먼저 뱀의 머리를 앞 칸으로 뻗고, 몸통에 머리가 닿으며 게임이 끝난다.

 

 

 

 

 

 

구현

2차원 배열에 있는 뱀의 위치를 덱에 기록하고,

매 iteration마다 time을 증가하고 뱀의 머리가 몸통에 닿는지 find함수로 체크했다.

 

현재 향하는 방향을 cur_dir 전역 변수에 기록한다.

0,1,2,3 순서대로 동서남북이다.

맨 처음 방향은 동쪽이므로 0으로 초기화한다.

 

보드의 사과가 위치한 곳은 1을 저장하고, 뱀의 방향을 바꿀 커맨드는 큐에 담아 pop()하여 사용한다.

 

go 함수의 파라미터 x, y는 뱀의 머리이다.

뱀의 머리가 보드의 범위를 초과했다면 종료한다.

 

q를 하나씩 pop()하며 커맨드에 맞게 방향을 바꾸고 한 칸씩 머리를 이동했다.

(change_dir, move_one_block함수에서 call by ref를 사용했다)

머리를 이동한 칸에 사과가 없다면 꼬리에 해당하는 deque.back을 pop하면 된다.

 

pair가 있는 find함수의 용법은 다음과 같다.

deque<pair<int, int>>::iterator it;
        for (it = d.begin(); it != d.end(); it++) {
            if (it->first == a && it->second == b) {
                cout << time+1;
                return;
            }
        }

 

그런데 생각해보니 뱀의 위치를 1이 아닌 다른 숫자로 보드에 표시하고

그 숫자에 머리가 위치하면 종료하는 게 더 나은 해법일 것 같다. ㅠㅠㅠㅠ

 

 

728x90

 

---

 

 

 

코드

#include <iostream>
#include <queue>
#include <algorithm>
#include <deque>
using namespace std;
int n;
int cur_dir; // 0=east, 1=west, 2=south, 3=north
char c;
int board[100][100];
queue <pair<int, char> > q;
deque <pair<int, int> > d;

void debug() {
    deque<pair<int, int>>::iterator it;
    for (it = d.begin(); it != d.end(); it++) {
        board[it->first][it->second] = 2;
    }
    
    for (it = d.begin(); it != d.end(); it++) {
        cout << it->first << " " << it->second << '\n';
    }
    cout << '\n';
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << board[i][j];
        }
        cout << '\n';
    }
}

void change_dir(int& dir, char cmd) {
    if (dir == 0) {
        if (cmd == 'D') dir = 2;
        else if (cmd == 'L') dir = 3;
    }
    else if (dir == 1) {
        if (cmd == 'D') dir = 3;
        else if (cmd == 'L') dir = 2;
    }
    else if (dir == 2) {
        if (cmd == 'D') dir = 1;
        else if (cmd == 'L') dir = 0;
    }
    else if (dir == 3) {
        if (cmd == 'D') dir = 0;
        else if (cmd == 'L') dir = 1;
    }
    return;
}

void move_one_block(int &x, int &y, int cur_dir) {
    switch (cur_dir) {
        case 0:
            y++;
            break;
        case 1:
            y--;
            break;
        case 2:
            x++;
            break;
        case 3:
            x--;
            break;
        default:
            break;
    }
    d.push_front({x, y});
    return;
}

void go(int x, int y) {
    int time = 0;
    while (1) {
        if (x < 0 || x >= n || y < 0 || y >= n) {
            cout << time;
            return;
        }
        if (time == q.front().first) {
            change_dir(cur_dir, q.front().second); // call by ref로 cur_dir을 cmd에 따라 바꿈
            q.pop();
        }
        
        move_one_block(x, y, cur_dir);
        
        // push 된 머리와 몸통이 닿았는지 검사해야 함
        int a = d.front().first;
        int b = d.front().second; // 뱀의 머리 좌표
        
        // 머리 좌표를 pop해서 현재 머리 좌표가 deque에 있는지 find
        d.pop_front();
        deque<pair<int, int>>::iterator it;
        for (it = d.begin(); it != d.end(); it++) {
            if (it->first == a && it->second == b) {
                cout << time+1;
                return;
            }
        }
        d.push_front({a, b}); // pop한 머리 좌표는 다시 넣어주기
        
        if (board[x][y] != 1) {
            board[d.back().first][d.back().second] =0;
            d.pop_back();
        }
        board[x][y] = 0; // 먹은 사과는 사라짐
        // debug();
        time++;
    }
    return;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int k, l, x;
    char c;
    cin >> n;
    cin >> k;
    for (int i = 0; i < k; i++) {
        int a, b;
        cin >> a >> b;
        board[a - 1][b - 1] = 1;
    }
    cin >> l;
    for (int i = 0; i < l; i++) {
        cin >> x >> c;
        q.push({ x, c });
    }
    d.push_back({ 0,0 });
    cur_dir = 0;
    go(0, 0);

    return 0;
}

 

 

 

 

사족

마음 먹고 vscode로 작성하려 했는데 코드 자동완성 뜨는 속도가 xcode보다 너무너무 느려서 답답시러웠다.

결국 거의 다 짜놓고 xcode로 돌아와 마음의 평화를 얻음...

xcode 짱~ 엑코는 자동완성도 빠릿빠릿하다고

예쁘고.. 정도 많이 들었고...

남들은 1시간만에 어떻게 푸는 걸까 ㅠㅠ 오류 빨리 찾고 싶어요우