백준 1385번 벌집 C++

출처 : https://www.acmicpc.net/problem/1385

 

빙글빙글 돌면서 증가하는 벌집을 2차원 배열로 구현하고 bfs를 사용해서 문제를 해결하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>

using namespace std;
using ll = long long;

int dRow[6] = { -1,-2,-1,1,2,1 };
int dCol[6] = { 1,0,-1,-1,0,1 };
int moveCnt[6] = { 1,0,1,1,1,1 };
vector<vector<int>> board(3001, vector<int>(3001, 0));
vector<vector<bool>> found(3001, vector<bool>(3001, false));
vector<vector<pair<int, int>>> parent(3001, vector<pair<int, int>>(3001));

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int a, b;
	cin >> a >> b;
	pair<int, int> start, end;

	int row = 1500;
	int col = 1500;
	board[row][col] = 1;
	if (a == 1) start = { row,col };
	int dir = 0;
	int cnt = 0;
	for (int i = 2; i <= 1000000;) {
		if (cnt == moveCnt[dir]) {
			moveCnt[dir]++;
			dir = (dir + 1) % 6;
			cnt = 0;
			continue;
		}
		row += dRow[dir];
		col += dCol[dir];
		board[row][col] = i;
		if (a == i) start = { row,col };
		cnt++;
		i++;
	}

	queue<pair<int, int>> q;
	q.push(start);
	found[start.first][start.second] = true;
	parent[start.first][start.second] = start;
	while (!q.empty()) {
		auto curr = q.front();
		q.pop();
		if (board[curr.first][curr.second] == b) {
			end = { curr.first, curr.second };
			break;
		}
		for (int i = 0; i < 6; i++) {
			int nextRow = curr.first + dRow[i];
			int nextCol = curr.second + dCol[i];
			if (nextRow < 0 || nextRow > 3000) continue;
			if (nextCol < 0 || nextCol > 3000) continue;
			if (found[nextRow][nextCol]) continue;
			found[nextRow][nextCol] = true;
			parent[nextRow][nextCol] = curr;
			q.push({ nextRow, nextCol });
		}
	}
	vector<int> ans;

	pair<int, int> curr = end;
	pair<int, int> prt = parent[end.first][end.second];
	while (curr != prt) {
		ans.push_back(board[curr.first][curr.second]);
		curr = prt;
		prt = parent[curr.first][curr.second];
	}
	ans.push_back(board[start.first][start.second]);
	for (int i = ans.size() - 1; i >= 0; i--) {
		cout << ans[i] << " ";
	}
};