백준 1938 : 통나무 옮기기 c++

www.acmicpc.net/problem/1938

1938번: 통나무 옮기기

풀이

 

1. 통나무 지금 위치랑 목적지를 입력받는다 

 -> 무조건 길이가 3이라고 했으니까 bb[1], ee[1]가 센터다

 

2. 기본적인 BFS인데 조오금 복잡하다

 -> 상하좌우로 움직이는거는 기존이랑 동일하게!! 다만 방향고려해서 양 끝에도 나무 없는지 추가 확인해야된다

 -> 회전을 추가! 

 

3. 여기서 입력은 char 로 받으니까 나무 위치 비교할때 '1'인거 주의!!!!!!!

ex)

 

구현 필요

 

1. wood 구조를 만든다

 -> 센터 위치랑 가로 세로 여부 판단

 -> way  0: 가로 1: 세로

 

2. 회전 가능 여부

 -> 센터를 주위로 3X3 배열 구현

 

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

struct wood {
	pair<int, int> center;
	int way;
};

int d_r[4] = { 1,-1,0,0 };
int d_c[4] = { 0,0,1,-1 };//아래 위 오른 왼

int n;
char map[51][51];
int visited[51][51][2];//센터 기준!! 가로, 세로
vector<pair<int, int> > bb;
vector<pair<int, int> > ee;
wood me;
int answer = 987654321;
int ee_way;

bool spin(pair<int,int> a)//돌릴수 있는지 확인 여부
{
	for (int i = -1; i <= 1; i++)
	{
		for (int j = -1; j <= 1; j++)
		{
			int new_r = a.first + i;
			int new_c = a.second + j;

			if (new_r < 0 || new_c < 0 || new_r >= n || new_c >= n)
				return false;

			if (map[new_r][new_c] == '1')
				return false;
		}
	}
	return true;
}


int main(int argc, char** argv)
{
	cin >> n;
	for(int i=0;i<n;i++)
		for (int j = 0; j < n; j++)
		{
			cin >> map[i][j];
			if (map[i][j] == 'B')
				bb.push_back(make_pair(i, j));
			if (map[i][j] == 'E')
				ee.push_back(make_pair(i, j));
		}

	me.center = bb[1];

	if (bb[0].first == bb[1].first)
		me.way = 0;//가로
	else
		me.way = 1;//세로

	if (ee[0].first == ee[1].first)
		ee_way = 0;//가로
	else
		ee_way = 1;//세로

	
	queue<wood> q;
	q.push(me);
	visited[me.center.first][me.center.second][me.way] = 1;

	int result = 0;
	while (!q.empty())
	{
		int s = q.size();
		for (int g = 0; g < s; g++)
		{
			wood a = q.front();
			wood b;
			q.pop();
			if (a.center.first == ee[1].first && a.center.second == ee[1].second)
			{
				if(a.way ==ee_way)//방향까지 같아야됨
					answer = min(answer, result);
			}

			for (int i = 0; i < 4; i++)
			{
				int new_r = a.center.first + d_r[i];
				int new_c = a.center.second + d_c[i];

				if (new_r < 0 || new_c < 0 || new_r >= n || new_c >= n)
					continue;

				if (visited[new_r][new_c][a.way] == 1)
					continue;
				if (map[new_r][new_c] == '1')
					continue;

				if (a.way == 0)//가로
				{
					if (new_c - 1 < 0 || new_c + 1 >= n)//지도 밖으로 나가면
						continue;
					if (map[new_r][new_c-1] == '1' || map[new_r][new_c+1] == '1')//나무 있으면
						continue;

					visited[new_r][new_c][a.way] = 1;

					b.center.first = new_r;
					b.center.second = new_c;
					b.way = a.way;
					q.push(b);
				}
				else if (a.way == 1)//세로
				{
					if (new_r - 1 < 0 || new_r + 1 >= n)//지도 밖으로 나가면
						continue;
					if (map[new_r-1][new_c] == '1' || map[new_r+1][new_c] == '1')//나무 있으면
						continue;

					visited[new_r][new_c][a.way] = 1;

					b.center.first = new_r;
					b.center.second = new_c;
					b.way = a.way;
					q.push(b);
				}
			}

			if (spin(a.center) == true)//돌리기 가능
			{
				if (visited[a.center.first][a.center.second][(a.way + 1) % 2] == 0)
				{
					visited[a.center.first][a.center.second][(a.way + 1) % 2] = 1;
					b.center.first = a.center.first;
					b.center.second = a.center.second;
					b.way = (a.way + 1) % 2;
					q.push(b);
				}
			}
		}
		result++;
	}

	if (answer == 987654321)
		answer = 0;

	cout << answer << endl;
	return 0;
}