[코딩테스트 스터디/C++] 백준 3190번 뱀

1.문제 링크

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

2. 풀이 전 계획과 생각

• 구현으로 풀기

3. 풀이

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

int N, K, L;

int map[101][101]; // 뱀이 있는 좌표는 1, 없는 좌표는 0  

vector<pair<int, int> > apple;
vector<pair<int, char> > command; 

queue<pair<int, int> > searchTail; // 꼬리 좌표를 알아내기 위한 큐  

int direction = 0;  // 0: 동 1: 서 2: 남, 3: 북  
int cx=1, cy=1;  // 머리좌표  

// 방향 설정  
void setDirection(char c){
	if(c=='L'){
		if(direction==0){
			direction=3;
		}
		else if(direction==1){
			direction=2;
		}
		else if(direction==2){
			direction=0;
		}
		else if(direction==3){
			direction=1;
		}
	}
	else if(c=='D'){
		if(direction==0){
			direction=2;
		}
		else if(direction==1){
			direction=3;
		}
		else if(direction==2){
			direction=1;
		}
		else if(direction==3){
			direction=0;
		}
	}
}

// 매개변수로 들어온 좌표값에 사과가 있는지 여부를 반환  
bool IsApple(int x, int y){
	for(int i=0;i<apple.size(); i++){
		if(apple[i].first==x && apple[i].second==y) {
			apple[i].first=-1;
			apple[i].second=-1;
			return true;
		}
	}	
	return false;
} 

// 꼬리 짜르기  
void updateTail(){
	int x = searchTail.front().first;
	int y= searchTail.front().second;
	searchTail.pop();
	map[x][y]=0;
}

int main(){
	// 입출력 빨라지게 해줌 
	ios_base::sync_with_stdio(0);
    cin.tie(0);
    
	cin>>N;
	cin>>K;
	
	// 사과 위치좌표 입력  
	for(int i=0;i<K;i++){
		int x,y;
		cin>>x>>y;
		apple.push_back({x,y});
	}
	
	map[1][1]=1;
	searchTail.push({1,1});
	
	// 몇초에 어떤 방향으로 회전할지 입력  
	cin>>L;
	for(int i=0; i<L; i++){
		int x; char c;
		cin>>x>>c;
		command.push_back({x,c});  
	}
	
	// 0초부터 1초씩 늘려감  
	int ans=0;
	while(true){
		ans++;
		if(direction==0){
			if(cy+1> N) break;
			if(map[cx][cy+1]) break;
			cy+=1;
 			searchTail.push({cx,cy});
			if(IsApple(cx,cy)) map[cx][cy]=1;
			else{
				map[cx][cy]=1;
				updateTail();
			}
		}
		else if(direction==1){
			if(cy-1< 1) break;
			if(map[cx][cy-1]) break;
			cy-=1;
			searchTail.push({cx,cy});
			if(IsApple(cx,cy)) map[cx][cy]=1;
			else{
				map[cx][cy]=1;
				updateTail();
			}
		}
		else if(direction==2){
			if(cx+1> N) break;
			if(map[cx+1][cy]) break;
			cx+=1;
			searchTail.push({cx,cy});
			if(IsApple(cx,cy)) map[cx][cy]=1;
			else{
				map[cx][cy]=1;
				updateTail();
			}
		}
		else{
			if(cx-1< 1) break;
			if(map[cx-1][cy]) break;
			cx-=1;
			searchTail.push({cx,cy});
			if(IsApple(cx,cy)) map[cx][cy]=1;
			else{
				map[cx][cy]=1;
				updateTail();
			}
		}
		if(command.size()!=0){
			if(command[0].first==ans){
				setDirection(command[0].second);
				command.erase(command.begin());
			}  	
		}
	}
	
	// 답 출력  
	cout<<ans;
}

4. 풀이하면서 고민했던 점

• 구현을 어떻게 하면 좋을지 고민함.

• 반례가 계속 발생함. 꼬리부분을 짜를 때 발생한 반례였는데, 어떻게 꼬리인지를 인식해 꼬리를 자를지 고민함

5. 문제를 풀고 알게된 개념 및 소감

• 함수를 나눠 작성하면 풀기 편함 모든 코드를 main함수에 작성하기 보다는 기능별로 함수를 만들어 코드를 작성하면 풀이하거나, 오류가 났을 때 문제점을 찾기가 보다 쉽다.