[백준/C++] 3190번 뱀

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

3190번: 뱀

 

문제 분석

정사각형 보드 위에서 뱀이 움직이는데, 자신의 몸에 닿거나 벽에 닿으면 끝나는 게임이다.

•   뱀은 사과를 먹을 때만 몸이 길어지고, 그 외에는 항상 동일하다.
  • 사과를 먹으면 꼬리는 제자리에 남아있고, 머리만 한 칸 이동한다.
  • 사과를 먹지 않으면 머리도 한 칸, 꼬리도 한 칸 이동한다.
    주의할 점은, 꼬리는 머리가 이동했던 경로를 따라서 이동해야 한다는 점이다.
  • 또한 뱀은 방향을 전환할 수 있다.
  • 뱀이 한번 이동을 하면 1초가 흐른다.

코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int N, K, L;
int board[102][102] = { 0 };
queue<pair<int, char>> dirQ; //방향 변환 정보를 담는 큐
queue<pair<int, int>> historyQ; //머리가 움직였던 방향을 기록해두는 큐
deque<pair<int, int>> dq; //현재 머리와 꼬리의 위치를 기록하는 큐

int dx[4] = { 0, 1, 0, -1 }; //동, 남, 서, 북 (오른쪽으로 회전)
int dy[4] = { 1, 0, -1, 0 };

void solveProblem() {
	dq.push_front({ 1, 1 }); //꼼장어 머리는 1, 1에서 시작
	dq.push_back({ 1, 1 });  //꼼장어 꼬리도 1, 1에서 시작
	int timer = 0; //시간은 0초부터
	int xDir = 0; //방향은 오른쪽(동) 부터
	int yDir = 0;

	while (true) {
		int fx = dq.front().first;
		int fy = dq.front().second;
		int nfx = fx + dx[xDir];
		int nfy = fy + dy[yDir];
		historyQ.push({ xDir, yDir }); //매 초마다 기록해야 함

		if (board[nfx][nfy] == 2) { //진행 방향에 사과가 있는지 확인
			dq.pop_front();
			dq.push_front({ nfx, nfy }); //머리만 이동
			board[nfx][nfy] = 1; //먹은 사과는 치우고 꼼장어 몸으로 대체
		}
		else if (board[nfx][nfy] == 1) { //진행 방향에 벽 또는 내 몸이 있는지 확인
			timer++; //이동은 하고 끝나야 하니까
			break;
		}
		else { //진행 방향에 아무것도 없을 경우
			// 머리는 현재 진행방향에 맞춰서 이동
			dq.pop_front();
			dq.push_front({ nfx, nfy });
			board[nfx][nfy] = 1;

			// 꼬리는 머리가 이동했던 방향을 따라서 이동
			int bx = dq.back().first;
			int by = dq.back().second;
			int nbx = bx + dx[historyQ.front().first];
			int nby = by + dy[historyQ.front().second];
			dq.pop_back();
			dq.push_back({nbx, nby});
			historyQ.pop();
			board[bx][by] = 0; //더이상 꼼장어 몸이 없으니까 0
		}

		timer++;
		// X초가 끝난 뒤에 방향 정보 변환
		if (!dirQ.empty()) {
			if (timer == dirQ.front().first) {
				if (dirQ.front().second == 'D') {
					xDir = (xDir + 1) % 4; //동->남->서->북->동
					yDir = (yDir + 1) % 4;
				}
				else if (dirQ.front().second == 'L') {
					xDir = (xDir - 1) % 4; //동->북->서->남->동
					yDir = (yDir - 1) % 4;

					if (xDir == -1) xDir = 3;
					if (yDir == -1) yDir = 3;
				}
				dirQ.pop();
			}
		}
	}

	cout << timer;
}

void getInput() {
	cin >> N >> K;
	for (int i = 0; i <= N + 1; i++) { //벽 설정
		board[0][i] = 1;
		board[i][0] = 1;
		board[N + 1][i] = 1;
		board[i][N + 1] = 1;
	}
	board[1][1] = 1; //꼼장어 초기 위치
	for (int i = 0; i < K; i++) { //사과 설정
		int row, column;
		cin >> row >> column;
		board[row][column] = 2;
	}

	cin >> L;
	for (int i = 0; i < L; i++) { //방향 변환 정보 기록
		int time;
		char dir;
		cin >> time >> dir;
		dirQ.push({ time, dir });
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	getInput();
	solveProblem();

	return 0;
}

문제 풀이

2차원 배열을 이용한 구현 문제였다.
먼저 기본적으로 필요한 것들은,

• 보드 정보를 담는 배열(board[102][102])
• 보드에서 움직이기 위한 방향 벡터(dx, dy)
  • 인덱스가 증가할 때마다 오른쪽으로 방향 전환(동->남->서->북)
• 방향 변환 정보를 담는 큐(dirQ)
• 현재 뱀의 머리 위치, 꼬리 위치를 저장하기 위한 덱(dq)
  • dq.front() = 머리의 위치
  • dq.back() = 꼬리의 위치

여기에 더해서 꼬리는 머리가 갔던 방향을 따라가야 하기 때문에, 머리가 움직였던 방향 또한 기록해 두어야 한다.

• 머리가 움직였던 방향을 저장하기 위한 큐(historyQ)
  • 매 초마다 기록해야 한다!

뱀이 한 번 움직이면 시간이 1초 흐른다.

• 몇 초가 지났는지 기록하기 위한 변수(timer)

이렇게 변수들이 준비 되면,

1. 먼저 입력을 받으면서 board를 초기화 한다.
   • 벽의 위치는 1로 기록하고, 사과의 위치는 2로 기록한다.
   • 첫 뱀의 위치는 (1, 1)이므로 이곳도 1로 기록한다.
2. 방향 변환 정보를 입력 받아서 dirQ에 저장한다.
3. 맨 처음에 뱀은 오른쪽으로 움직이기 때문에, dx, dy 배열을 이용하기 위한 인덱스 정보를 담는 변수 xDir, yDir는 모두 0으로 시작한다.
4. 뱀의 머리가 이동할 좌표를 nfx, nfy에 저장한다. (next front x, next front y라는 뜻)

   5-1. 머리가 이동할 방향에 사과가 있다면(board[nfx][nfy] == 2), 꼬리는 제자리에서 기다리고 머리만 해당 위치로 이동            하고, 해당 좌표에 몸이 있다는 의미로 1을 기록한다.

  5-2. 머리가 이동할 방향에 벽이나 자신의 몸이 있다면 timer를 1 증가하고 while loop을 탈출한다.

  5-3. 진행 방향에 아무 것도 없다면 머리는 해당 좌표로 이동하고,

• dq.pop_front(): 기존에 있던 머리 정보를 지우고
• dq.push_front({ nfx, nfy }): 새로운 위치를 저장하고
• board[nfx][nfy] = 1: 보드에 뱀의 몸이 있다는 것을 알린다.

        꼬리는 머리가 이동했던 방향으로 이동한다.

• dq.pop_back(): 기존에 있던 꼬리 정보를 지우고
• dq.push_back({ nbx, nby }): 새로운 위치를 저장하고
• board[nbx][nby] = 1: 보드에 뱀의 몸이 있다는 것을 알린다.

  6. 뱀이 이동을 마치면 timer를 1 증가한다.

  7. X초가 지나서 방향을 바꿔야 한다면 바꾼다.

• dirQ.front().first: X초인가
• dirQ.front().second: 방향을 오른쪽(D)으로 변환하는가, 왼쪽(L)으로 변환하는가
• 방향 변환을 마쳤으면 dirQ.pop()을 꼭 해준다.

위 과정을 반복하면 된다.

이런 구현 문제를 풀 때에는

• 방향 벡터를 활용한다면 각 인덱스가 내가 의도한 방향을 뜻하는지 잘 확인하고,
• 초기값을 잘 확인하고,
• 자료 구조를 사용한다면 뒷처리를 잘 했는지 확인하고,
• 항상 오타를 확인하자.

내가 이번 문제를 풀면서 틀렸던 이유들이었다..

(참고) -1 % 4 = -1