로봇

코드

#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <deque>
#include <numeric>
#include <map>
#include <stack>
#define ll long long
using namespace std;
// 1132 ~ 0140
struct Pos{
    int r;
    int c;
    int dir;
};
int dr[4] = {1, 0, -1, 0};// 남 서 북 동
int dc[4] = {0, -1, 0, 1};
int M,N,ans=1e9;
int board[105][105]; // 1~100 인덱스 사용
int cost[4][105][105];
Pos start;
Pos dest;
/* 문제의 방향을 right/left 하기 좋은 내 방향으로 바꾸기 */
int changeDir(int d)
{
    if(d == 1) return 3;
    if(d == 2) return 1;
    if(d == 3) return 0;
    return 2;
}
/* cur에서 right/left로 얼마나 했을 때 hope로 갈수 있는지 최소값 */
int diffDir(int cur, int hope)
{
    if(cur == hope) return 0;
    int cur_t = cur;
    int leftCnt=0;
    while(cur_t != hope){
        cur_t--;
        if(cur_t<0) cur_t +=4;
        leftCnt++;
    }
    cur_t = cur;
    int rightCnt=0;
    while(cur_t != hope){
        cur_t++;
        if(cur_t>3) cur_t -=4;
        rightCnt++;
    }
    return min(leftCnt, rightCnt); // 왼쪽, 오른쪽 회전 중 최소 값 리턴
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> M >> N; // M=세로, N=가로
    for(int i=1;i<=M;i++)
        for(int j=1;j<=N;j++)
            cin >> board[i][j];
    cin >> start.r >> start.c >> start.dir;
    cin >> dest.r >> dest.c >> dest.dir;
    start.dir = changeDir(start.dir);
    dest.dir = changeDir(dest.dir);

    /* 에외처리 - 출발점과 도착점이 같다면 방향 회전으로만 답을 구할 수 있음 */
    if(dest.r == start.r and dest.c == start.c){
        cout << diffDir(dest.dir, start.dir);
        return 0;
    }
    /* cost초기화 */
    for(int z=0;z<4;z++)
        for(int i=1;i<=M;i++)
            fill(cost[z][i], cost[z][i]+N+1, 1e9);
    queue<Pos> q;
    q.push(start);
    cost[start.dir][start.r][start.c] = 0;
    while(!q.empty())
    {
        auto cur = q.front(); q.pop();
        for(int d=0;d<4;d++)
        {
            int nr = cur.r;
            int nc = cur.c;
            for(int n=1;n<=3;n++)
            {
                nr += dr[d];
                nc += dc[d];
                int dval = diffDir(cur.dir, d); // 오른쪽, 왼쪽 회전중 최소 회수
                int destval = 0;
                // 목적지라면 최종 방향도 cost계산을 해줘야함
                if(nr == dest.r and nc == dest.c) destval = diffDir(d, dest.dir);
                if(nr<1 or nc<1 or nr>M or nc>N) break; // 범위를 벗어나면 종료
                if(board[nr][nc] == 1) break; // 벽을 만나도 종료
                /* cost의 길이가 같은 경우에 continue 해주지 않으면 무한루프에 걸림 
                   --> 값이 동일하면 어차피 그 좌표에서 그 방향을 가졌으면 같은 결과를 산출 */
                if(cost[d][nr][nc] <= cost[cur.dir][cur.r][cur.c] + dval + destval + 1) continue;
                cost[d][nr][nc] = cost[cur.dir][cur.r][cur.c] + dval + destval + 1;
                if(nr == dest.r and nc == dest.c) continue;
                Pos t = {nr, nc, d};
                q.push(t);
            }
        }
    }
    for(int d=0;d<4;d++)
        ans=min(cost[d][dest.r][dest.c], ans);
    cout << ans;
    return 0;
}

• 핵심
  • board[dir][r][c]를 사용해서 보드판의 입장에서 어떤 방향을 가지고 있는지에 따라 최소 값 갱신
  • cost를 비교할 때 같은 cost를 가지면 반드시 continue로 넘겨줘야 한다
    --> 그렇지 않으면 무조건 무한루프에 빠진다
  • 출발지점과 도착지점이 같은 경우 예외처리
  • right / left 회전 중 최소 회전을 찾는 diffDir 정의

• 느낀 점
  • 프로그래머스의 활주로 건설 이라는 문제로 처음 board 상태에 따른 3차원 배열을 접했는데 종종 나오는 것 같다