백준 1726 / 로봇

BFS 문제

그저 최단거리를 찾는 문제아닌,  방향 바꾸는 행위와 1,2,3칸 직진이 추가된 BFS 문제다.

check 배열과 최단거리를 담는 d 배열을 방향값까지 추가하여 3차원으로 선언 후.

직진하는 경우와 방향을 바꾸는 경우를 구현했다.

1. 직진하는 경우

3칸까지 갈 수 있기떄문에

자신의 방향 앞에 놓인 값들이 모두 0일떄 직진할 수 있게 구현했다.

2. 방향을 바꾸는 경우

젤 헷갈렸던 부분

동쪽이 1 서쪽 2 남쪽3 북쪽4 이기 떄문에

예를 들어, 동쪽에서 서쪽에서 바꾸는 경우 숫자는 1이 들지만 방향을 두 번(오른쪽,오른쪽) 바꾸어야되기떄문에 

이런 경우들을 체크하는 조건문을 걸어두었다.

dir + i == 7 || dir + i == 3

dir은 현재 방향, i는 바꾸고자 하는 방향. 

동에서 서로 바꾸는 경우 dir+i가 3, 남에서 북으로 바꾸는 경우 7이 되기 떄문에 방향을 두 번 바꾸었다고 하면 된다.

코드

#include<stdio.h>
#include<vector>
#include<queue>
#include<iostream>
#include<algorithm>
#include<memory.h>
#include<tuple>
#include<math.h>
 
using namespace std;
 
int dx[] = {0, 0,0,1,-1 };
int dy[] = { 0, 1,-1,0,0 };
 
 
int map[101][101];
bool check[101][101][5];
int d[101][101][5];
 
int n, m;
int sx, sy, sdir;
int gx, gy, gdir;
 
queue<tuple<int, int, int>>q;
 
bool gocheck(int x, int y, int nx, int ny) {
 
    
    if (nx >= 1 && ny >= 1 && nx <= n && ny <= m) {
        if (x < nx ) {
            for (int i = x; i <= nx; i++) {
                for (int j = y; j <= ny; j++) {
                    if (map[i][j] == 1) {
                        return false;
                    }
                }
            }
        }
        if (y < ny) {
            for (int i = x; i <= nx; i++) {
                for (int j = y; j <= ny; j++) {
                    if (map[i][j] == 1) {
                        return false;
                    }
                }
            }
        }
        if (x > nx) {
            for (int i = nx; i <= x; i++) {
                for (int j = y; j <= ny; j++) {
                    if (map[i][j] == 1) {
                        return false;
                    }
                }
            }
        }
        if (y > ny) {
            for (int i = x; i <= nx; i++) {
                for (int j = ny; j <= y; j++) {
                    if (map[i][j] == 1) {
                        return false;
                    }
                }
            }
        }
 
    }
    else {
        return false;
    }
    return true;
 
}
int main() {
    
    //freopen("Text.txt", "r", stdin);
    cin >> n >> m;
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> map[i][j];
        }
    }
 
    cin >> sx >> sy >> sdir;
    cin >> gx >> gy >> gdir;
 
    q.push(make_tuple(sx, sy, sdir));
    check[sx][sy][sdir] = true;
 
    while (!q.empty()) {
        int x, y, dir;
        tie(x, y, dir) = q.front();
        q.pop();
 
        for (int c = 1; c <= 2; c++) {
            if (c == 1) { // 직진
                for (int go = 1; go <= 3; go++) {
                    int nx = x + go * dx[dir];
                    int ny = y + go * dy[dir];
 
    
                    if (nx >= 1 && ny >= 1 && nx <= n && ny <= m) {
                        if (map[nx][ny] == 0 && check[nx][ny][dir] == false && gocheck(x, y, nx, ny)==true) {
                            check[nx][ny][dir] = true;
                            d[nx][ny][dir] = d[x][y][dir] + 1;
                            q.push(make_tuple(nx, ny, dir));
                        }
 
                    }
                }
            }
            if (c == 2) { // 방향 바꾸기
                for (int i = 1; i <= 4; i++) {
                    if (i == dir) continue;
 
                    if (check[x][y][i] == false) {
 
                        if (dir + i == 7 || dir + i == 3) {
                            check[x][y][i] = true;
                            d[x][y][i] = d[x][y][dir] + 2;
                            q.push(make_tuple(x, y, i));
                        }
                        else {
                            check[x][y][i] = true;
                            d[x][y][i] = d[x][y][dir] + 1;
                            q.push(make_tuple(x, y, i));
                        }
                    }
                }
            }
        }
    }
 
    cout << d[gx][gy][gdir] << endl;
}