[ 백준 ] 1726 / 로봇

金弘均·2021년 9월 14일
0

Baekjoon Online Judge

목록 보기
14/228
post-thumbnail
post-custom-banner

# Appreciation

/*
 * Problem :: 로봇 / 1726
 *
 * Kind :: BFS
 *
 * Insight
 * - 필요한 최소 명령 횟수는
 *   최소 비용 또는 최단 거리로 생각할 수 있다
 *   그러니 BFS 를 사용하면 되겠다
 *   + 한번 방문한 곳을 또 방문할 필요는 없을 것 같다
 *     명령 하나하나가 모두 비용이라고 생각하면
 *     로봇의 초기 위치와 방향에서 BFS 를 돌때
 *     새롭게 방문하는 위치와 방향이 무조건 최소 비용일 수밖에 없다
 *     그러니 재방문을 고려하지 않아도 될 듯 하다
 *
 * Point
 * - 여기서 Node 또는 Point(위에서 말한 '곳') 는
 *   위치와 방향을 모두 포함한다
 *   + 같은 위치에 있더라도 방향이 다르면
 *     서로 다른곳이라 생각해야 한다
 *     # 위치와 방향정보를 함께 고려해주자
 *
 * - Zero-based Numbering
 *   위치가 (1,1) 부터, 방향은 1 부터 시작하는데
 *   다루기 쉽게 각각 (0,0), 0 부터 시작하게끔 전처리했다
 *
 * - BFS 에서 Go k 명령을 구현할 때
 *   Go 1 명령을 수행한다면 도착할 위치가 공장 밖이거나 궤도가 없다면 Go 1 명령은 불가능하다
 *   + Go 1 명령이 불가능하다면 Go 2, Go 3 명령도 불가능하다
 *     이점을 놓치면 항상 정답보다 값이 작은 오답을 얻게 된다
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <queue>

using namespace std;

#define endl '\n'

// Set up : Global Variables
int M, N;
char A[100][100];
struct Point { int y, x, d; };
bool isVisited[100][100][4];
enum Direction { East, West, South, North };
enum Turn { Left, Right };
int D[4][2] = {
        // Left, Right
        {North, South}, // East
        {South, North}, // West
        {East, West}, // South
        {West, East}  // North
};
int dy[4] = {0, 0, +1, -1};
int dx[4] = {+1, -1, 0, 0};

// Set up : Functions Declaration
bool isValid(int y, int x);


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    cin >> M >> N;
    for (int i=0; i<M; i++)
        for (int j=0; j<N; j++)
            cin >> A[i][j];
    int sy, sx, sd;
    cin >> sy >> sx >> sd;
    int ey, ex, ed;
    cin >> ey >> ex >> ed;

    // Process
    sy--, sx--, sd--; /* 시작 위치와 방향 Zero-based Numbering */
    ey--, ex--, ed--; /* 종료 위치와 방향 Zero-based Numbering */

    queue<Point> que;

    isVisited[sy][sx][sd] = true;
    que.push({sy, sx, sd});

    int ans = -1; /* 명령 수행 횟수 */
    while (not(que.empty())) {
        ans++;
        auto sz = que.size();
        while (sz--) {
            auto [cy, cx, cd] = que.front();
            que.pop();

            // Control : Output
            /* 출발지점에서 도착지점까지 항상 이동가능 */
            if (cy == ey && cx == ex && cd == ed) {
                cout << ans << endl;
                exit(0);
            }

            /* Go k */
            for (int i=1; i<=3; i++) {
                int ny = cy + i*dy[cd];
                int nx = cx + i*dx[cd];
                /* 위치 (ny,nx) 가 공장 내이고 궤도가 설치되어 있다면 */
                if (isValid(ny, nx) && A[ny][nx] == '0') {
                    if (not(isVisited[ny][nx][cd])) {
                        isVisited[ny][nx][cd] = true;
                        que.push({ny, nx, cd});
                    }
                /* 위치 (ny,nx) 가 공장 밖이거나 궤도가 설치되어 있지 않다면 */
                } else break;
            }
            /* Turn dir */
            for (int i=0; i<2; i++) {
                int nd = D[cd][i];
                if (not(isVisited[cy][cx][nd])) {
                    isVisited[cy][cx][nd] = true;
                    que.push({cy, cx, nd});
                }
            }
        }
    }
}

// Helper Functions
bool isValid(int y, int x)
/* 주어진 좌표 (y,x) 가 유효하면 true 를 반환, 그 외 false 를 반환 */
{
    return y >= 0 && y < M && x >= 0 && x < N;
}
profile
이런 미친 게임을 봤나! - 옥냥이
post-custom-banner

0개의 댓글