백준 3190 뱀

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

3190번: 뱀

 

- 초기 설계를 잘 해야하는 시뮬레이션 문제이다.

 

- 일단 방문 여부를 체크하기위한 d 배열을 둔다. d에는 가장 최근에 방문한 시간이 들어간다. 

  - 만약 d가 -1이 아니면, 이전에 방문한 적이 있는 것이고 그와 동시에 해당 격자판에 현재 몸통이 존재하는지

    를 체크해준다. 이는 now와 몸 길이 len으로 체크한다.

 

- now에 1을 더해주고, x,y와 격자판 범위를 넘어가는 지를 체크한다. 다음으로, d 배열의 값을 체크한다.

 

- 중간중간 방향을 바꿀 때는 (now<t) 를 활용하여 체크해준다. 더 이상 방향전환이 없을 때는 t에 최대값인 n * n + 1을 넣어주고 이를 체크한다.

 

- 방향을 바꾸는 로직은 dir에 1이나 3을 더한 후 4로 나눈 나머지로 구해주면 된다.

 

#include <iostream>
#include <cstring>
using namespace std;
int d[100][100]; // 해당 자리를 방문한 시간이 들어감
bool apple[100][100];
// 오른쪽, 아래, 왼쪽, 위
int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };
int main() {
	int n; 
	cin >> n;
	int m; 
	cin >> m;
	while (m--) { // 사과의 위치 저장
		int x, y;
		cin >> x >> y;
		apple[x - 1][y - 1] = true;
	}
	memset(d, -1, sizeof(d)); // -1 초기화. 즉 -1은 방문하지 않은 자리 의미
	int x = 0;
	int y = 0;
	int dir = 0; // 처음 방향. 오른쪽으로 이동
	int len = 1;
	d[x][y] = 0; // 초기위치 방문시간 0
	cin >> m;
	int now = 0;
	for (int k = 0; k <= m; k++) {
		int t = n * n + 1; // 다음 방향전환 까지의 값
		char ch = 'L'; 
		if (k < m) { 
			cin >> t >> ch;
		}
		while (now < t) {
			now += 1;
			x += dx[dir];
			y += dy[dir];
			if (x < 0 || x >= n || y < 0 || y >= n) { // 벽에 닿는 경우
				cout << now << '\n';
				return 0;
			}
			if (apple[x][y]) {
				apple[x][y] = false; // 사과를 먹고 없애준다
				len += 1; // 몸 길이 증가
			}
			if (d[x][y] != -1 && now - d[x][y] <= len) { // 격자판 재방문 && 해당 격자판에 몸통이 존재하는 경우
				cout << now << '\n';
				return 0;
			}
			d[x][y] = now;
		}
        // 방향 바꾸기
		if (ch == 'L') { 
			dir = (dir + 3) % 4;
		}
		else {
			dir = (dir + 1) % 4;
		}
	}
	return 0;
}