[백준 17780,17837] 새로운 게임1,2 c++ (완전 탐색, 구현)

 

17780번

문제 링크

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

17780번: 새로운 게임

 

문제 풀이

우선, 말이 합쳐진 이후에는 가장 위, 가장 아래 2개의 말만 저장하면 된다. ( 가운데의 말은 아무리 위아래를 바꾸더라도 맨 아래에 와서 움직임에 관여 불가 ) 

따라서 각 말이 합쳐질 때마다, 적절한 top&bottom을 유지시킨뒤 움직임을 지시했다.

 

처음에는 queue를 통한 bfs 탐색으로 수행하고, 말이 합쳐질 경우, queue에 추가하지 않아 분기점을 합치는 식으로 완전탐색을 진행했지만, 이는 문제점이 있다.

 

2번말 위에 3번말이 있을 때, 만약 2번말이 이동하여 빨간 칸을 밟는다면, 해당 턴에 3번말의 움직임이 수행될 가능성이 존재하기에, 1개의 말 덩어리가 같은턴에 2회 이상 움직일 수 있는 것이다.

따라서 각 말의 번호에 따라 해당 말의 위치를 location 배열에 저장하고, 매번 이동한 칸의 성질에 따라 적절하게 top&bottom의 location 값을 수정하여 문제를 해결했다. (만약 유지하지 않아도 되는 중간 값이 되는 경우, 더 이상 location값을 갱신하지 않기에 invalid한 값이 된다.)

 

정답 코드

#include<iostream>
#include<queue>
using namespace std;
struct Point{ //한개의 칸에 누적되어지는 말을 표현 
	int top;
	int bottom;
	int cnt;
};

int dr[4] = { 0,0,-1,1 };
int dc[4] = { 1,-1,0,0 };
Point points[13][13];
int arr[13][13];
const Point NONE = { -1,-1,0 };

pair<int, int> location[11];

int reverse_dir(int dir) {
	if (dir == 0)return 1;
	if (dir == 1)return 0;
	if (dir == 2)return 3;
	if (dir == 3)return 2;

}


int direction[11];

int main() {
	//맨위, 맨아래 말, cnt
	int ans_val = 4, answer = 0;
	int n, k;
	cin >> n >> k;
	for (int r = 0; r < n; r++) {
		for (int c = 0; c < n; c++) {
			points[r][c] = NONE;
		}
	}

	for (int r = 0; r < n; r++) {
		for (int c = 0; c < n; c++) {
			cin>>arr[r][c];
		}
	}
	queue<pair<int,int>> qu;
	for (int i = 0; i < k; i++) {
		int r, c, dir;
		cin >> r >> c >> dir;
		direction[i] = dir-1;// i번 말의 방향 지정 
		points[r-1][c-1] = { i,i,1 };//처음엔 자신이 top & bottom
		location[i] = { r - 1,c - 1 };
	}
	int t = 0;
	int num = k;
	
	while (answer==0) {
		t++;//턴	
		if (t > 1000) {
			answer = -1;
			break;
		}

		
		//   (2,3)  묶여있어도, 빨간거 밝아서   2,3 하고 같은 턴에 3,2로 이동가능!    
		//while (!qu.empty() && count < now_num) {// && count < now_num
		for(int i=0;i<k;i++){
			int r = location[i].first, c = location[i].second;
			if (points[r][c].bottom != i)continue;
			int dir = direction[points[r][c].bottom];
			int nr = r + dr[dir], nc = c + dc[dir];

			//맵 밖 or 파란색 이면 반대 방향 으로 nr,nc를 수정!
			if ((0 > nr || nr >= n || 0 > nc || nc >= n) || (arr[nr][nc] == 2)) {
				int rev_dir = reverse_dir(dir);
				direction[points[r][c].bottom] = rev_dir;
				nr = r + dr[rev_dir], nc = c + dc[rev_dir];
				//반대 방향도 맵밖 or 파랑색이면 이동 x방향만
				if ((0 > nr || nr >= n || 0 > nc || nc >= n) || (arr[nr][nc] == 2)) {
					continue;
				}
			}

			//빨간색
			if (arr[nr][nc] == 1) {
				if (points[nr][nc].cnt != 0) {
					points[nr][nc].top = points[r][c].bottom;
					points[nr][nc].cnt = points[nr][nc].cnt + points[r][c].cnt;
					if (points[nr][nc].cnt >= ans_val) {
						answer = t;
					}
				}
				else {
					points[nr][nc] = points[r][c];
					int tmp = points[nr][nc].top;
					points[nr][nc].top = points[nr][nc].bottom;
					points[nr][nc].bottom = tmp;
				}
				points[r][c] = NONE;
				location[points[nr][nc].top] = { nr,nc };
				location[points[nr][nc].bottom] = { nr,nc };
			}
			//일반
			else if (arr[nr][nc] == 0) {
				if (points[nr][nc].cnt!=0) { //말이 이미 있다면 올리기
					points[nr][nc].top = points[r][c].top;
					location[points[nr][nc].top] = { nr,nc };
					points[nr][nc].cnt = points[nr][nc].cnt+points[r][c].cnt;
					if (points[nr][nc].cnt >= ans_val) {
						answer = t;
					}
					points[r][c] = NONE;
					num--;// 한턴에 움직일 말의 개수 1 감소

				}
				else {//말이 없다면 그냥 이동 
					points[nr][nc] = points[r][c];
					points[r][c] = NONE;
					location[points[nr][nc].top] = { nr,nc };
					location[points[nr][nc].bottom] = { nr,nc };
				}
			}

		}
	}
	cout << answer << endl;

	
	
}

 

 

17837번

문제 링크

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

17837번: 새로운 게임 2

문제 풀이

이전의 문제와 다르게, 말이 합쳐지면 맨 아랫말만 이동 가능한게 아니라, 각각의 말이 자신의 위에 쌓인 말을 가지고 이동하는 형식이다.

여기서 포인트는 '빨간칸', '파란 칸' 의 처리이다.

 

[파란 칸or 맵 밖]

파란 칸 혹은 맵 밖으로 이동한 경우, 방향을 바꿔서 이동하게 된다. 따라서 이 상황에서 방향을 바꾼 뒤, 만약 또다시 파란 칸이 나온다면 이동을 하지않고, 그 외의 칸이 나온다면 각각의 칸에 맞는 로직을 통해 해결하면 된다.

 

[일반 칸]

(r,c) -> (nr,nc) 의 이동을 수행하려고 할 때, 만약 nr,nc가 일반 칸이면 어떻게 해야할까?

(r,c) 에서 이동할 만의 위에 있는 모든 말들을 정방향으로 nr,nc의 말 위에 쌓아야한다

즉, (r,c)의 앞에서 부터 1개씩 (nr,nc)의 뒤에 쌓아주면 된다.

 

[빨간 칸]

(r,c) -> (nr,nc) 의 이동을 수행하려고 할 때, 만약 nr,nc가 빨간 칸이면 어떻게 해야할까?

(r,c) 에서 이동할 만의 위에 있는 모든 말들을 역순으로 nr,nc의 말 위에 쌓아야한다.

즉, (r,c)의 뒤에서 부터 1개씩 (nr,nc)의 뒤에 쌓아주면 된다.

 

이러한 상황을 고려하여, 맵의 모든 지점에 deque 자료구조를 할당하여 이동시마다 적절하게 말의 값을 이동 시키도록 구현했다.

 

 

정답 코드

#include<iostream>
#include<queue>
#include<deque>
using namespace std;
// 40분 경과. 
deque<int> obj_list[13][13]; //각 위치에 있는 말의 모음 
pair<int, int> location[13]; //각 말의 위치
int dir[13];//각 말의 방향 
int arr[13][13];

int dr[4] = { 0,0,-1,1 };
int dc[4] = { 1,-1,0,0 };

int rev_dir(int d) {
	if (d == 0)return 1;
	if (d == 1)return 0;
	if (d == 2)return 3;
	if (d == 3)return 2;
}

int main() {

	// 일반 칸: front -> Back
	// 빨간 칸: back_> Back 
	int ans_val = 4;
	int n, k;
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
		}
	}
	for (int i = 0; i < k; i++) {
		int r, c, d;
		cin >> r >> c >> d;
		dir[i] = d - 1;
		location[i] = { r - 1,c - 1 };
		obj_list[r - 1][c - 1].push_back(i);
	}

	int answer = -1;
	int turn = 0;


	
	while (answer==-1) {
		turn++;
		
		if (turn > 1000) {
			break;
		}
		for (int i = 0; i < k; i++) {
			int r = location[i].first, c = location[i].second;
			int nr = r + dr[dir[i]], nc = c + dc[dir[i]];
			if ((0 > nr || nr >= n || 0 > nc || nc >= n) || (arr[nr][nc] == 2)) {
				dir[i] = rev_dir(dir[i]);
				nr = r + dr[dir[i]], nc = c + dc[dir[i]];//뒤집힌 방향으로 갱신
				//만약 또 밖 or 파란색 -> 이동 x 
				if ((0 > nr || nr >= n || 0 > nc || nc >= n) || (arr[nr][nc] == 2)) continue;
				
			}

			if (arr[nr][nc] == 0) {// 일반
				int cnt = obj_list[r][c].size();
				bool st = false;

				while (cnt--) {
					int f = obj_list[r][c].front();
					if (f == i) {
						st = true;
					}
					if (st) {//해당 말 & 그 위의 말 다음 칸으로 이동. 
						obj_list[nr][nc].push_back(f);
						obj_list[r][c].pop_front();
						location[f] = { nr,nc };
					}
					else {
						obj_list[r][c].push_back(f);//해당 말 아래의 말들은 그대로 둔다.
						obj_list[r][c].pop_front();
					}
				}
				if (obj_list[nr][nc].size() >= ans_val) {
					answer = turn;
				}
			}
			else if (arr[nr][nc] == 1) { // 빨강
				int cnt = obj_list[r][c].size();
				bool st = false;
				while (cnt--) {
					int b = obj_list[r][c].back(); 
					obj_list[nr][nc].push_back(b);
					obj_list[r][c].pop_back();
					location[b] = { nr,nc };
					if (b == i) {
						break;
					}
					
					
				}
				if (obj_list[nr][nc].size() >= ans_val) {
					answer = turn;
				}
			}
		}
	}
	cout << answer << endl;
}