https://www.acmicpc.net/problem/1938
좀 까다로운 문제였습니다. 회전과 서로 길이가 3개인 녀석을 움직여야하니 구현하기가 좀 까다롭습니다.
저는 BFS를 사용하여 문제를 해결했습니다.
3좌표 모두 사용하지 않고 가운데 좌표만 사용했고, BFS 시 사용하는 check 배열을 3차원으로 만들어서
ch[방향][x][y]로 체크했습니다.
나머지는 가능 여부에 따라 통나무를 움직였습니다.
#include <iostream>
#include <queue>
using namespace std;
//2132
int n;
char map[51][51];
int ch[2][51][51];
struct Info {
int x;
int y;
int dir;//0가로1세로
};
queue < Info > q;
int ex, ey, ed;//E의 중앙x,y,d
int dx[] = { -1,1,0,0,-1,-1,1,1 };
int dy[] = { 0,0,-1,1,-1,1,1,-1 };
bool bfs() {
int cnt = -1;
while (!q.empty()) {
int size = q.size();
cnt++;
for (int t = 0; t < size; t++) {
int x = q.front().x;
int y = q.front().y;
int dir = q.front().dir;
q.pop();
if (x == ex && y == ey && dir == ed) {//만났으면
cout << cnt;
return true;
}
for (int i = 0; i < 4; i++) {//상하좌우
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < n&&ny < n&&map[nx][ny] == '0') {
if (dir == 0) {//가로
if (map[nx][ny + 1] == '0'&&map[nx][ny - 1] == '0'
&&ch[0][nx][ny] == false) {
q.push({ nx,ny,0 });
ch[0][nx][ny] = true;
}
}
else {//세로
if (map[nx + 1][ny] == '0'&&map[nx - 1][ny] == '0'
&&ch[1][nx][ny] == false) {
q.push({ nx,ny,1 });
ch[1][nx][ny] = true;
}
}
}
}
bool canRotate = true;
for (int i = 0; i < 8; i++) {//회전가능여부 판단
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || ny < 0 || nx >= n || ny >= n || map[nx][ny] != '0') {
canRotate = false;
break;
}
}
//회전구현
if (canRotate) {
if (dir == 0) {//가로->세로
if (ch[1][x][y] || x <= 0 || x >= n - 1)continue;
q.push({ x,y,1 });
ch[1][x][y] = true;
}
else {//세로->가로
if (ch[0][x][y] || y <= 0 || y >= n - 1)continue;
q.push({ x,y,0 });
ch[0][x][y] = true;
}
}
}
}
return false;//결국 못 만났으면
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
int bcnt = 0;
int ecnt = 0;
int tbx = 0;
int tex = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> map[i][j];
if (map[i][j] == 'B') {
map[i][j] = '0';
bcnt++;
if (bcnt == 2) {//B의 가운데 좌표와 방향 저장
if (tbx == i) {
q.push({ i,j,0 });
ch[0][i][j] = true;
}
else {
q.push({ i,j,1 });
ch[1][i][j] = true;
}
}
tbx = i;
}
else if (map[i][j] == 'E') {//E의 가운데 좌표와 방향 저장
map[i][j] = '0';
ecnt++;
if (ecnt == 2) {
ex = i;
ey = j;
if (tex == i) ed = 0;
else ed = 1;
}
tex = i;
}
}
}
if(!bfs()) cout << '0';
}
- 나 혼자 말하고 나 혼자 듣는 말
….