[BOJ] #3190 뱀

시간 제한	메모리 제한	정답 비율
1 초	128 MB	31.052%

 

3190번: 뱀

 

테스트케이스

testcase 1

20
13
6 15
7 18
20 14
14 13
11 9
7 10
3 18
10 10
13 13
13 5
6 9
10 4
4 3
19
17 D
36 D
41 D
54 D
56 L
57 L
63 L
68 L
72 L
73 L
76 D
79 D
82 D
85 D
87 D
93 L
105 D
110 D
114 D

출력 : 90

testcase 2

5
2
2 5
2 4
6
4 D
5 D
6 D
7 D
8 D
9 D

출력 : 14

 

시행착오

testcase 1에 해당하는 그림

분홍색 형광펜 = 사과

테스트케이스를 질문검색에서 얻어서 그려보는데 어쩐지 계속 85가 나와서 뭐지... 하니까 '56 L' 이 누락됐었다 ㄱ- 제대로 다시 시작하니 왜 90초가 나오는지 알 수 있었다.

틀렸던 이유와 해결방법

1. 이전에 몇 번 틀렸었는데 그 이유는 뱀은 자기자신의 '몸'과 부딪히면 게임이 끝나게 되는데, 나는 '꼬리' 위치만 저장하여 몸과 부딪혔을 때를 무시하고 계속 게임을 진행했기 때문에 틀렸다.

이를 해결하기 위하여 꼬리의 위치는 계속 유지하되, 뱀이 지나가는 부분을 arr[i][j] 라고 한다면 arr[i][j]=2 로 바꾸어 뱀인지 아닌지를 판단하게 하였다. 뱀의 머리가 사과를 먹지 않아 꼬리를 한 칸 당기게 될 때는, 현재 꼬리 위치에 해당하는 arr[tail.first][tail.second]=0 으로 바꾸고 꼬리의 방향대로 tail을 갱신한다.

2. 변수의 의미를 헷갈렸다.

내가 코드를 짜면서도 로직을 제대로 생각하지 않고 먼저 코드를 작성하다보니, 코드수정 시 실수를 하게 되어 변수에 대한 혼란이 와서 틀리지 않아도 되는 부분을 틀렸다. 앞으로는 제대로 노트에 필기도 하고 생을 충분히하고 코드를 짜야겠다.

 

메모리	시간
1160 KB	0 ms

#include <cstdio>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
int arr[105][105];
int n, K, L, i, idx, tail_idx, dir, tail_dir; //idx 는 turn 의 인덱스 번호, dir 은 머리 방향, tail_dir은 꼬리 방향
int dx[] = { 0, 1, 0, -1 };
int dy[] = { 1, 0, -1, 0 };
pair<int, char> turn[105];
pair<int, int> tail;
// 사과는 1, 뱀은 2, 아무것도 없으면 0
int main(){    
    scanf("%d %d", &n, &K);
    for (int i = 0, a, b; i < K; i++) {
        scanf("%d %d", &a, &b);
        arr[a][b] = 1; // 사과
    }
    scanf("%d", &L);
    int X; char C;
    for (int i = 0; i < L; i++) {
        scanf("%d %c", &X, &C);
        turn[i] = { X, C };
    }
    int r = 1, c = 1, sec = 0, cnt = 0;
    arr[1][1] = 2;
    tail = { 1,1 };
    while (r >= 1 && r <= n && c >= 1 && c <= n) {
        int tf = turn[idx].first;    char ts = turn[idx].second;
        
        r = r + dx[dir]; c = c + dy[dir];
        sec++;
        if (arr[r][c] == 2) {
            break;
        }
        if (!arr[r][c]) { // 꼬리가 위치한 칸을 당겨준다.
            cnt++;
            arr[tail.first][tail.second] = 0;
            tail.first = tail.first + dx[tail_dir]; tail.second = tail.second + dy[tail_dir];
        }
        if (sec == tf) { // 머리 방향전환
            dir = ts == 'L' ? (dir + 3) % 4 : (dir + 1) % 4;
            idx++;
        }
        if (cnt == turn[tail_idx].first) { // 꼬리 방향전환
            tail_dir = turn[tail_idx].second == 'L' ? (tail_dir + 3) % 4 : (tail_dir + 1) % 4;
            tail_idx++;
        }        
        arr[r][c] = 2;
    }
    printf("%d", sec);
    return 0;
}