[BOJ] 1938 통나무 옮기기

문제: https://www.acmicpc.net/problem/1938

 

문제 풀이:

통나무의 길이는 항상 3이다. 그리고 중심을 기준으로 회전한다.

-> 통나무의 이동, 방문 여부, 거리 계산은 [중심점]과 [가로/세로] 기록하면 된다.

 

 만약 통나무가 세로인 상태라면 

↓: X축  → : Y축

(X-1,Y)

(X,Y)

(X+1,Y)

 

통나무를 회전시키려면, 중심점을 중심으로 두고 주변 3x3 영역에 아무것도 없어야한다.

 

 

소스 코드:

#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#define inf 987654321
using namespace std;


typedef pair<int, int> P;
int n,dist[52][52][2];
char arr[52][52];
vector<P> startP,endP;
bool endRow;
bool visit[52][52][2];

int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };

queue<pair<P,int>> q;

bool check(int x, int y) { // 중심점을 기준으로 3X3에 나무가 없는지 확인
	for (int i = x - 1; i <= x + 1; i++) {
		if (i < 0||i>=n) return false;
		for (int j = y - 1; j <= y + 1; j++) {
			if (j < 0||j>=n) return false;
			if (arr[i][j] == '1') return false;
		}
	}
	return true;
}
void func() {
	P startPos = startP[1];
	bool startRow = false;
	if (startP[0].second == startP[1].second - 1) startRow = true;
	P endPos = endP[1];
	if (endP[0].second == endP[1].second - 1) endRow = true;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			dist[i][j][0] = inf;
			dist[i][j][1] = inf;
		}
	}
	q.push({ startPos,startRow });
	dist[startPos.first][startPos.second][startRow] = 0;
	visit[startPos.first][startPos.second][startRow] = true;
	while (!q.empty()) {
		P cur = q.front().first;
		bool row = q.front().second;
		q.pop();

		if (cur == endP[1] && row == endRow) continue;

		for (int i = 0; i < n; i++) {
			int x = cur.first + dx[i];
			int y = cur.second + dy[i];
			if (row == 0) {
				if(x-1<0||x+1>=n|| y < 0 || y >= n || visit[x][y][row] == 1) continue;
				if (arr[x][y] == '1' || arr[x - 1][y] == '1' || arr[x + 1][y] == '1') continue;
			}
			else {
				if (x < 0 || x >= n || y - 1 < 0 || y + 1 >= n || visit[x][y][row] == 1) continue;
				if (arr[x][y - 1] == '1' || arr[x][y] == '1' || arr[x][y + 1] == '1') continue;
			}

			if (dist[cur.first][cur.second][row] + 1 < dist[x][y][row]) {
				dist[x][y][row] = dist[cur.first][cur.second][row] + 1;
				visit[x][y][row] = true;
				q.push({ { x,y }, row });
			}
		}
		int x = cur.first;
		int y = cur.second;
		if (check(x, y) && !visit[x][y][!row]) {
			if (dist[x][y][row] + 1 < dist[x][y][!row]) {
				dist[x][y][!row] = dist[x][y][row] + 1;
				visit[x][y][!row] = true;
				q.push({ { x,y }, !row });
			}
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 'B') startP.push_back({ i,j });
			if (arr[i][j] == 'E') endP.push_back({ i,j });
		}
	}
	func();
	int res = dist[endP[1].first][endP[1].second][endRow];
	if (res == inf) cout << "0\n";
	else cout << res << '\n';
	return 0;
}