백준 3190 (뱀)

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

3190번: 뱀

풀이

해당 문제는 완전탐색 문제로 재귀함수를 이용하여 풀이할 수 있다.

조건을 살펴보면 다음과 같다.

뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.

• 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
• 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
• 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

필요한 요소는 다음과 같다.

1. 사과의 위치를 저장할 배열 map

2. 뱀의 위치를 저장할 배열 visit

3. 특정 초 에 방향정보를 담을 배열

4. 뱀의 이동경로를 담을 queue

다음과 같은 요소들을 활용하여 뱀을 우측으로 이동시키면서 visit 배열에 뱀이 이동한 경로를 1로 바꾸어 준다 만약 사과가 있다면 map의 사과가 있는 좌표의 값을 0으로 초기화 시킨 후 큐에 현재 뱀의 위치를 추가한다. 만약 뱀이 이동했을 때 사과가 없다면 뱀의 꼬리의 위치를 0으로 초기화 시켜준다 (큐에 front 에는 뱀의 꼬리 좌표가 담겨있음) 그 뒤 큐에 뱀의 이동한 위치의 좌표를 넣어 준다.

위의 과정을 계속 재귀하면 된다.

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

using namespace std;
struct dirList{
	char cmd;
	int check;
};

struct Node{
	int y, x;
};
dirList dirlist[10001];
queue<Node> qu;

int n;
int applecnt;
int dirCnt;

int	map[100][100];
int visit[100][100];
int check[4][2] = {
	0, 1,
	1, 0,
	0, -1,
	-1, 0
};

void dfs(int level, int y, int x, int idx){
	if (dirlist[level].check == 1){
		//방향전환
		if (dirlist[level].cmd == 'D'){
			if (idx == 0) idx = 1;
			else if (idx == 1) idx = 2;
			else if (idx == 2) idx = 3;
			else if (idx == 3) idx = 0;
		}
		else{
			if (idx == 0) idx = 3;
			else if (idx == 3) idx = 2;
			else if (idx == 2) idx = 1;
			else if (idx == 1) idx = 0;
		}
	}

	int dy = y + check[idx][0];
	int dx = x + check[idx][1];

	if (dy >= 0 && dx >= 0 && dy < n && dx < n && visit[dy][dx] == 0){
    // 뱀의 이동 위치 visit 배열에 체크
		visit[dy][dx] = 1;
		if (map[dy][dx] == 0){
        // 이동한 위치에 사과가 없을 경우 큐의 front 값을 pop하고 이동한 좌표를 추가
        // 큐에 front 좌표 (꼬리) 의 위치를 0으로 바꾼다
			if (qu.empty() == true){
				Node tmp = { dy, dx };
				qu.push(tmp);
			}
			else{
				visit[qu.front().y][qu.front().x] = 0;
				qu.pop();
				Node tmp = { dy, dx };
				qu.push(tmp);
			}
		}
		if (map[dy][dx] == 2){
        // 사과가 있을경우 큐에 이동한 위치를 추가
			Node tmp = { dy, dx };
			qu.push(tmp);
			map[dy][dx] = 0;
		}
		dfs(level + 1, dy, dx, idx);
	}

	else{
		cout << level + 1 << endl;
	}
}

int main(){
	//freopen_s(new FILE*, "tes.text", "r", stdin);
	cin >> n;
	cin >> applecnt;
	// 0 : 빈칸 -> 1 : 뱀 -> 2 : 사과

	for (int i = 0; i < applecnt; ++i){
		int y, x;
		cin >> y >> x;
		map[y -1][x - 1] = 2;
	}
	cin >> dirCnt;

	for (int i = 0; i < dirCnt; ++i){
		int move;
		char ch;
		cin >> move >> ch;
		dirlist[move] = { ch , 1};
	}
	Node tmp = { 0, 0 };
	qu.push(tmp);
	visit[0][0] = 1;
	dfs(0, 0, 0, 0);


}