[백준][1938][c++] 통나무 옮기기

[통나무 옮기기 문제 링크]

[문제 풀이]
상하좌우로 움직이는 것을 구현하는 것이 전형적인 BFS문제중 일부이다. 하지만 회전하는 것은 중간 위치에 있는 통나무를 기준으로 3x3 내에 덜자른 나무가 있으면 안된다는 조건이 붙어 있다.

통나무라는 구조체를 선언해서 middle 좌표랑 middle 양 옆에 있는 것들의 좌표를 각각 저장했다. 이 BFS가 복잡해지는 것을 방지하기 위해 구조체 안에서 상하좌우, 회전 함수를 선언했다. middle을 중심으로 양옆이 좌우 이면 상하로 상하 이면 좌우로 움직이도록 회전함수를 하드코딩 했다. 또한 중복 검사를 위해 map을 사용했고 overriding을 하였다. 나머지는 BFS랑 동일하다.

( 카카오 블라인드 코딩 문제인 블록움직이기랑 비슷하다는 느낌을 받았고 아래 코드를 많이 참고했다.
https://yjyoon-dev.github.io/kakao/2021/01/14/kakao-moveblock/ )

[코드]

#include <iostream>
#include <queue>
#include <string>
#include <map>
#define N_MAX 51

using namespace std;

int N;
char info[N_MAX][N_MAX];
int dir_y[4] = { 0,1,0,-1 };
int dir_x[4] = { 1,0,-1,0 };

struct coordi {
	int y;
	int x;
};

bool check_range(int y, int x) {
	if (y < 0 || y >= N || x < 0 || x >= N) return false;
	return true;
}

int get_dir(int y, int x, int y_other, int x_other) {
	//middle에 대해서 side가 어떤 방향에 있는지 알려주는 함수
	for (int dir = 0; dir < 4; dir++) {
		if (y + dir_y[dir] == y_other && x + dir_x[dir] == x_other) return dir;
	}
	return -1;
}

bool check_box(int y, int x) {
	//middle을 중심으로 3x3내에 잘리다 만 나무가 있는지 확인하는 함수
	int y_low = y - 1;
	int x_low = x - 1;
	int y_high = y + 1;
	int x_high = x + 1;
	if (x_low < 0 || x_low >= N || y_low < 0 || y_low >= N || x_high < 0 || x_high >= N || y_high < 0 || y_high >= N) return false;
	for (int y = y_low; y <= y_high; y++) {
		for (int x = x_low; x <= x_high; x++) {
			if (info[y][x] == '1') return false;
		}
	}
	return true;
}

struct namu {
	coordi middle; //가운데 있는 통나무
	coordi side1; //가운데를 기준으로 양옆 중 하나
	coordi side2; //가운데를 기준으로 양옆 중 하나
	int cost = 0; //시작을 기준으로 얼마나 움직였는지
	bool live = true; //이것 valid한 namu인지

	namu move_dir(int dir) {
		//상하좌우로 움직이는 함수
		namu new_name;
		new_name.middle.y = middle.y + dir_y[dir];
		new_name.middle.x = middle.x + dir_x[dir];
		if (!check_range(new_name.middle.y, new_name.middle.x) || info[new_name.middle.y][new_name.middle.x] == '1') {
			new_name.live = false;
			return new_name;
		}
		new_name.side1.y = side1.y + dir_y[dir];
		new_name.side1.x = side1.x + dir_x[dir];
		if (!check_range(new_name.side1.y, new_name.side1.x) || info[new_name.side1.y][new_name.side1.x] == '1') {
			new_name.live = false;
			return new_name;
		}
		new_name.side2.y = side2.y + dir_y[dir];
		new_name.side2.x = side2.x + dir_x[dir];
		if (!check_range(new_name.side2.y, new_name.side2.x) || info[new_name.side2.y][new_name.side2.x] == '1') {
			new_name.live = false;
			return new_name;
		}
		return new_name;
	}

	namu turn() {
		//회전한 함수
		namu new_namu;
		if (!check_box(middle.y, middle.x)) {
			new_namu.live = false;
			return new_namu;
		}
		//상하면 좌우로, 좌우면 상하로 바꿔주는 역할
		new_namu.middle.y = middle.y;
		new_namu.middle.x = middle.x;
		int returned_dir = get_dir(middle.y, middle.x, side1.y, side1.x);
		returned_dir++;
		if (returned_dir > 3) returned_dir = 0;
		new_namu.side1.y = middle.y + dir_y[returned_dir];
		new_namu.side1.x = middle.x + dir_x[returned_dir];

		returned_dir = get_dir(middle.y, middle.x, side2.y, side2.x);
		returned_dir++;
		if (returned_dir > 3) returned_dir = 0;
		new_namu.side2.y = middle.y + dir_y[returned_dir];
		new_namu.side2.x = middle.x + dir_x[returned_dir];
		return new_namu;

	}
};


map<namu, int> dist;
queue<namu> q;

bool operator < (const namu& a, const namu& b) {
	return tie(a.middle.y, a.middle.x, a.side1.y, a.side1.x, a.side2.y, a.side2.x) < tie(b.middle.y, b.middle.x, b.side1.y, b.side1.x, b.side2.y, b.side2.x);
}

bool operator == (const namu& a, const namu& b) {
	//namu를 비교할 때 side1과 side2가 정렬이 안 되어 있기 때문에 side1 == side1, side2 == side2인지 아님 side1== side2, side2 == side1인지 확인해주는 함수
	if (a.middle.y == b.middle.y && a.middle.x == b.middle.x) {
		if (a.side1.y == b.side1.y && a.side1.x == b.side1.x) {
			if (a.side2.y == b.side2.y && a.side2.x == b.side2.x) {
				return true;
			}
		}
		else if (a.side1.y == b.side2.y && a.side1.x == b.side2.x) {
			if (a.side2.y == b.side1.y && a.side2.x == b.side1.x) {
				return true;
			}
		}
	}
	return false;
}

int bfs(namu start) {
	int ans = 0;
	dist[start]++;
	q.push(start);
	while (!q.empty()) {
		namu cur = q.front();
		q.pop();
		int cur_cost = cur.cost;
		if (info[cur.middle.y][cur.middle.x] == 'E' && info[cur.side1.y][cur.side1.x] == 'E' && info[cur.side2.y][cur.side2.x] == 'E') {
			//통나무가 EEE위치로 옮겨졌는지 확인
			return cur_cost;
		}
		for (int dir = 0; dir < 4; dir++) {
			//상하좌우 
			namu new_namu = cur.move_dir(dir);
			if (!new_namu.live) continue;
			dist[new_namu] ++;
			if (dist[new_namu] > 1) continue;
			new_namu.cost = cur_cost + 1;
			q.push(new_namu);
		}
		//회전
		namu new_namu = cur.turn();
		if (!new_namu.live) continue;
		dist[new_namu]++;
		if (dist[new_namu] > 1) continue;
		new_namu.cost = cur_cost + 1;
		q.push(new_namu);

	}
	return ans;
}

int main() {
	cin >> N;
	string str;
	namu start;
	int count = 0;
	for (int y = 0; y < N; y++) {
		cin >> str;
		for (int x = 0; x < N; x++) {
			info[y][x] = str[x];
			if (info[y][x] == 'B' && count == 0) {
				count++;
				start.side1.y = y;
				start.side1.x = x;
			}
			else if (info[y][x] == 'B' && count == 1) {
				count++;
				start.middle.y = y;
				start.middle.x = x;
			}
			else if (info[y][x] == 'B' && count == 2) {
				count++;
				start.side2.y = y;
				start.side2.x = x;
			}
		}
	}

	int ans = bfs(start);
	cout << ans << "\n";
}

[총평]
map overriding만 잘 해결하면 되는 것!