[BOJ/1726/C++] 로봇

출처 : https://www.acmicpc.net/problem/1726

문제

• 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다.

로봇의 이동을 제어하는 명령어는 다음과 같이 두 가지이다.

• 명령 1. Go k: k는 1, 2 또는 3일 수 있다. 현재 향하고 있는 방향으로 k칸 만큼 움직인다.

• 명령 2. Turn dir: dir은 left 또는 right 이며, 각각 왼쪽 또는 오른쪽으로 90° 회전한다.

• 공장 내 궤도가 설치되어 있는 상태가 0과 1로 이루어진 직사각형 모양으로 로봇에게 입력된다. 0은 궤도가 깔려 있어 로봇이 갈 수 있는 지점이고, 1은 궤도가 없어 로봇이 갈 수 없는 지점이다.

조건

• 첫째 줄에 공장 내 궤도 설치 상태를 나타내는 직사각형의 세로 길이 M과 가로 길이 N이 빈칸을 사이에 두고 주어진다.(M과 N은 둘 다 100이하의 자연수)

• 다음 줄에는 로봇의 출발 지점의 위치 (행과 열의 번호)와 바라보는 방향이 빈칸을 사이에 두고 주어진다. 마지막 줄에는 로봇의 도착 지점의 위치 (행과 열의 번호)와 바라보는 방향이 빈칸을 사이에 두고 주어진다.

• 방향은 동쪽이 1, 서쪽이 2, 남쪽이 3, 북쪽이 4로 주어진다. 출발지점에서 도착지점까지는 항상 이동이 가능하다.

풀이

이 문제는 풀이방법을 떠올리는데 오래걸렸다기 보단 다른 지점에서 어려웠던 문제이다.

1. 동서남북의 방향이 평소에 쓰던 한 방향을 기점으로 시계방향 or반시계 방향이 아니였던 점
2. 방향을 틀어서 갔을 때, 더 짧게 도달 할 수 있는 가능성이 있다.
3. 방향을 트는 것 보다는, 먼저 가보는게 이득이긴 하다. (이건 횟수를 줄일 수 있긴 하기 때문)

위와 같이 길찾기 문제에서 조심해야할 게, 풀이를 생각하다보면 최적화의 관점에서 이렇게 가면 당연히 더 빠르게 도달 할 수 있지 않을까 라는 생각을 하게끔 문제를를 볼 수 있다. 하지만, 이 생각을 섣불리 확장시키면 안된다. 즉, 방향을 트는 것보다 먼저 가보는게 이득인건 팩트지만 그렇다고 해당좌표에 먼저 도달할 수 있느냐?는 미지수라는 거다.

그리고, BFS를 쓴다는 의미는 결국 모든 케이스를 둘러보겠다는 의미(완탐)니까, 웬만하면 BFS를 써야겠다 => 어? 시간복잡도 내에 안될 것 같은데.. -> 최적화 이런 생각의 흐름이 자연스러운 것 같다.

방향을 틀어서 갔을 때, 더 짧게 도달 할 수 있는 가능성이 있다는 무슨말임?

문제를 BFS를 통해 푼다는 의미는 2차원배열을 아래와 같이 생각을 해서 탐색한다는 의미이다. 그리고, 노드의 상태는 일정하기 때문에 , BFS로 탐색을 하게되면 최단거리가 당연하게 보장이 된다.

하지만, 여기서 묻는건 노드의 상태변화가 최소가 되는 상황이다. 즉, 해당 좌표까지 가는데 여러가지 방법이 있겠지만 , 최대한 변화를 적게 하면서 가라는 의미이다. BFS로 보장되는 것은 해당 좌표로 최소의 Edge로 간다는 것 밖에 보장이 되지않는다.

그러므로, 상태 변화에 대해서 여러가지 Layer를 만들어서 단순히 넘나드는게 아니라, North -> E -> W 등으로 제자리에서 턴해서 가기도 하고, 가다가 방향을 바꾸는 등의 여러가지 상태 변화를 모두 해볼 필요가 있다. North 층에서, East로 턴한 뒤 가는게 최소한의 상태변화로 도착하게 될 수 있는 가능성을 내포한다는 이야기이다.

그러므로, 3차원 배열을 써서, 여러가지 Layer를 반영해야한다. 동서남북의 순서를 지켜주기 위해서, dx,dy를 위와같이 세웠고 , Turnning을 2번하는 상황은 동->서, 남->북 경우밖에 없기 때문에, (현재보는 방향 + dir)%4 ==1이 되어야 한다.

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;

int N, M;

int sx, sy, sd, ex, ey, ed;

// 동,서,남,북
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

struct Robot
{
  int x;
  int y;
  int head;
};

int board[101][101];
int dist[101][101][4];

bool outOfRange(int x, int y)
{
  return x < 0 || x >= N || y < 0 || y >= M;
}
void bfs()
{
  queue<Robot> Q;
  Q.push({sx - 1, sy - 1, sd - 1});
  while (!Q.empty())
  {
    Robot cur = Q.front();
    Q.pop();
    if (cur.x == ex - 1 && cur.y == ey - 1 && cur.head == ed - 1)
    {
      cout << dist[cur.x][cur.y][cur.head] << '\n';
      return;
    }
    // GoK
    for (int i = 1; i <= 3; i++)
    {
      int nx = cur.x + dx[cur.head] * i;
      int ny = cur.y + dy[cur.head] * i;
      if (outOfRange(nx, ny))
        break;
      if (board[nx][ny])
        break;
      // 해당 지점에 방문을 해봤으면, 더 가본다.
      if (dist[nx][ny][cur.head])
        continue;
      Q.push({nx, ny, cur.head});
      dist[nx][ny][cur.head] = dist[cur.x][cur.y][cur.head] + 1;
    }
    // Tunning Left,Right
    //  90도 회전 -> 180도면 제자리에서 2번 회전.
    //  나머지는 오른쪽이나 왼쪽으로 1번 돌아야함.
    for (int dir = 0; dir < 4; dir++)
    {
      if (dir == cur.head)
        continue; // 현재 보는 방향과 같다면 넘어가고
      int step = (dir + cur.head) % 4 == 1 ? 2 : 1;
      if (dist[cur.x][cur.y][dir])
        continue; // 이미 방문을 했다면, 다른 방향으로 틀어본다.
      Q.push({cur.x, cur.y, dir});
      dist[cur.x][cur.y][dir] = dist[cur.x][cur.y][cur.head] + step;
    }
  }
}

int main()
{
  fastio;
  cin >> N >> M;
  for (int i = 0; i < N; i++)
  {
    for (int j = 0; j < M; j++)
    {
      cin >> board[i][j];
    }
  }
  cin >> sx >> sy >> sd;
  cin >> ex >> ey >> ed;
  bfs();
  return 0;
}

refer : https://rebas.kr/742