[알고리즘] 백준 17387 새로운 게임 2

📖문제

17387 새로운 게임 2

💡구상

구현 문제니 문제의 조건을 먼저 살펴보자.

• 맵의 크기 NXN, 말의 개수 K
• 말은 1턴에 1번 말부터 K번 말까지 순서대로 한칸 움직인다.
  • 이동 방향(오른쪽 :1, 왼쪽: 2, 위쪽: 3, 아래쪽:4)
  • 말이 이동할때, 위에 올려져 있는 말이 있으면 함께 이동한다.
  • 말은 이동할 지점에 말이 있다면 그 말 위로 이동한다.
• 맵의 색상 (흰색: 0, 빨간색: 1, 파란색: 2)
  • 흰색: 이동한다.
  • 빨간색: 현재 말부터 머리 위에 쌓여있는 모든 말의 순서를 반대로 바꾸고 이동한다.
  • 파란색
    • 말의 방향을 반대로 바꾼다.
    • 바꾼 방향으로 1칸 이동한다.
    • 바꾼 방향의 목적지가 파란색이라면 이동하지 않는다.
    • 체스판을 벗어나는 경우 파란색과 동일하게 처리한다.
• 종료 조건
  • 한 체스판에 쌓인 말이 4마리 이상이라면, 현재 턴을 출력한다.
  • 현재 턴이 1,000 이상이거나 절대로 게임을 종료되지 않는 경우 -1을 출력한다.

위 조건에 따라서 차근차근 구현해보자.

🔍코드

#include<bits/stdc++.h> 
using namespace std;
int n,k,x,y,d,cnt=1; 
int mp[13][13];
stack<int> horseMap[13][13];
vector<int> horse[11];
int dy[4]={0,0,-1,1};
int dx[4]={1,-1,0,0}; 

// 방향 반대로 바꾸기 
int changeDir(int num){
	if(num == 0) return 1;
	if(num == 1) return 0;
	if(num == 2) return 3;
	if(num == 3) return 2;
}
// 말 움직이기 
void move(int y, int x, int dir, int idx,int turn){
	// 다음 지점 
	int ny = y+dy[dir];
	int nx = x+dx[dir];
	// 다음 지점 검토 
	if(mp[ny][nx]==2 || ny<0 || ny>=n || nx<0 ||nx>=n){
		// 다음 지점이 범위 밖이거나
		// 파란색 바닥일 경우 방향을 바꿈 
		horse[idx][2]=changeDir(horse[idx][2]);
		dir = horse[idx][2];
		ny = y+dy[dir];
	    nx = x+dx[dir];
		// 바꿔도 같다면 return(이동X) 
		if(mp[ny][nx]==2 || ny<0 || ny>=n || nx<0 ||nx>=n) return;
	}
	
	// 하양
	if(mp[ny][nx]==0){
		vector<int> v;
		// 자기 위에 있는것 먼저 벡터에 삽입 
		while(horseMap[y][x].top()!=idx){
			v.push_back(horseMap[y][x].top());
			// 말의 이동: 말의 좌표를 갱신해줌 
			horse[horseMap[y][x].top()][0]=ny;
			horse[horseMap[y][x].top()][1]=nx;
			// pop
			horseMap[y][x].pop();
		}
		// 현재 index의 말 같은 로직 실행 
		v.push_back(horseMap[y][x].top());
		horse[idx][0]=ny;
		horse[idx][1]=nx;
		horseMap[y][x].pop();
		// 벡터 순서 뒤집기 
		for(int i = v.size()-1; i>=0; i--){
			// horseMap에 삽입 
			horseMap[ny][nx].push(v[i]);
		}
	}
	
	// 빨강 
	if(mp[ny][nx]==1){
		// 자기 위에 있는것 먼저 벡터에 삽입
		while(horseMap[y][x].top()!=idx){
			horseMap[ny][nx].push(horseMap[y][x].top());
			// 말의 이동: 말의 좌표를 갱신해줌 
			horse[horseMap[y][x].top()][0]=ny;
			horse[horseMap[y][x].top()][1]=nx;
			// pop 
			horseMap[y][x].pop();
		}
		// 현재 index의 말 같은 로직 실행 
		horseMap[ny][nx].push(horseMap[y][x].top());
		horse[idx][0]=ny;
		horse[idx][1]=nx;
		horseMap[y][x].pop();
	}
	
	// 움직인 지점의 말이 4개이상 쌓여있다면 종료 
	if(horseMap[ny][nx].size()>=4){
		cout<<turn;
		exit(0);
	}
}
int main() {
	cin>>n>>k;
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			cin>>mp[i][j];
			// 0: 흰, 1: 빨, 2: 파 
		}
	}
	// 행, 열, 이동방향 (오,왼,위,아래) 
	for(int i=1; i<=k; i++){
		cin>>y>>x>>d;
		horse[i].push_back(y-1);
		horse[i].push_back(x-1);
		horse[i].push_back(d-1);
		horseMap[y-1][x-1].push(i); 
	}
	while(cnt<1000){
		// 현재 턴이 1,000 이상이라면 종료 
		for(int i=1; i<=k; i++){
			move(horse[i][0],horse[i][1],horse[i][2],i,cnt);
		}
		cnt++;
	} 
	 
	cout<<-1;
	return 0;
}

자료형

먼저, 문제의 로직을 수행하기 위해서는, 아래 3가지 자료형이 필요하다.

• 체스판 (색상 구분)
• 말의 현재 위치와 방향
• 체스판 마다 쌓여있는 말의 상황

체스판

색상 (0,1,2) 만 저장하면 되므로 단순한 정수배열로 선언한다.

int mp[13][13];

말의 현재 위치와 방향

말의 위치와 방향이 계속 바뀌므로 갱신해줄 자료형이 필요하다.
필자는 말의 index를 기준으로 위치와 방향을 갱신해줄 2차원 배열 벡터로 설정하였다.

vector<int> horse[11];

horse[index] 에 y좌표, x좌표, 방향값을 순서대로 push_back() 해줄 것이다.

체스판 마다 쌓여있는 말의 상황

말을 움직이는 로직을 자세히 살펴보자.
쌓여있는 순서가 존재하므로 stack으로 구현했다.

stack<int> horseMap[13][13];

horseMap[y][x] 는 y,x좌표의 맵에 있는 말들을 나타낸다.

움직이는 로직

다음 구역이 파랑일때, 맵을 벗어날때

좌표기반 탐색을 진행할때는 이상치 먼저 걸러내는 습관을 들이자.

void move(int y, int x, int dir, int idx,int turn){
	// 다음 지점 
	int ny = y+dy[dir];
	int nx = x+dx[dir];
	// 다음 지점 검토 
	if(mp[ny][nx]==2 || ny<0 || ny>=n || nx<0 ||nx>=n){
		// 다음 지점이 범위 밖이거나
		// 파란색 바닥일 경우 방향을 바꿈 
	}
}

파란색이라면, 방향을 바꿔야한다. 방향을 바꾸는 함수를 구현하자.

// 방향 반대로 바꾸기 
int changeDir(int num){
	if(num == 0) return 1;
	if(num == 1) return 0;
	if(num == 2) return 3;
	if(num == 3) return 2;
}

이 함수를 기반으로 파란색과 맵을 벗어날때의 경우를 구현해준다.

void move(int y, int x, int dir, int idx,int turn){
	// 다음 지점 
	int ny = y+dy[dir];
	int nx = x+dx[dir];
	// 다음 지점 검토 
	if(mp[ny][nx]==2 || ny<0 || ny>=n || nx<0 ||nx>=n){
		// 다음 지점이 범위 밖이거나
		// 파란색 바닥일 경우 방향을 바꿈 
		horse[idx][2]=changeDir(horse[idx][2]);
		dir = horse[idx][2];
		ny = y+dy[dir];
	    nx = x+dx[dir];
		// 바꿔도 같다면 return(이동X) 
		if(mp[ny][nx]==2 || ny<0 || ny>=n || nx<0 ||nx>=n) return;
	}

방향을 바꿔주고 바뀐 방향이 파란색이거나 맵 밖이라면 움직이지 않는다.

하양

먼저 하양인 경우는 자기 머리위에있는 말을 모두 데리고 도착지 말의 머리 위로 이동해야한다.

예를 들어 {y,x} 좌표의 A가 {ny, nx} 좌표로 이동해야할 경우, A위의 B,C 를 함께 데려가야한다.
하지만 스택 특성상 C->B->A 순서로 나오게된다. 그렇기 때문에 중간에서 값을 저장해줄 벡터가 필요하다.

if(mp[ny][nx]==0){
		vector<int> v;
		// 자기 위에 있는것 먼저 벡터에 삽입 
		while(horseMap[y][x].top()!=idx){
			v.push_back(horseMap[y][x].top());
			// 말의 이동: 말의 좌표를 갱신해줌 
			horse[horseMap[y][x].top()][0]=ny;
			horse[horseMap[y][x].top()][1]=nx;
			// pop
			horseMap[y][x].pop();
		}
		// 현재 index의 말 같은 로직 실행 
		v.push_back(horseMap[y][x].top());
		horse[idx][0]=ny;
		horse[idx][1]=nx;
		horseMap[y][x].pop();
		// 벡터 순서 뒤집기 
		for(int i = v.size()-1; i>=0; i--){
			// horseMap에 삽입 
			horseMap[ny][nx].push(v[i]);
		}
	}

벡터에 위 순서대로 저장해주고 인덱스 뒤에서 부터 접근하여 horseMap에 삽입해준다.

while(horseMap[y][x].top()!=idx){
	v.push_back(horseMap[y][x].top());
	// 말의 이동: 말의 좌표를 갱신해줌 
	horse[horseMap[y][x].top()][0]=ny;
	horse[horseMap[y][x].top()][1]=nx;
	// pop
	horseMap[y][x].pop();
}

위 코드에서도 pop 의 순서가 잘못되면 위치 갱신이 잘못될 수 있으니 주의하자.

빨강

빨강은 하양과 코드가 동일하지만, horseMap에 삽입시 반대의 순서로 삽입해주어야 하므로, 굳이 vector에 저장하지않고 바로 삽입해줘도 무방하다.

// 빨강 
if(mp[ny][nx]==1){
	// 자기 위에 있는것 먼저 벡터에 삽입
	while(horseMap[y][x].top()!=idx){
		horseMap[ny][nx].push(horseMap[y][x].top());
		// 말의 이동: 말의 좌표를 갱신해줌 
		horse[horseMap[y][x].top()][0]=ny;
		horse[horseMap[y][x].top()][1]=nx;
		// pop 
		horseMap[y][x].pop();
	}
	// 현재 index의 말 같은 로직 실행 
	horseMap[ny][nx].push(horseMap[y][x].top());
	horse[idx][0]=ny;
	horse[idx][1]=nx;
	horseMap[y][x].pop();
}

종료

움직인 지점의 말이 4개 이상 쌓여있다면 종료한다.

if(horseMap[ny][nx].size()>=4){
	cout<<turn;
	exit(0);
}

🔥배운 점

어려워 보이더라도 구현문제라면 차근차근 구현해 나가자.
그리고 문제의 조건을 잘 읽자..
문제의 조건을 잘못 읽어서 파랑일시 일시적으로 방향을 바꾸는 줄 알고 디버깅으로 2시간동안 고생했다😂