[백준 1938] 통나무 옮기기

[백준 1938] 통나무 옮기기

문제 링크

#include "header.h"
using namespace std;
int N, dir, ans_dir;
char land[54][54];
int visit[54][54][2];
vector <pair<int, int>> b;
vector <pair<int, int>> e;
queue <vector<int>> q;
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
// 범위 벡터
vector <pair<int, int>> ran[2] = {{{-1, 0}, {1, 0}}, {{0, -1}, {0, 1}}}; // 0 : 세로, 1 : 가로
//회전 벡터
vector <pair<int, int>> rot[2] = {{{-1, -1}, {0, -1}, {1, -1}, {-1, 1}, {0, 1}, {1, 1}}, {{-1, -1}, {-1, 0}, {-1, 1}, {1, -1}, {1, 0}, {1, 1}}};

bool range(int x, int y) {
  return (x >= 0 && y >= 0 && x < N && y < N);
}
void input() {
  cin >> N;
  for(int i=0; i<N; i++) {
    for(int j=0; j<N; j++) {
      cin >> land[i][j];
      if(land[i][j] == 'B') {
        b.push_back({i, j});
      } else if(land[i][j] == 'E') {
        e.push_back({i, j});
      }
    }
  }

  if(b[0].first == b[1].first) dir = 1; // 가로
  if(e[0].first == e[1].first) ans_dir = 1;
}

void solve() {

  q.push({b[1].first, b[1].second, dir, 0}); //중심 넣기
  visit[b[1].first][b[1].second][dir] = 1;

  while (!q.empty()){
    int top_x = q.front()[0];
    int top_y = q.front()[1];
    int top_dir = q.front()[2];
    int cnt = q.front()[3];
    q.pop();

    // 도착 했는지 확인
    if(top_x == e[1].first && top_y == e[1].second && ans_dir == top_dir) {
      cout << cnt << endl;
      return;
    }

    // 중심을 움직이기
    for(int i=0; i<4; i++) {
      int nx = top_x + dx[i];
      int ny = top_y + dy[i];
      
      if(visit[nx][ny][top_dir] || land[nx][ny] == '1' || !range(nx, ny)) continue;

      // 범위 체크
      int flag = 1;
      for(int j=0; j<2; j++) {
        int rx = nx + ran[top_dir][j].first;
        int ry = ny + ran[top_dir][j].second;
        if(land[rx][ry] == '1' || !range(rx, ry)) {
          flag = 0;
          break;
        }
      }
      if(!flag) continue;
      q.push({nx, ny, top_dir, cnt + 1});
      visit[nx][ny][top_dir] = 1;

      // 회전 시켜보기
      // 범위 체크
      flag = 1;
      for(int j=0; j<6; j++) {
        int rx = top_x + rot[top_dir][j].first;
        int ry = top_y + rot[top_dir][j].second;
        if(land[rx][ry] == '1' || !range(rx, ry)) {
          flag = 0;
          break;
        }
      }
      if(!flag) continue;
      q.push({top_x, top_y, !top_dir, cnt + 1});
      visit[top_x][top_y][!top_dir] = 1;
    }
  }
  
  cout << 0 << endl;
}
int main() {

  input();
  solve();

  return 0;
}

• bfs문제
• 중심을 옮겨 가면서 진행 했다.
• 큐에 cnt도 함께 넣어주어서 얼마나 움직였는지 세어 준다.
• 중심을 bfs로 움직인다.
  • 움직일 때 마다 통나무의 범위 체크도 해 준다.
• 움직인 이후, 회전도 체크를 해 준다.
  • 이 때 6방향을 체크 해 주어야 한다.
• 만약 통나무의 중심이 E의 중심을 만나면, 방향이 같은지도 체크 해 준다.
• 방향이 같다면 답을 출력 해 준다.