[SWEA 4112] 이상한 피라미드 탐험 (C++)

문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWJHmLraeEwDFAUH#

SW Expert Academy

1. 주의할 점 (모두 중요)

- 이 문제는 구현보다는 배열을 어떻게 설정할 것인지 생각하는게 중요!

- Arr[][],Numx[],Numy[]를 직접 만들어서 시행했는데, TC를 입력받기 전에 미리 1번 Make_arr()함수를 실행하여 생성해 놓는다

- 6각형 모양이라고 생각하고 (y,x)를 기준으로 6방향인 (y-1,x+1), (y,x+2), (y+1,x+1), (y+1,x-1), (y,x-2), (y-1,x-1)를 탐색한다

- 입력받는 A,B의 최대값은 10000이므로 N*(N+1)/2 ≒ 10000 으로 N=150이라고 설정했다. 하지만 X를 기준으로 최대 2칸씩 양옆으로 이동하므로 Arr[][]의 범위를 300으로 놓고 시작한다

 

2. 구현

- TC를 입력받기 전, Make_arr() 함수를 통해 Arr[][], Numx[], Numy[]를 구한다

- TC마다 Check[] 배열을 초기화한다(Check[idx] : idx 숫자를 방문했는지 확인)

- A,B를 입력받은 후, Bfs() 함수를 실행해서 정답을 도출한다

 

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
struct info {
	int x, y;
};
info tmp;
int dx[6] = { 1,2,1,-1,-2,-1 };
int dy[6] = { -1,0,1,1,0,-1 };
int start, target, result;
int check[10001];
int arr[300][300];
int numx[10001];
int numy[10001];
void bfs() {
	queue<info> q;
	tmp.x = numx[start];
	tmp.y = numy[start];
	q.push(tmp);
	check[start] = 0;
	while (!q.empty()) {
		int cx = q.front().x;
		int cy = q.front().y;
		q.pop();
		if (arr[cy][cx] == target) {
			result = check[arr[cy][cx]];
			break;
		}
		for (int i = 0; i < 6; i++) {
			int nx = cx + dx[i];
			int ny = cy + dy[i];
			if (nx >= 0 && ny >= 0 && nx < 300 && ny < 300 && arr[ny][nx] != 0 && check[arr[ny][nx]] == -1) {
				check[arr[ny][nx]] = check[arr[cy][cx]] + 1;
				tmp.x = nx;
				tmp.y = ny;
				q.push(tmp);
			}
		}
	}
}

void make_arr() {
	int num = 1;
	bool finish = false;
	for (int k = 1;; k++) {
		for (int i = 0; i < 300; i++) {
			for (int j = 150 - i; j <= 150 + i; j += 2) {
				arr[i][j] = num;
				numx[num] = j;
				numy[num] = i;
				num++;
				if (num > 10000) {
					finish = true;
					break;
				}
			}
			if (finish) break;
		}
		if (finish) break;
	}
}

int main() {
	int test;
	cin >> test;
	make_arr();
	for (int t = 1; t <= test; t++) {
		cin >> start >> target;
		int maxi = max(start, target);
		for (int i = 1; i <= maxi; i++)
			check[i] = -1;
		bfs();
		cout << "#" << t << " " << result << '\n';
	}
	system("pause");
	return 0;
}