[백준/BOJ] 백준 1938번 : 통나무 옮기기

www.acmicpc.net/problem/1938

1938번: 통나무 옮기기

discovered와 depth를 discovered[50][50][2]; //[중간의 x][중간의 y][0:가로 1:세로], depth[50][50][2]; //[중간의 x][중간의 y][0:가로 1:세로]로 표현하여 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <string>
#include <queue>
using namespace std;

int n;
int board[50][50];
vector<pair<int, int>> tree;
vector<pair<int, int>> dest;
int discovered[50][50][2]; //[중간의 x][중간의 y][0:가로 1:세로]
int depth[50][50][2]; //[중간의 x][중간의 y][0:가로 1:세로]
int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };

void Pre()
{
	for (int i = 0; i < 50; i++)
		for (int j = 0; j < 50; j++)
		{
			board[i][j] = 0;

			for (int k = 0; k < 2; k++)
				discovered[i][j][k] = 0;
		}
}

bool Can_there(pair<int, int> tree_mid, int dir)
{
	if (dir == 0) //가로
	{
		if (board[tree_mid.first][tree_mid.second - 1] == 0 && board[tree_mid.first][tree_mid.second] == 0 && board[tree_mid.first][tree_mid.second + 1] == 0)
			return true;
	}

	else //세로
	{
		if (board[tree_mid.first - 1][tree_mid.second] == 0 && board[tree_mid.first][tree_mid.second] == 0 && board[tree_mid.first + 1][tree_mid.second] == 0)
			return true;
	}

	return false;
}

//회전할 수 있는지 확인
bool Can_turn(pair<int, int> tree_mid, int dir)
{
	if (dir == 0) //가로 방향
	{
		//행의 양 끝일때
		if (tree_mid.first == 0 || tree_mid.first == n - 1)
			return false;

		if (board[tree_mid.first - 1][tree_mid.second - 1] == 0 && board[tree_mid.first - 1][tree_mid.second] == 0 && board[tree_mid.first - 1][tree_mid.second + 1] == 0)
			if (board[tree_mid.first + 1][tree_mid.second - 1] == 0 && board[tree_mid.first + 1][tree_mid.second] == 0 && board[tree_mid.first + 1][tree_mid.second + 1] == 0)
				return true;
	}

	else //세로 방향
	{
		//열의 양 끝일때
		if (tree_mid.second == 0 || tree_mid.second == n - 1)
			return false;

		if (board[tree_mid.first - 1][tree_mid.second - 1] == 0 && board[tree_mid.first][tree_mid.second - 1] == 0 && board[tree_mid.first + 1][tree_mid.second - 1] == 0)
			if (board[tree_mid.first - 1][tree_mid.second + 1] == 0 && board[tree_mid.first][tree_mid.second + 1] == 0 && board[tree_mid.first + 1][tree_mid.second + 1] == 0)
				return true;
	}

	return false;
}

bool Finish(pair<int, int> tree_mid, int dir)
{
	vector<pair<int, int>> check_tree;

	check_tree.push_back(tree_mid);
	if (dir == 0)
	{
		check_tree.push_back(make_pair(tree_mid.first, tree_mid.second - 1));
		check_tree.push_back(make_pair(tree_mid.first, tree_mid.second + 1));
	}

	else
	{
		check_tree.push_back(make_pair(tree_mid.first - 1, tree_mid.second));
		check_tree.push_back(make_pair(tree_mid.first + 1, tree_mid.second));
	}

	sort(check_tree.begin(), check_tree.end());
	sort(dest.begin(), dest.end());

	//최종 위치일때
	if (check_tree == dest)
		return true;

	return false;
}

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

	Pre();

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		string input;
		cin >> input;

		for (int j = 0; j < n; j++)
		{
			if (input[j] == '1')
				board[i][j] = 1;

			if (input[j] == 'B')
			{
				tree.push_back(make_pair(i, j));
			}

			if (input[j] == 'E')
			{
				dest.push_back(make_pair(i, j));
			}
		}
	}

	sort(tree.begin(), tree.end());
	pair<int, int> tree_mid = tree[1]; //나무의 가운데 위치
	int dir; // 0:가로 1:세로

	if (tree[0].first == tree[1].first)//행이 같을때 (가로 방향일때)
		dir = 0;
	else //(세로 방향일때)
		dir = 1;

	queue<pair<pair<int, int>, int>> q;

	discovered[tree_mid.first][tree_mid.second][dir] = 1;
	depth[tree_mid.first][tree_mid.second][dir] = 0;
	q.push(make_pair(tree_mid, dir));

	while (!q.empty())
	{
		pair<pair<int, int>, int> here = q.front();
		pair<int, int> here_xy = here.first;
		int here_dir = here.second;
		q.pop();

		//최종위치에 도착했을때
		if (Finish(here_xy, here_dir))
		{
			cout << depth[here_xy.first][here_xy.second][here_dir];
			return 0;
		}

		for (int i = 0; i < 4; i++)
		{
			pair<int, int> there_xy = make_pair(here_xy.first + dxdy[i][0], here_xy.second + dxdy[i][1]);

			if (here_dir == 0) //가로 방향일때
			{
				if (there_xy.first < 0 || there_xy.first >= n)
					continue;

				if (there_xy.second - 1 < 0 || there_xy.second + 1 >= n)
					continue;
			}

			else //세로 방향일때
			{
				if (there_xy.second < 0 || there_xy.second >= n)
					continue;

				if (there_xy.first - 1 < 0 || there_xy.first + 1 >= n)
					continue;
			}

			//there로 갈 수 없을때
			if (Can_there(there_xy, here_dir) == false)
				continue;

			if (discovered[there_xy.first][there_xy.second][here_dir] == 1)
				continue;

			discovered[there_xy.first][there_xy.second][here_dir] = 1;
			depth[there_xy.first][there_xy.second][here_dir] = depth[here_xy.first][here_xy.second][here_dir] + 1;
			q.push(make_pair(there_xy, here_dir));
		}

		if (Can_turn(here_xy, here_dir)) //회전할 수 있을때
		{
			int there_dir;

			if (here_dir == 0)
				there_dir = 1;
			else
				there_dir = 0;

			if (discovered[here_xy.first][here_xy.second][there_dir] == 0)
			{
				discovered[here_xy.first][here_xy.second][there_dir] = 1;
				depth[here_xy.first][here_xy.second][there_dir] = depth[here_xy.first][here_xy.second][here_dir] + 1;
				q.push(make_pair(here_xy, there_dir));
			}
		}

	}

	cout << 0;

	return 0;
}