통나무 옮기기

BOJ/C++

통나무 옮기기

IamToday 2020. 2. 29. 19:50

*시뮬레이션

*통나무는 중간에 있는 좌표와 현재 방향(세로/가로)의 상태만 저장한다.

#include <iostream>
#include <vector>
#include <queue>
#define INF 987654321
using namespace std;

typedef pair < int, int > pp;
typedef pair < pp, int > ppi;
typedef pair < pp, pp > pppp;

int n, ans = INF;
char map[51][51];
ppi treeB, treeE;
bool visited[51][51][2];
int dx[4] = { -1,1,0,0 }, dy[4] = { 0,0,-1,1 };
int cdx[8] = { -1,-1,-1,0,0,1,1,1 }, cdy[8] = { -1,0,1,-1,1,-1,0,1 };
bool check(int x, int y, int dir, int n_dir) {
	if (n_dir < 2) {
		//남 북 
		if (dir == 1) {
			
			if (x < 0 || x >= n || y < 0 || y >= n || visited[x][y][dir] ) return false;
			else return true;
		}
		else if (dir == 0) {
			//내 위 아래 인덱스가 빠져나갈 가능성을 생각하낟. 
			if (x <= 0 || x >= n - 1 || y < 0 || y >= n || visited[x][y][dir]) return false;
			else return true;
		}
	}
	else {
		//동서 
		if (dir == 1) {
			if (x < 0 || x >= n || y <= 0 || y >= n-1 || visited[x][y][dir]) return false;
			else return true;
		}
		else if (dir == 0) {
			//내 위 아래 인덱스가 빠져나갈 가능성을 생각하낟. 
			if (x < 0 || x >= n || y < 0 || y >= n || visited[x][y][dir]) return false;
			else return true;
		}
	}
}
void bfs() {
	queue < pppp > q;
	q.push(pppp(pp(0, treeB.second), treeB.first));

visited[treeB.first.first][treeB.first.second][treeB.second] = true;

while (!q.empty())
	{
		int size = q.size();
		while (size--) {
			int x = q.front().second.first;
			int y = q.front().second.second;
			int cnt = q.front().first.first;
			int dir = q.front().first.second;
			q.pop();
			//통나무 중간위치의 좌표 
			//x, y기준으로 가르키는 방향으로 위아래 / 양옆으로 더 있다. 
			//회전할 수 있는 기준은 중간 통나무 기준으로 3*3이 비어있어야 한다.

if (x == treeE.first.first && y == treeE.first.second && dir == treeE.second) {
				ans = min(ans, cnt);
				continue;
			}

for (int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i]; 
				
				if (check(nx, ny, dir, i)) {
					//가는 방향으로 나무가 잇는 지 확인한다. 
					if (dir == 0) {
						if (i == 0) {
							//북 
							//내 위에 위에가 나무인지 확인한다. 
							if (map[nx - 1][ny] == '1') continue;

}
						else if (i == 1) {
							if (map[nx + 1][ny] == '1' ) continue;

}
						else if (i == 2 || i == 3) {
							//서 
							//세 군데 모두 살펴봐야 한다. 
							if (map[nx][ny] == '1' || map[nx-1][ny] == '1' || map[nx + 1][ny] == '1') continue;
						}
					}
					else if (dir == 1) {
						if (i == 0 || i == 1) {
							if (map[nx][ny] == '1' || map[nx][ny - 1] == '1' || map[nx][ny + 1] == '1') continue;

}
						else if (i == 2) {
							//서쪽 
							if (map[nx][ny - 1] == '1') continue;
						}
						else if (i == 3) {
							if (map[nx][ny + 1] == '1') continue;
						}
					}
					
					// 모두 통과한 경우 
					visited[nx][ny][dir] = true;
					q.push(pppp(pp(cnt + 1, dir), pp(nx, ny)));
				}

}
			//방향전환 
			//3*3안에 아무것도 없어야 한다. 
			bool flag = true;
			for (int i = 0; i < 8; i++) {
				int nx = x + cdx[i];
				int ny = y + cdy[i];

if (nx < 0 || nx >= n || ny < 0 || ny >= n || map[nx][ny] == '1') {
					flag = false;
					break;
				}
			}
			if (flag) {
				int n_dir = 1 - dir;
		
				if (visited[x][y][n_dir]) continue;
				visited[x][y][n_dir] = true;
				q.push(pppp(pp(cnt + 1, n_dir), pp(x, y)));
			}
		}
	}
}
int main() 
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

//통나무는 중간의 좌표와 방향만 저장한다.

cin >> n;
	bool flagB = false, flagE = false;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		
		for (int j = 0; j < n; j++) {
			map[i][j] = s[j];
		}
	}

for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 'B' && !flagB) {
				if (map[i][j + 1] == 'B') {
					//가로 방향 
					treeB = ppi(pp(i, j+1), 1);
				}
				else if (map[i + 1][j] == 'B') {
					treeB = ppi(pp(i+1, j), 0);
				}
				flagB = true;
			}
			
			if (map[i][j] == 'E' && !flagE) {
				if (map[i][j + 1] == 'E') {
					//가로 방향 
					treeE = ppi(pp(i, j+1), 1);
				}
				else if (map[i + 1][j] == 'E') {
					treeE = ppi(pp(i+1, j), 0);
				}
				flagE = true;
			}
		}
	}
	
	bfs();

if (ans == INF) cout << 0 << '\n';
	else 	cout << ans << '\n';
	return 0;
}