1938_통나무 옮기기

sol : 58' 35''

• 수행 시간 : 0ms
• 메모리 : 2044KB

Learnings

• BFS의 본질적인 기능에 대해 훨씬 추상적으로 이해할 수 있게 됐다.
• 골드2라기엔 생각보다 너무 쉽게 풀었는데.. 내가 그만큼 발전했다고 생각하자 :)

#include <iostream>
#include <utility>
#include <tuple>
#include <queue>

using namespace std;

#define MAX_N 50
#define EMPTY 0
#define TREE 1
#define B 2
#define E 3

const int HORIZONTAL = 0;
const int VERTICAL = 1;
const int ds[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

int n;
string s;
int grid[MAX_N][MAX_N];
bool visited[MAX_N][MAX_N][2];

void InitVisited() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < 2; k++) {
				visited[i][j][k] = false;
			}
		}
	}
}

struct Tree {
	int ci;
	int cj;
	int dir;

	Tree() {}
	Tree(int _ci, int _cj, int _dir) :
		ci(_ci), cj(_cj), dir(_dir) {
	}
};

Tree beginT = Tree(-1, -1, -1);
Tree endT = Tree(-1, -1, -1);

void Init() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> s;
		for (int j = 0; j < n; j++) {
			if (s[j] == 'B') {
				// is first found
				if (beginT.ci == -1) {
					// is horizontal
					if (j < n - 2 && s[j + 1] == 'B') {
						beginT = Tree(i, j + 1, HORIZONTAL);
					}
					else {
						beginT = Tree(i + 1, j, VERTICAL);
					}
				}
				grid[i][j] = B;
			}
			else if (s[j] == 'E') {
				if (endT.ci == -1) {
					// is horizontal
					if (j < n - 2 && s[j + 1] == 'E') {
						endT = Tree(i, j + 1, HORIZONTAL);
					}
					else {
						endT = Tree(i + 1, j, VERTICAL);
					}
				}
				grid[i][j] = E;
			}
			else if (s[j] == '0') grid[i][j] = EMPTY;
			else if (s[j] == '1') grid[i][j] = TREE;
		}
	}
}

bool InGrid(int ci, int cj, int dir) {
	if (dir == HORIZONTAL) {
		if (ci < 0 || ci >= n) return false;
		if (cj < 0 || cj >= n) return false;
		if (cj - 1 < 0 || cj - 1 >= n) return false;
		if (cj + 1 < 0 || cj + 1 >= n) return false;
	}
	else if (dir == VERTICAL) {
		if (cj < 0 || cj >= n) return false;
		if (ci < 0 || ci >= n) return false;
		if (ci - 1 < 0 || ci - 1 >= n) return false;
		if (ci + 1 < 0 || ci + 1 >= n) return false;
	}
	return true;
}

bool LineMoveEmpty(int ci, int cj, int dir) {
	if (dir == HORIZONTAL) {
		if (grid[ci][cj - 1] == TREE || grid[ci][cj] == TREE || grid[ci][cj + 1] == TREE) return false;
	}
	else if (dir == VERTICAL) {
		if (grid[ci - 1][cj] == TREE || grid[ci][cj] == TREE || grid[ci + 1][cj] == TREE) return false;
	}
	return true;
}

bool RotateEmpty(int ci, int cj) {
	for (int i = -1; i <= 1; i++) {
		for (int j = -1; j <= 1; j++) {
			if (grid[ci + i][cj + j] == TREE) return false;
		}
	}
	return true;
}

void Simulate() {
	// i, j, dir, operated_num
	queue<tuple<int, int, int, int>> q;
	q.push({ beginT.ci, beginT.cj, beginT.dir, 0 });

	visited[beginT.ci][beginT.cj][beginT.dir] = true;
	while (!q.empty()) {
		int ci, cj, cd, coNum;
		tie(ci, cj, cd, coNum) = q.front();
		q.pop();

		if (ci == endT.ci && cj == endT.cj && cd == endT.dir) {
			cout << coNum;
			return;
		}

		// 상하좌우 이동
		for (int op = 0; op < 4; op++) {
			int ni = ci + ds[op][0], nj = cj + ds[op][1];
			if (InGrid(ni, nj, cd) && !visited[ni][nj][cd] && LineMoveEmpty(ni, nj, cd)) {
				q.push({ ni, nj, cd, coNum + 1 });
				visited[ni][nj][cd] = true;
			}
		}

		// 회전
		int nd = (cd + 1) % 2;
		if (InGrid(ci, cj, nd) && !visited[ci][cj][nd] && RotateEmpty(ci, cj)) {
			q.push({ ci, cj, nd, coNum + 1 });
			visited[ci][cj][nd] = true;
		}
	}

	cout << 0;
	return;
}

int main() {
	Init();

	Simulate();

	return 0;
}