백준[3190] 뱀

문제의 출처는 이곳이다.

 

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

 

필자는 문제를 보고 우선 어떤 자료구조를 사용하여 해결할까? 고민을 조금 하면서, 다음 칸으로 이동할 때, 그 위치를 가지고 있어야한다. 이 후, 이동한 위치에 사과가 없으면 가장 처음에 있던 위치를 제거해야 하기 때문에, 'Queue' 자료구조를 사용하였다.

 

'Deck'을 사용하거나 다른 방법도 존재한다. 자료구조를 택하였으면, 문제에 있는 조건대로 구현하면 된다.

 

구현은, 방향을 저장하고 있는 배열만 관리하여 x,y 위치값들을 각 방향에 따라 이동시킨 후, 사과가 없다면 큐의 원소를 제거하는 방식으로 코드를 작성하였다.

 

아래 코드를 보면 이해할 수 있다. 

*방향을 선택할때, 필자의 스타일대로 작성하였으며, 깔끔한 코드를 위해 for() 반복문을 사용하여 간결하게 할 수 있다.

*처음에 맵에 관한 정보인 arr배열과 방문 여부를 확인하는 visit배열을 따로 설정하여 몇몇 테스트케이스에서 오답을 출력하였다. 방문여부를 arr배열에 함께 저장하여 시뮬레이션을 돌리면 문제없이 해결된다.

 

-소스 코드-

#include<stdlib.h>
#include<iostream>
#include<string.h>
#include<string>
#include<math.h>
#include<algorithm>
#include<stack>
#include<queue>
#include<set>
#include<iterator>
#include<deque>
#include<sstream>
 
using namespace std;
 
int main()
{
    int n, k, arr[110][110] = { 0 }, m,  move1[110] = { 0 }, ans = 0;
    int dir = 0, x = 1, y = 1;
    char move2[110] = { NULL };
    queue<pair<int, int>> q;
 
    cin >> n >> k;
    for (int i = 0; i < k; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        arr[a][b] = 2;
    }
    cin >> m;
    for (int i = 0; i < m; i++) {
        int a;
        char b;
        scanf("%d %c", &a, &b);
        move1[i] = a;
        move2[i] = b;
    }
    //cout << arr[3][28];
    //arr[1][3] = 2;
    q.push({ x,y });
    arr[x][y] = 1;
    m = 0;
    
    while (1) {
        if (ans == move1[m]) {
            if (move2[m] == 'L') {
                if (dir == 0) dir = 3;
                else if (dir == 1) dir = 0;
                else if (dir == 2) dir = 1;
                else if (dir == 3)    dir = 2;
            }
            else {
                if (dir == 0) dir = 1;
                else if (dir == 1)    dir = 2;
                else if (dir == 2)     dir = 3;
                else if (dir == 3)     dir = 0;
            }
            m++;
        }
        //int xx=q.front().first, yy = q.front().second;
        ans++;
        //cout << xx << "  " << yy << endl;
        if (dir == 0) {
            x = x;
            y = y + 1;
            q.push({ x,y });
        }
        else if (dir == 1) {
            x = x + 1;
            y = y;
            q.push({ x,y });
        }
        else if (dir == 2) {
            x = x;
            y = y - 1;
            q.push({ x,y });
        }
        else if (dir == 3) {
            x = x - 1;
            y = y;
            q.push({ x,y });
        }
 
        if (arr[x][y] == 1) break;
        if (x > n || y > n || x < 1 || y < 1) break;
        
        //cout << x << "  " << y << endl;;
 
        if (arr[x][y] != 2) {
            int a = q.front().first;
            int b = q.front().second;
            //cout << a << "  " << b << endl;
            //cout << "delete : " << a << "  " << b << endl;
            q.pop();
            arr[a][b] = 0;
        }
        
        arr[x][y] = 1;
        //q.push({ x,y });
        //cout << ans << " " << dir << " " << x << "  " << y << "______  ";
        //cout << q.size() << "  " << q.front().first << " " << q.front().second << endl;
        //printf("\n");
        //cout << st.size() << "  " << q.size() << endl;
    }
    cout << ans;
    return 0;
}