[C++] BOJ 1938 - 통나무 옮기기

 

 

BOJ 1938 - 통나무 옮기기 (https://www.acmicpc.net/problem/1938)

 

01. 🔎 문제 탐색

N: NxN크기의 평지 $(4 \leq N \leq 50)$
(N개의 줄에는 각 칸의 상태{0: 빈 칸, 1: 나무, B: 통나무, E: 목적지}가 주어짐)

통나무(B)와 목적지(E)는 항상 연속적으로 3개가 놓임 (BBB가 1개, EEE가 1개)
통나무와 목적지는 대각선으로 놓일 수 없으며, 항상 x축이나 y축과 평행함

통나무는 상, 하, 좌, 우, 90도 회전 과 같이 5가지 행동을 할 수 있음
(행동 반경에 나무(1)가 존재할 경우, 이동/회전 할 수 없음)

• 통나무를 5가지 행동으로 목적지까지 이동시키되, 최소 동작 횟수를 출력

01-1. 알고리즘 선택 & 시간 복잡도

• 통나무를 목적지까지 이동시키기 위한 최소 동작을 묻는 문제로, BFS를 활용할 수 있다.
  (단, 연속된 B(통나무)는 함께 움직이므로 이를 고려하여 구현되어야 함)
• 각 칸에 대해 행동 5회를 탐색하게 되므로, 최악의 경우 50*50*5 약12,500 회 연산을 가지게 됨
  이를 시간 복잡도로 나타내면 $O(N^2)$로 2초 내에 충분히 가능

02. 📝 코드 설계하기

1. 평지에 대한 정보를 입력 (N과 {0: 빈 칸, 1: 나무, B: 통나무, E: 목적지})
2. B와 E의 중앙점 위치와 상태(가로/세로)를 각각 저장
3. 통나무의 위치를 B의 중앙점을 기준으로 가로, 세로 상태로 각각 BFS 탐색
   1. 통나무가 세로일 경우, 각 B의 y 값이 서로 같으므로 $x \pm 1$ 에 대해서 유효한지 확인하여 이동
   2. 통나무가 가로일 경우, 각 B의 x 값이 서로 같으므로 $y \pm 1$ 에 대해서 유효한지 확인하여 이동
   3. 통나무를 회전해야 할 경우, 중앙점을 기준으로 주변(8방향)을 탐색하여, 평지를 나가지 않고 나무가 없는 경우에만 회전
   4. 위의 규칙을 따라 통나무를 이동시키며, 이동 1회당 현재 위치와 방향에 따라 횟수를 누적
4. 탐색이 끝나고, 목적지의 중앙점 위치와 방향(가로/세로)에 누적된 횟수를 출력

03. 🛠️ 시도별 수정

1회차

• 진짜 너무 멍청하게 틀렸다.. 습관적으로 참조변수를 사용했는데, queue에서 제거한 요소를 참조 중인 모습이다..

2회차

---

04. 🗝️ 정답 코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pos;
#define X first
#define Y second

int N;
string board[51];
int cost[51][51][2];
bool visited[51][51][2];

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

const int ax[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int ay[8] = {-1, 0, 1, 1, 1, 0, -1, -1};


bool is_valid(int x, int y){
  return (x >= 0 && x < N && y >= 0 && y < N && board[x][y] != '1');
}

bool check_around(int x, int y){
  for(int i = 0; i < 8; i++)
    if(!is_valid(x+ax[i], y+ay[i])) return false;
  return true;
}

int solution(vector<pos> loc, vector<pos> goal){
  queue<tuple<int, int, int>> q;

  int init_dir;
  if(loc[0].X == loc[2].X) init_dir = 1;
  else if(loc[0].Y == loc[2].Y) init_dir = 0;
  int goal_dir;
  if(goal[0].X == goal[2].X) goal_dir = 1;
  else if(goal[0].Y == goal[2].Y) goal_dir = 0;

  q.emplace(loc[1].X, loc[1].Y, init_dir);
  visited[loc[1].X][loc[1].Y][init_dir] = true;
  cost[loc[1].X][loc[1].Y][init_dir] = 0;

  while(!q.empty()){
    auto [x, y, dir] = q.front(); q.pop();

    if(goal[1].X == x && goal[1].Y == y && dir == goal_dir)
      return cost[goal[1].X][goal[1].Y][goal_dir];
    
    for(int i = 0; i < 4; i++){
      int nx = x + dx[i], ny = y + dy[i];

      if(dir == 0){
        if(!(is_valid(nx, ny) && is_valid(nx-1, ny) && is_valid(nx+1, ny))) continue;
        if(visited[nx][ny][dir]) continue;

        visited[nx][ny][dir] = true;
        cost[nx][ny][dir] = cost[x][y][dir] + 1;
        q.emplace(nx, ny, dir);
      }
      else{
        if(!(is_valid(nx, ny) && is_valid(nx, ny-1) && is_valid(nx, ny+1))) continue;
        if(visited[nx][ny][dir]) continue;

        visited[nx][ny][dir] = true;
        cost[nx][ny][dir] = cost[x][y][dir] + 1;
        q.emplace(nx, ny, dir);
      }
    }

    // Rotate
    int nxt_dir = (dir + 1) % 2;
    if(check_around(x, y) && !visited[x][y][nxt_dir]){
      visited[x][y][nxt_dir] = true;
      cost[x][y][nxt_dir] = cost[x][y][dir] + 1;

      q.emplace(x, y, nxt_dir);
    }
  }

  return 0;
}

int main(){
  cin.tie(0)->sync_with_stdio(0);

  cin >> N;
  vector<pos> loc;
  vector<pos> goal;

  for(int i = 0; i < N; i++){
    cin >> board[i];
    for(int j = 0;j < N; j++){
      if(board[i][j] == 'B') loc.emplace_back(i, j);
      else if(board[i][j] == 'E') goal.emplace_back(i, j);
    }
  }

  cout << solution(loc, goal) << "\n";

  return 0;
}