[C++] 백준 3190번 뱀

구현 문제.

표현이 애매해서 처음에 이해하기가 어려웠던 문제였던 것 같다.

(예를들어 벽에 부딪히는게 1 또는 마지막 칸을 의미한다고 생각했는데,

그게 아니고 그냥 최대 범위를 넘어가는 게 부딪힌다는 뜻이였다.)

그래서 방향이 위일때 위 벽에, 오른쪽일때 오른쪽 벽에 이런식으로 고려를 해주다 보니 예외처리가 상당히 많아졌었다.

그러나 그냥 DFS처럼 범위만 예외처리 해주면 되는 조건이였다.

테스트 케이스들로 그림을 그려보면서 풀면 풀 수 있는 문제.

 

문제 풀이

맨 처음 뱀은 1, 1의 좌표에서 시작을 하고 방향은 오른쪽(→)이다.

그리고 뱀은 1초마다 이동을 하는데 다음과 같은 조건이 붙는다.

• 이동한 곳에 사과가 있다면 꼬리를 그대로 둔다. (길이가 1 늘어난다.)
• 이동한 곳에 사과가 없다면 몸을 한칸 앞으로 움직인다. 즉, 꼬리가 있던 칸이 빈 칸이 된다. (길이가 그대로다.)
• 벽, 또는 자기자신의 몸과 부딪히면 게임이 종료된다.

그리고 시간이 지날 때마다 방향이 바뀔수가 있다. 시간이 지날때마다 왼쪽 혹은 오른쪽으로 90도 회전을 하게 된다.

따라서 방향은 상, 하, 좌, 우로 이동이 가능하다.

 

조건을 정리하면 이정도가 된다. 따라서 위 조건들을 코드로 구현해서 처리해주면 된다.

 

코드를 살펴보자.

사용한 STL과 변수

먼저, queue STL을 사용해서 자료구조 큐를 사용했다. 큐는 총 두 곳에서 사용된다.

• 뱀이 이동한 곳을 저장해두는 용도
• 방향이 바뀔 시간과 바꾸는 방향을 입력받을 때, 선입 선출을 해 주기 위한 용도

 

그리고 Snake Class를 만들었다.

• headPoint : 뱀의 머리부분을 의미. 즉 내가 지금 보고있는 좌표를 의미하게 된다.
• movePoint : 위에서 설명한 뱀이 이동한 곳을 저장하는 용도. 만일 뱀의 길이가 줄어들어야 할 때, 제일 처음으로 들어왔던 좌표를 수정해주면 된다.
• direction : 현재 방향을 상, 하, 좌, 우를 입력받아서 이동시에 좌표에 더해주게 하는 변수. direction[4] 배열과 함께 사용이 된다.

 

• board 배열 : 게임의 판을 의미한다. 빈 칸은 0, 사과는 1, 뱀의 몸은 2가 되도록 만들었다.
• direcChangeQueue 큐 : 바뀔 방향과 언제 바뀌는지에 대한 초를 입력받는 큐이다. 
• direction 배열 : 각 방향에 대해 이동시에 y, x의 값에 어떤 값을 더해야 하는지 저장하는 배열이다.
• widthHeight : 판의 길이와 너비이다.
• numOfApple : 사과의 개수이다.
• numOfDirectionChange : 방향을 바꾸는 횟수이다.
• timeCnt : 시간이 얼마나 지났는지에 대한 결과값이다.

메인함수 - 1

처음에 Snake Class를 이용해서 snake를 만들어준다. {1, 1}은 시작위치, 0은 오른쪽 방향을 의미한다.

그리고 길이와 너비를 입력받고, 사과의 개수를 입력받은 후 사과의 좌표에는 board 배열에 1을 표기하도록 한다.

후에 방향이 얼마나 바뀌는지에 대해 입력받고, 언제 바뀌는지, 어떤 방향으로 바뀌는지에 대해 입력받고 큐에 저장해준다.

 

메인함수 - 2

현재 뱀의 좌표를 curY, curX 변수로 받는다.

그리고 현재 좌표가 이미 범위를 넘어섰거나(벽에 부딪혔거나),

뱀의 몸 부분이라면 반복문을 탈출하도록 한다.

아니라면 시간을 1초 증가시키고 뱀의 현재 방향을 moveIdx 변수로 받아온다.

뱀의 headPoint가 다음 이동방향을 가리키도록 수정해서 다음 반복문에서 조사하도록 해준다.

그리고 뱀의 현재좌표는 movePoint 큐에 넣어놔서 이동좌표에 하나를 추가시킨다.

 

만일 현재 좌표가 0이라면, 길이를 하나 줄여야 하므로 제일 최근에 입력받은 좌표를 0으로 만들어주고,

현재 좌표는 2로 업데이트 해준다.

 

메인함수 - 3

만일 방향을 바꿀 큐가 비지 않았고, 시간이 방향을 바꿀 시간이 됐다면 방향을 바꿔준다.

L 방향이라면 좌측으로 90도를 가게 되는데, 이 때 내 경우는 우하좌상 순서로 돼있어서,

좌측 방향수정은 -1, 우측 방향 수정은 +1을 해주게 된다.

(위에 direction[4] 배열을 확인해 보면 알 수 있다.)

그리고 -1을 할 때는 0보다 작으면 3이 되게 하고, +1을 할 때는 모듈로 연산을 해서 idx가 벗어나는 일이 없도록 만들어 준다.

 

처음에 조건을 잘못 이해해서 한 번 틀렸다.

조건을 다시 설정해 둔 뒤에는 맞았습니다를 받을 수 있었다.

 

GitHub - kimyunseok/study-record: my study-record

코드는 위에서 확인이 가능하다.