[백준] 1726번 로봇 (C++)

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

 

 

이 문제는 격자판에서 장애물과 갈 수 있는 칸과 현재 시작점의 위치와 바라보는 방향, 도착점의 위치와 바라보는 방향이 주어졌을 때

시작점에서 시작하여 최소한의 명령을 사용하여 도착점의 위치에 도착하여 해당하는 방향으로 바라보는 횟수를 구하는 문제이다.

 

현재 위치, 방향을 기준으로 어떤 명령어로 움직여야 최적인지를 모르기 때문에 모든 경우의 수를 구해야 한다고 생각하였다.

 

그래서 bfs(너비 우선 탐색)을 사용하였다.
이때 방향 요소 까지 있기 때문에 3차원 방문배열을 사용하였다.

 

 

이때 2개의 명령어가 있는데 왼쪽과 오른쪽으로 45도 회전하는 명령어 같은 경우는

상, 하 에서 좌우로 움직일때 나올 수 있는 방향은 좌우이며

좌, 우 에서 좌우로 움직일때 나올 수 있는 방향은 상, 하기 때문에 2개를 한묶음으로 보았다.

 

또한 움직이는 명령어는 현재 바라보는 방향에서 1~3칸 움직일 수 있는데

만약 1~3칸 움직이다가 장애물을 마주쳤다면 이는 갈 수 없는 것으로 처리해야한다.

 

정답 코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
};

//int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
//int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};
int dx[] = {0, 0, 0, 1, -1};
int dy[] = {0, 1, -1, 0, 0};
int M, N, startx, starty, startdir;
int graph[101][101];
bool visited[101][101][6];
int endx, endy, enddir;

bool check(int x, int y, int dirs) {
    if(x > 0 && x <= M && y > 0 && y <= N) {
        if(!visited[x][y][dirs] && graph[x][y] == 0) {
            return true;
        }
    }
    return false;
}

void bfs(int stx, int sty, int direc) {
    queue<tuple<int, int, int, int>> q;
    q.push({stx, sty, direc, 0});
    visited[stx][sty][direc] = true;

    while(!q.empty()) {
        int x = get<0>(q.front());
        int y = get<1>(q.front());
        int dir = get<2>(q.front());
        int cnt = get<3>(q.front());
        q.pop();

        if(x == endx && y == endy && dir == enddir) {
            cout << cnt;
            return;
        }

        if(dir == 1 || dir == 2) {
            for(int i = 3; i <= 4; i++) {
                if(check(x, y, i)) {
                    q.push({x, y, i, cnt+1});
                    visited[x][y][i] = true;
                }
            }
        } else if(dir == 3 || dir == 4) {
            for(int i = 1; i <= 2; i++) {
                if(check(x, y, i)) {
                    q.push({x, y, i, cnt+1});
                    visited[x][y][i] = true;
                }
            }
        }

        for(int i = 1; i <= 3; i++) {
            int nx = x + dx[dir] * i;
            int ny = y + dy[dir] * i;

            if (nx <= 0 || ny <= 0 || nx > M || ny > N) break;
            if (graph[nx][ny] == 1) break;
            if (visited[nx][ny][dir]) continue;

            q.push({nx, ny, dir, cnt+1});
            visited[nx][ny][dir] = true;
        }
    }
}

void solve() {
    bfs(startx, starty, startdir);
}

void input() {
    cin >> M >> N;

    for(int i = 1; i <= M; i++) {
        for(int j = 1; j <= N; j++) {
            cin >> graph[i][j];
        }
    }

    cin >> startx >> starty >> startdir;

    cin >> endx >> endy >> enddir;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}

 

 

회고록

바로 bfs를 사용해야하는 것을 10분안에 캐치하였다. 근데 코드가 뭔가 단순하지 않다고 생각해서

조금더 코드를 예쁘게 짤 수 있는 다른사람들의 방법을 좀 참고해야 한다고 생각한다.