3190번 : 뱀
https://www.acmicpc.net/problem/3190
문제
'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.
게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.
뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.
- 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
- 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
- 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.
사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.
입력
첫째 줄에 보드의 크기 N이 주어진다. (2 ≤ N ≤ 100) 다음 줄에 사과의 개수 K가 주어진다. (0 ≤ K ≤ 100)
다음 K개의 줄에는 사과의 위치가 주어지는데, 첫 번째 정수는 행, 두 번째 정수는 열 위치를 의미한다. 사과의 위치는 모두 다르며, 맨 위 맨 좌측 (1행 1열) 에는 사과가 없다.
다음 줄에는 뱀의 방향 변환 횟수 L 이 주어진다. (1 ≤ L ≤ 100)
다음 L개의 줄에는 뱀의 방향 변환 정보가 주어지는데, 정수 X와 문자 C로 이루어져 있으며. 게임 시작 시간으로부터 X초가 끝난 뒤에 왼쪽(C가 'L') 또는 오른쪽(C가 'D')로 90도 방향을 회전시킨다는 뜻이다. X는 10,000 이하의 양의 정수이며, 방향 전환 정보는 X가 증가하는 순으로 주어진다.
출력
첫째 줄에 게임이 몇 초에 끝나는지 출력한다.
예제 1
| 입력 | 출력 |
| 6 3 3 4 2 5 5 3 3 3 D 15 L 17 D |
9 |
예제 2
| 입력 | 출력 |
| 10 4 1 2 1 3 1 4 1 5 4 8 D 10 D 11 D 13 L |
21 |
예제 2
| 입력 | 출력 |
| 10 5 1 5 1 3 1 2 1 6 1 7 4 8 D 10 D 11 D 13 L |
13 |
문제 분석
예제 1을 예시로 들어 분석을 하겠다.
우선, 문제를 보고 2차원 배열을 이용해 보드위의 상황을 정리해야겠다 생각했다.
# 보드
1. 외곽 벽을 만들기 위해 (N+2)x(N+2)배열로 초기화를 한다.
2. 모든 칸은 'O'로 초기화 한다.
3. 사과가 있는 칸은 'A'로 표시한다.
4. 뱀의 몸이 있는 곳은 'S'로 표시하며, 첫 시작엔 1행 1열에서 뱀('S')이 '오른쪽 방향'으로 출발한다.
ex)예제 1에서 5초 경과 했을 때, 사과를 하나 먹어 몸이 늘어남
0 0 0 0 0 0
0 0 0 S A 0
0 0 0 S 0 0
0 0 0 0 0 0
0 0 A 0 0 0
0 0 0 0 0 0# 뱀
1. 정해진 방향으로 1초에 한칸 씩 움직인다.
2. 다음 이동할 칸이 빈칸'O'인 경우, 몸 길이를 유지하고 움직인다. 다시 말해, 꼬리칸은 다시 'O'가 돼야 한다.
3. 다음 이동할 칸에 사과('A')가 있는 경우, 몸 길이가 1 늘어난다. 다시 말해 꼬리가 위치한 칸은 그대로 유지하면 된다.
4. 외곽 벽('0행 또는 0열')으로 이동할 경우, 게임을 끝낸다.
5. 다음 이동할 칸이 뱀('S')인 경우, 게임을 끝낸다.
여기서 고민 했던 것은 뱀의 꼬리 위치를 어떻게 알아내야 하냐는 것이었다.
움직일 때, 꼬리 위치의 값을 바꿔야 하기 때문이다. 근데, 몸 꼬리 하니까 생각 나는 것이 있었다.
바로, 큐(queue)다
제일 먼저 생겼던 칸이 꼬리이고, 제일 나중에 생긴 값이 머리라고 생각하면 똑 닮은 것이었다.
그렇다면, 움직일때 마다 이동한 칸의 좌표를 `push()`해주면 자연스럽게 뱀의 몸이 있는 좌표가 꼬리부터 머리까지 순서대로 저장이 된다. 거기다가, `front()`를 쓰면 머리의 위치이고, `back()`을 쓰면 꼬리의 위치도 나온다.
그리고 뱀의 방향의 경우에도 똑같이 큐(queue)로 순서대로 저장해서, 구조체를 이용해 시간('X')와 방향('C')로 방향 구조체를 만들어, 큐에 저장하면, 시간과 방향을 차례대로 불러올 수 있다.
문제 풀이
1. initBoard() : 보드를 생성한다.
void initBoard()
{
scanf("%d", &N); // 보드 크기 입력
board = new char *[N + 2]; // 외곽 벽을 생각해서 2칸씩 여유를 더 준다.
for (int i = 0; i < N + 2; i++)
{
board[i] = new char[N + 2];
for (int j = 0; j < N + 2; j++)
{
board[i][j] = 'O'; // 우선 모두 빈칸'O' 로 초기화
}
}
scanf("%d", &K); // 사과 개수 입력
for (int num = 1; num <= K; num++)
{
int i, j;
scanf("%d %d", &i, &j);
board[i][j] = 'A'; // 사과의 위치에 'A'로 저장
}
board[1][1] = 'S'; // 1행 1열에서 뱀이 출발한다.
snakeBody.push({1, 1}); // 뱀의 출발 위치도 구조체 '뱀몸'에 추가한다.
}
2. initDirection() : 방향 전환 순서를 큐에 저장한다.
void initDirection()
{
int L;
int X;
char D;
scanf("%d", &L);
for (int i = 1; i <= L; i++) {
scanf(" %d %c", &X, &D);
directList.push({ X, D }); // 큐에 시간과 방향 저장
}
}
여기서 다행인 점은, 입력사항에 시간 순서로 방향이 주어진다는 것이다.
만일 시간 순서대로 주어지지 않는다면, 시간 순서대로 정렬을 하는 과정을 추가하면 될 것 같다.
3. moveSnake() : 뱀을 움직이자.
void moveSnake(string direct)
{
moveTime++; // 1초 경과
int head_i = snakeBody.back().i; //현재 머리의 행
int head_j = snakeBody.back().j; //현재 머리의 열
int* move_ij = initMove(direct); // initMove()를 통해 방향에 따른 좌표 이동값 설정
int move_i = move_ij[0], move_j = move_ij[1]; //initMove()로 얻은 이동값을 행과 열에 각각 입력
head_i += move_i; // 움직인 머리의 행
head_j += move_j; // 움직인 머리의 열
if (head_i != 0 && head_j != 0 && head_i != N + 1 && head_j != N + 1 && board[head_i][head_j] != 'S')
{ // 0행 또는 0열 또는 N+1행 또는 N+1열이면 벽에 부딪힌걸고 간주, 그리고 몸에 부딪혀도 안된다.
if (board[head_i][head_j] == 'O') // 사과 안먹음
{
board[head_i][head_j] = 'S'; // 이동한 칸 'S'로 변경
snakeBody.push({ head_i,head_j }); // snakeBody에 push()
int tail_i = snakeBody.front().i; // 꼬리 행 가져오기
int tail_j = snakeBody.front().j; // 꼬리 열 가져오기
board[tail_i][tail_j] = 'O'; // 몸 안늘어났으니 꼬리 좌표 'O'로 변경
snakeBody.pop(); // snakeBody도 pop()으로 변경사항 저장
}
if (board[head_i][head_j] == 'A') //사과 먹음
{
board[head_i][head_j] = 'S';
snakeBody.push({ head_i,head_j }); // 위와 다르게 몸이 늘어났으므로 이하 과정 생략
}
if (!directList.empty()) { // 방향 큐가 비어있을 경우 대비
if (moveTime == directList.front().X)// 방향 차례 시간이 됐는지 확인
{
direct = checkDirect(direct); // checkDirect()를 통해 꺽인 방향이 '위','아래','오른쪽','왼쪽'인지 확인
}
}
moveSnake(direct); // 다음 움직임
}
}함수가 조금 길다.. 나중에 시간이 되면 리팩토링을 해야겠다.
여기서 중요한 것은 뱀의 머리좌표와 꼬리 좌표를 이용하는 것이다.
그리고 움직일 방향을 객관적으로 받아오는 것이다.
문제에선 '왼쪽', '오른쪽'이라고 했는데, 이건 뱀의 입장이고, 제 3자인 우리가 보드판을 봤을땐, '위','아래','오른쪽','왼쪽' 으로 바꿔 줘야한다.
1. initMove() : 움직일 방향에 맞춰 좌표 변화값을 구한다.
int* initMove(string direct)
{
int* move_ij = new int[2]; // 좌표 변화값을 저장할 배열
move_ij[0] = 0;
move_ij[1] = 0;
if (direct == "up") // 위쪽
{
move_ij[0] = -1; // 행 -1
}
if (direct == "down") // 아랫쪽
{
move_ij[0] = 1; // 행 +1
}
if (direct == "left") // 왼쪽
{
move_ij[1] = -1; // 열 -1
}
if (direct == "right") // 오른쪽
{
move_ij[1] = 1; // 열 +1
}
return move_ij;
}움직이는 방향에 따라 좌표 변화값을 구해 반환해주는 함수이다.
이걸 이용한다면, moveSnake()를 위, 아래, 오른쪽, 왼쪽 으로 나눠서 할 필요가 없어지므로 추가했다.
2. chekcDirect() : 방향 전환
string checkDirect(string direct)
{
string nextDirect;
char turnDirect = directList.front().D;
directList.pop();
if (turnDirect == 'L')
{
if (direct == "up")
{
nextDirect = "left";
}
if (direct == "left")
{
nextDirect = "down";
}
if (direct == "down")
{
nextDirect = "right";
}
if (direct == "right")
{
nextDirect = "up";
}
}
if (turnDirect == 'D')
{
if (direct == "up")
{
nextDirect = "right";
}
if (direct == "right")
{
nextDirect = "down";
}
if (direct == "down")
{
nextDirect = "left";
}
if (direct == "left")
{
nextDirect = "up";
}
}
return nextDirect;
}움직이는 방향은 뱀의 머리를 기준으로 '왼쪽'과 '오른쪽'으로 주어진다.
다시 말해, 뱀의 입장의 방향이므로, 이것만으로는 보드의 어느 방향인지 모른다.
그래서 이 함수를 통해, 뱀의 머리가 가리키던 방향('direct')을 기준으로 왼쪽, 오른쪽에 맞는 객관적인 방향으로 변환해준다.
SSAFY 준비한다고 풀었는데, 생각보다 할만하고 재밌던 문제였다.자료구조에 대한 이해가 좀 많이 필요하다는 느낌도 들었고, 문제 분석 능력도 중요한거 같다.
근데 역시, 준비하던 우테코 프리코스랑은 다르게 빠르게 푸는게 중요하다 보니, 리팩토링이 필요한 부분이 좀 보인다..
그래도 우테코 하기 전에 했던 코드들을 보면... 가독성은 많이 나아진거 같다.. ㅋㅋ..
마지막은 전체 코드!
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <string>
#include <string.h>
#include <sstream>
#include <queue>
using namespace std;
int N, K, moveTime = 0;
char** board;
struct Direct
{
int X;
char D;
};
struct Snake
{
int i, j;
};
queue<Direct> directList;
queue<Snake> snakeBody;
void initBoard()
{
scanf("%d", &N);
board = new char* [N + 2];
for (int i = 0; i < N + 2; i++)
{
board[i] = new char[N + 2];
for (int j = 0; j < N + 2; j++)
{
board[i][j] = 'O';
}
}
scanf("%d", &K);
for (int num = 1; num <= K; num++)
{
int i, j;
scanf("%d %d", &i, &j);
board[i][j] = 'A';
}
board[1][1] = 'S';
snakeBody.push({ 1, 1 });
}
void initDirection()
{
int L;
int X;
char D;
scanf("%d", &L);
for (int i = 1; i <= L; i++) {
scanf(" %d %c", &X, &D);
directList.push({ X, D });
}
}
int* initMove(string direct)
{
int* move_ij = new int[2];
move_ij[0] = 0;
move_ij[1] = 0;
if (direct == "up")
{
move_ij[0] = -1;
}
if (direct == "down")
{
move_ij[0] = 1;
}
if (direct == "left")
{
move_ij[1] = -1;
}
if (direct == "right")
{
move_ij[1] = 1;
}
return move_ij;
}
string checkDirect(string direct)
{
string nextDirect;
char turnDirect = directList.front().D;
directList.pop();
if (turnDirect == 'L')
{
if (direct == "up")
{
nextDirect = "left";
}
if (direct == "left")
{
nextDirect = "down";
}
if (direct == "down")
{
nextDirect = "right";
}
if (direct == "right")
{
nextDirect = "up";
}
}
if (turnDirect == 'D')
{
if (direct == "up")
{
nextDirect = "right";
}
if (direct == "right")
{
nextDirect = "down";
}
if (direct == "down")
{
nextDirect = "left";
}
if (direct == "left")
{
nextDirect = "up";
}
}
return nextDirect;
}
void moveSnake(string direct)
{
moveTime++;
int head_i = snakeBody.back().i;
int head_j = snakeBody.back().j;
int* move_ij = initMove(direct);
int move_i = move_ij[0], move_j = move_ij[1];
//머리 이동
head_i += move_i;
head_j += move_j;
if (head_i != 0 && head_j != 0 && head_i != N + 1 && head_j != N + 1 && board[head_i][head_j] != 'S')
{ //벽에 안부딪힐때
if (board[head_i][head_j] == 'O') // 사과 안먹음
{
board[head_i][head_j] = 'S';
snakeBody.push({ head_i,head_j });
int tail_i = snakeBody.front().i;
int tail_j = snakeBody.front().j;
board[tail_i][tail_j] = 'O';
snakeBody.pop();
}
if (board[head_i][head_j] == 'A') //사과 먹음
{
board[head_i][head_j] = 'S';
snakeBody.push({ head_i,head_j });
}
if (!directList.empty()) {
if (moveTime == directList.front().X)
{
direct = checkDirect(direct);
}
}
moveSnake(direct);
}
}
int main()
{
initBoard();
initDirection();
moveSnake("right");
printf("%d", moveTime);
}