[BOJ] 3190번 : 뱀

1. problem : 

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

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second 
int n, k, l; // board 크기, 사과 개수, 방향 변환 횟수;

int board[102][102];
int isvis[102][102]; 
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
pair<int, int> head = { 0,0 };

deque<pair<int, int>> snake;
queue<pair<int, char>> dir_loc;  // 방향변환 <시간,방향> 저장 

bool isover = false; // game 끝났는지
int gametime;
int curdir = 1;

void go(int dir) {
	head.X += dx[dir]; 
	head.Y += dy[dir]; 
	if (head.X < 0 || head.X >= n || head.Y < 0 || head.Y >= n || isvis[head.X][head.Y] == 1) {
		isover = true; 
		return;
	}
	isvis[head.X][head.Y] = 1; 
	snake.push_front({ head.X,head.Y });
	
	if (board[head.X][head.Y] == 1) {
		board[head.X][head.Y] = 0; 
	}
	else {
		isvis[snake.back().X][snake.back().Y] = 0; 
		snake.pop_back();
	}
	
}
void change_dir(int todir) {
	if (todir == 'D') curdir = (1 + curdir) % 4;
	else curdir = (3 + curdir) % 4; 
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	cin >> k; 
	while (k--) {
		int x, y; 
		cin >> x >> y; 
		board[x - 1][y - 1] = 1; 
	}
	cin >> l; 
	for (int i = 0; i < l; i++) {
		int t;
		char v;
		cin >> t >> v;
		dir_loc.push({ t,v });
	}
	snake.push_back({ 0,0 });
	isvis[0][0] = 1;
	while (1) {
		gametime++;  
		go(curdir);
		if (isover) break; 
		
		if (!dir_loc.empty() && dir_loc.front().X == gametime) {
			change_dir(dir_loc.front().Y);
			dir_loc.pop();
		}
	}
	cout << gametime << '\n';
}

deque을 이용해서 뱀이 있는 좌표를 추적하는 것을 놓쳤다.  

 

3. solution 2 :

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second 

int n, k, l; // 보드 크기, 사과 개수, 방향 변환 횟수

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

queue<pair<int, char>> dir_loc;  // 방향변환 <시간,방향> 저장 

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n;
    cin >> k;
    
    for (int i = 0; i < k; i++) {
        int x, y; 
        cin >> x >> y;
        board[x-1][y-1] = 1; // 사과 위치 설정
    }
    
    cin >> l;
    for (int i = 0; i < l; i++) {
        int t;
        char v;
        cin >> t >> v;
        dir_loc.push({t, v});
    }
    
    deque<pair<int, int>> snake; // 뱀의 위치를 저장할 덱
    snake.push_back({0, 0});
    isvis[0][0] = 1;
    
    int gametime = 0;
    int curdir = 1;
    
    while (true) {
        gametime++;
        
        int nx = snake.front().X + dx[curdir];
        int ny = snake.front().Y + dy[curdir];
        
        // 벽에 부딪히거나 자기자신의 몸에 부딪히면 게임 종료
        if (nx < 0 || nx >= n || ny < 0 || ny >= n || isvis[nx][ny]) {
            break;
        }
        
        // 뱀이 이동
        snake.push_front({nx, ny});
        isvis[nx][ny] = 1;
        
        if (board[nx][ny] == 1) { // 사과가 있다면
            board[nx][ny] = 0; // 사과를 먹음
        } else { // 사과가 없다면 꼬리를 줄임
            isvis[snake.back().X][snake.back().Y] = 0;
            snake.pop_back();
        }
        
        // 방향 전환
        if (!dir_loc.empty() && dir_loc.front().X == gametime) {
            char dir = dir_loc.front().Y;
            dir_loc.pop();
            
            if (dir == 'D') {
                curdir = (curdir + 1) % 4; // 오른쪽 회전
            } else {
                curdir = (curdir + 3) % 4; // 왼쪽 회전
            }
        }
    }
    
    cout << gametime << '\n';
}

훨씬 깔끔한 풀이. chatgpt가 작성했다. deque의 front를 사실상 head의 좌표로 이용해서 전진할 때, 이용하고 있다. 이게 훨씬 낫네.

 

4. solution 3 :

// Authored by : yongjunleeme
// Co-authored by : -
// http://boj.kr/7a74fe31a87c42ffbaa39e94711ae557
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

int n, k;
int a, b, c, l;
char d;
int board[105][105]; // 1: 뱀, 2: 사과
int second = 0;
int dx[4] = {1, 0, -1, 0};  // [1][0]: 아래, [0][1]: 오른쪽, [-1][0]: 위, [0][-1]: 왼쪽
int dy[4] = {0, 1, 0, -1};
deque<pair<int, int>> dq;
queue<pair<int, char>> switchDir;

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n;
  cin >> k;
  while(k--){
    cin >> a >> b;
    // 사과
    board[a][b] = 2;
  }

  cin >> l;
  while(l--){
    // 방향전환
    cin >> c >> d;
    switchDir.push({c, d});
  }

  dq.push_front({1,1});
  int dir = 1;

  while(1){
    dir %= 4;

    auto cur = dq.front();
    board[cur.X][cur.Y] = 1;
    second++;

    int nx = cur.X + dx[dir];
    int ny = cur.Y + dy[dir];

    if(nx < 1 || nx > n || ny < 1 || ny > n) break;
    if(board[nx][ny] == 1) break;

    if(board[nx][ny] != 2) {
      auto tail = dq.back();
      board[tail.X][tail.Y] = 0;
      dq.pop_back();
    }

    auto sd = switchDir.front();
    if(sd.X == second){
      if(sd.Y == 'L') dir += 1;
      else if(sd.Y == 'D') dir += 3;
      switchDir.pop();
    }
    dq.push_front({nx, ny});
  }
  cout << second;
}

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x0D/solutions/3190.cpp

basic-algo-lecture/0x0D/solutions/3190.cpp at master · encrypted-def/basic-algo-lecture