백준 3190번 뱀 (C++)

삼성 SW 역량 테스트 기출 문제이다.

역시 삼성은 dfs bfs 엄청 좋아하는 것 같다. 

그리고 언제나 그렇듯이 뭔가 되게 애매하게? 문제를 낸다.... 이번에도 가장 중요한 포인트가 있었다.

 

1. 시간이 끝나고 방향이 변한다. 즉 8 D 라고 들어오면 8초가 끝난 후 9초부터 방향이 바뀌는 것이다.

2. 1,1 부터 시작은 우리 일반 적 배열에선 0,0 에서 시작하는 것과 같다.

 

나의 풀이 

- 각 방향이 주어지고 어떠한 거리를 구하는 것이 아니기 때문에 DFS가 적절하다.

- 지나온 지점을 모두 기억하고 있어야한다. 이동할 수록 꼬리의 위치가 바뀌기 때문이다. 나의 경우 큐에 담아두었다.

- 이번에 간 지점이 사과이면 큐에 담기만 하고 방문표시를 한다.

- 이번에 간 지점이 사과가 없으면 큐에 담고 큐의 front에서 pop하고 가장 아래의 위치에 방문표시를 해제한다.

 

#include <iostream>
#include <queue>
#define MAX 101
using namespace std;

int N;
int boad[MAX][MAX] = { 0, };

bool visited[MAX][MAX] = { false, };

queue<pair<int, int >> q;
vector<pair<int, char>> direct;

int idx = 0;
void dfs(int hereX, int hereY, int cnt, int direction) {
	q.push(make_pair(hereX, hereY));
	if (boad[hereX][hereY] == 0) {
		visited[q.front().first][q.front().second] = false;
 		q.pop();
	}

	boad[hereX][hereY] = 0;
	if (idx < direct.size() && cnt - 1 == direct[idx].first) {
		if (direct[idx].second == 'D') {
			if (direction == 4)
				direction = 1;
			else
				direction += 1;
		}
		else if(direct[idx].second == 'L') {
			if (direction == 1)
				direction = 4;
			else
				direction -= 1;
		}
		idx += 1;
	}
	if (direction == 1) {
		int nextX = hereX;
		int nextY = hereY + 1;

		if (nextX < N && nextX > -1 && nextY < N && nextY > -1 && visited[nextX][nextY] == false) {
			visited[nextX][nextY] = true;
			dfs(nextX, nextY, cnt + 1, direction);
		}
		else {
			cout << cnt << '\n';
			exit(0);
		}
	}
	else if (direction == 2) {
		int nextX = hereX + 1;
		int nextY = hereY;

		if (nextX < N && nextX > -1 && nextY < N && nextY > -1 && visited[nextX][nextY] == false) {
			visited[nextX][nextY] = true;

			dfs(nextX, nextY, cnt + 1, direction);
		}
		else {
			cout << cnt << '\n';
			exit(0);
		}
	}
	else if (direction == 3) {
		int nextX = hereX;
		int nextY = hereY - 1;

		if (nextX < N && nextX > -1 && nextY < N && nextY > -1 && visited[nextX][nextY] == false) {
			visited[nextX][nextY] = true;

			dfs(nextX, nextY, cnt + 1, direction);
		}
		else {
			cout << cnt << '\n';
			exit(0);
		}
	}
	else if (direction == 4) {
		int nextX = hereX - 1;
		int nextY = hereY;

		if (nextX < N && nextX > -1 && nextY < N && nextY > -1 && visited[nextX][nextY] == false) {
			visited[nextX][nextY] = true;

			dfs(nextX, nextY, cnt + 1, direction);
		}
		else {
			cout << cnt << '\n';
			exit(0);
		}
	}
}

int main() {
	int K;

	cin >> N >> K;

	for (int i = 0; i < K; i++) {
		int x, y;
		cin >> x >> y;
		boad[x - 1][y - 1] = 1;
	}
	
	int L;
	cin >> L;
	for (int i = 0; i < L; i++) {
		int x;
		char y;
		cin >> x >> y;
		direct.push_back(make_pair(x, y));
	}
	q.push(make_pair(0, 0));
	
	dfs(0, 1, 2, 1);

	return 0;
}