[BAE/<JOON> 문제풀이] 1938. 통나무 옮기기

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

1938번: 통나무 옮기기

서론

정석적인 탐색 문제다. 2020년 카카오 블라인드 7번 문제랑 좀 비슷한 것 같긴 하다. 이게 골드2 문제가 맞나 ? 그래프 태그만 있는 문제들은 티어에 비해 너무 쉽다.

---

풀이

구현만 잘하면 된다. 통나무 위치는 중간 부분을 기준으로 삼는게 여러모로 편했다.

통나무 4방향으로 옮기고 돌리는 작업 총 5가지 작업을 반복하며 BFS로 탐색하면 된다.

돌릴 때 통나무를 포함하는 9개 칸을 모두 확인해야 한다.

방향에 따라 같은 위치에서 확인해야 하는 횟수는 총 2개이다.

같은 횟수로 같은 상태 / 같은 위치에 도착했다면 그 탐색은 유지할 필요가 없다.

이 정도만 지키면 풀린다.

---

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <string>
#include <list>
using namespace std;
using ll = long long;
struct pa {
	ll sum, cnt;
};
struct pos {
	short x, y, s, c = 0;
};
struct cmp {
	bool operator()(pos a, pos b) {
		return a.c > b.c;
	}
};
short mvx[4] = { 0 ,1, 0, -1 };
short mvy[4] = { 1, 0, -1, 0 };
int main() {	
	ios::sync_with_stdio(0); cin.tie(0);
	short n; cin >> n; vector<vector<short>> arr(n + 1, vector<short>(n + 1)); vector<vector<vector<short>>> ch(n + 1, vector<vector<short>>(n + 1, vector<short>(2, 32000)));
	pos s = { -1, -1, 0, 0 }, e = { -1, -1, 0, 0 };
	for (short i = 1; i <= n; i++) {
		string tmp; cin >> tmp;
		for (short j = 1; j <= n; j++) {
			if (tmp[j - 1] == '1') {
				arr[i][j] = 1; 
			}
			if (tmp[j - 1] == 'B') {
				if (s.x < i) {
					s.x = i;
					s.s = 1;
				}
				if (s.y < j) {
					s.y = j;
					s.s = 0;
				}
			}
			if (tmp[j - 1] == 'E') {
				if (e.x < i) {
					e.x = i;
					e.s = 1;
				}
				if (e.y < j) {
					e.y = j;
					e.s = 0;
				}
			}
		}
	}
	if (s.s == 1) {
		s.x--;
	}
	else {
		s.y--;
	}
	if (e.s == 1) {
		e.x--;
	}
	else {
		e.y--;
	}
	priority_queue<pos, vector<pos>, cmp> q; q.push(s); ch[s.x][s.y][s.s] = 0;
	while (!q.empty()) {
		const auto cur = q.top(); q.pop();		
		for (int i = 0; i < 4; i++) {
			short mx = cur.x + mvx[i];
			short my = cur.y + mvy[i];
			if (cur.s == 1) {
				if (mx >= n || my > n || mx <= 1 || my < 1 || arr[mx][my] == 1 || arr[mx - 1][my] == 1 || arr[mx + 1][my] == 1 || ch[mx][my][cur.s] <= cur.c + 1) continue;
			}
			else {
				if (mx > n || my >= n || mx < 1 || my <= 1 || arr[mx][my] == 1 || arr[mx][my - 1] == 1 || arr[mx][my + 1] == 1 || ch[mx][my][cur.s] <= cur.c + 1) continue;
			}			
			if (mx == e.x && my == e.y && cur.s == e.s) {
				cout << cur.c + 1;
				return 0;
			}
			ch[mx][my][cur.s] = cur.c + 1;
			q.push({ mx, my, cur.s, cur.c + 1 });
		}
		short mx = cur.x; short my = cur.y;
		if ((mx >= n || my >= n || mx <= 1 || my <= 1 || ch[mx][my][1 - cur.s] <= cur.c + 1) == false) {
			bool sign = 0;
			for (int i = -1; i <= 1; i++) {
				for (int j = -1; j <= 1; j++) {
					if (arr[mx + i][my + j] == 1) {
						sign = 1; break;
					}
				}
			}
			if (sign == 0) {
				if (mx == e.x && my == e.y && 1 - cur.s == e.s) {
					cout << cur.c + 1;
					return 0;
				}
				ch[mx][my][1 - cur.s] = cur.c + 1;
				q.push({ mx, my, 1 - cur.s, cur.c + 1 });					
			}
		}
	}
	cout << 0;
	return 0;
}