백준 3190 c++ "뱀" -PlusUltraCode-

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

 

[필자 사고]

이 문제는 큰 틀에서 보면 BFS 탐색 문제이다.

 

다만 이 문제만의 특별한 점은 아래와 같다.

1. 이동하는 뱀

2. 사과를 먹은 후 뱀의 상태

3. 뱀의 이동방향

4. 벽에 부디치거나 몸통에 부디치면 종료

 

총 4개로 나눌 수 있다.

 

필자는 첫 번째 이동하는 뱀과 사과를 먹은 후 뱀의 상태에서 많은 어려움이 있었다.

고민의 고민한 결과 큐를 이용하여 뱀의 이동과정을 기록하였다.

 

다른 분들의 코드를 참고해보면 덱을 이용하신 분들도 있었다. 같은 원리이기 때문에 설명은 생략한다.

아래는 소스코드 해설이다.

 

함수 설명

1. configGoTo()
   • 현재 시간에 따라 방향을 변경합니다. path 맵에서 nowTime에 해당하는 방향 변환이 있을 경우, 이를 적용하여 goTo 값을 업데이트합니다.
   • "D"는 오른쪽으로 90도 회전(방향 인덱스를 3 증가시킴), "L"은 왼쪽으로 90도 회전(방향 인덱스를 1 증가시킴)합니다.
   • 방향을 업데이트한 후 % 4 연산을 통해 인덱스를 0~3 범위로 유지합니다.
2. Input()
   • 게임의 초기 설정을 입력받는 함수입니다.
   • cin >> N >> K: 게임판의 크기 N과 사과의 개수 K를 입력받습니다.
   • arr와 snail 벡터를 각각 NxN 크기로 초기화하고, 모든 요소를 -1로 설정합니다.
   • 반복문을 통해 K개의 사과의 위치를 입력받아 arr에서 해당 위치를 2로 표시합니다.
   • 방향 전환 정보를 L개 입력받아 path 맵에 저장합니다. 각 방향 전환 정보는 (시간, 방향) 쌍입니다.
3. isInside(int sero, int garo)
   • 주어진 좌표 (sero, garo)가 게임판의 유효한 범위 내에 있는지를 확인합니다.
   • 조건문을 사용하여 sero와 garo가 0 이상이고 N 미만인지 검사합니다. 유효하면 true, 아니면 false를 반환합니다.
4. Print()
   • 현재 게임판의 상태를 콘솔에 출력하는 함수입니다.
   • 2중 반복문을 통해 snail 벡터의 각 요소를 확인하고, -1인 경우 "0", 1인 경우 "1"로 출력하여 뱀의 위치를 시각적으로 표시합니다.
   • 각 행마다 개행 문자를 출력하여 격자 형태로 게임판을 표시합니다.
5. BFS(int sero, int garo)
   • BFS를 이용하여 뱀의 이동 로직을 구현하는 함수입니다.
   • 시작 위치 (sero, garo)에서 BFS를 시작합니다.
   • 큐 myQueue에 현재 위치를 추가하고, snail 벡터에서 해당 위치를 1로 설정하여 뱀의 몸통을 표시합니다.
   • while 루프를 사용하여 큐가 비어있지 않을 때까지 반복합니다.
     • 현재 위치에서 방향을 업데이트하고, 다음 위치를 계산합니다.
     • isInside() 함수를 사용해 다음 위치가 게임판 내에 있는지 확인하고, 뱀의 몸통에 닿았는지 체크합니다.
     • 벽에 부딪히거나 뱀의 몸통에 부딪히면 게임이 종료되고, 현재 시간을 증가시킵니다.
     • 사과가 있는 경우:
       • myQueue에 다음 위치를 추가하고, snail에서 해당 위치를 1로 설정합니다.
       • 사과를 먹었으므로 arr에서 해당 위치를 0으로 설정하여 사과를 제거합니다.
     • 사과가 없는 경우:
       • 다음 위치를 큐에 추가하고, snail에서 해당 위치를 1로 설정합니다.
       • tail에서 꼬리 위치를 제거하고, 그 위치를 -1로 설정하여 뱀의 몸통에서 꼬리를 제거합니다.
     • 매 반복마다 nowTime을 1 증가시킵니다.
6. GameStart()
   • 게임을 시작하는 함수입니다.
   • BFS(0, 0)을 호출하여 (0, 0)에서 게임을 시작합니다.
   • 최종 경과 시간 nowTime을 출력하여 게임이 종료된 시점을 표시합니다.

 

 

[소스 코드]

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <string.h>
#include <algorithm>
#include <map>

using namespace std;

typedef pair<int, string> Node;
typedef pair<int, int> qNode;

int dy[4] = { 0,-1,0,1 };
int dx[4] = { 1,0,-1,0 };

bool cmp(Node a, Node b) {
	return a.first < b.first;
}

vector<vector<int>> arr;
vector<vector<int>> snail; //뱀이 없으면 -1 있으면 1
queue<qNode> tail;
map<int, string> path;
int N, K, L;
int goTo = 0;
int nowTime = 0;

void configGoTo() {
	if (path.find(nowTime) != path.end()) {
		auto it = path.find(nowTime);
		string str = it->second;
		if (str == "D") {
			goTo = (goTo + 3) % 4;
		}
		else if (str == "L") {
			goTo = (goTo + 1) % 4;
		}
	}
}

void Input() {
	cin >> N >> K;
	arr.resize(N);
	snail.resize(N);
	for (int i = 0; i < N; i++) {
		arr[i].resize(N,-1);
		snail[i].resize(N, -1);
	}
	for (int i = 0; i < K; i++) {
		int sero, garo;
		cin >> sero >> garo;
		arr[sero-1][garo-1] = 2;//사과 있음
	}

	cin >> L;
	for (int i = 0; i < L; i++) {
		int num;
		string str;
		cin >> num >> str;
		path.insert({ num,str });
	}

}

bool isInside(int sero, int garo) {
	if (sero >= 0 && sero < N && garo >= 0 && garo < N)return true;
	return false;
}

void Print() {
	cout << "********* NowTime : " << nowTime << " **********" << '\n';
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < N; k++) {
			if (snail[i][k] == -1) {
				cout << "0";
			}
			else if(snail[i][k]==1) {
				cout << "1";
			}
		}
		cout << '\n';
	}
}

void BFS(int sero, int garo) {
	queue<qNode> myQueue;
	myQueue.push({ sero,garo });
	snail[sero][garo] = 1;
	tail.push({ sero,garo });

	while (!myQueue.empty()) {
		int nowSero = myQueue.front().first;
		int nowGaro = myQueue.front().second;
		myQueue.pop();

		configGoTo();
		int nextSero = nowSero + dy[goTo];
		int nextGaro = nowGaro + dx[goTo];

		if (isInside(nextSero, nextGaro) == false
			|| snail[nextSero][nextGaro] == 1) {
			nowTime++;
			return;
		}


		//꼬리 그대로
		//꼬리를 원상복구

		if (arr[nextSero][nextGaro] == 2) {
			myQueue.push({ nextSero,nextGaro });
			snail[nextSero][nextGaro] = 1;
			tail.push({ nextSero,nextGaro });
			arr[nextSero][nextGaro] = 0;
		}
		else {
			myQueue.push({ nextSero,nextGaro });
			snail[nextSero][nextGaro] = 1;
			tail.push({ nextSero, nextGaro });
			int dSero = tail.front().first;
			int dGaro = tail.front().second;
			tail.pop();
			snail[dSero][dGaro] = -1;

		}

		nowTime++;
	}
}



void GameStart() {
	BFS(0, 0);

	cout << nowTime;
}

int main(void) {
	Input();
	GameStart();
}