[BFS]BOJ 1726_로봇

문제 링크 : www.acmicpc.net/problem/1726

1726번: 로봇

다소 전형적인 2차원 배열에서의 BFS 응용 문제이다.

2차원 배열의 판(Board)에 로봇(말)이 있고, 목표 지점까지의 최소 거리 등을 구하는 유형의 문제이다.

[BFS에 대해]

BFS (Breadth-First Search, 너비 우선 탐색)

 

이 문제를 단순하게 2차원 배열에서의 칸 이동으로 그래프를 생각한다면,

문제의 각 칸들을 다음과 같은 그래프로 생각할 수 있다.

이 이차원 배열을

이런 그래프로 생각할 수 있다.

 

하지만, 이 문제에서는 로봇의 방향이 고려되어야 한다.

방향을 오른쪽 또는 왼쪽으로 도는 것 또한 한 번의 명령으로 간주하기 때문에,

실제로 이 문제의 각 칸을 그래프로 나타내면 다음과 같은 그래프가 된다.

로봇의 방향을 포함시킨 이차원 배열의 그래프

따라서, 로봇이 한 번의 명령을 통해 그래프에서 이동 가능한 점은 다음 그림에서의 색칠한 노드와 같다.

그림에 없는 아래의 노드도 포함이다. (최대 3칸 이동)

이는 코드에서 2차원 배열에 대한 visit 배열을 한 차원 올려 구현할 수 있다.

코드에서 실제로 visit이 3차원 배열로 선언되어 있음을 볼 수 있다.

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <tuple>
#include <queue>
 
using namespace std;
typedef tuple<int, int, int> tup;
 
int r, c;
int board[101][101];
int visit[101][101][5];    //1234-EWSN
int dir_r[4] = { 0, 0, 1, -1 };
int dir_c[4] = { 1, -1, 0, 0 };
tup start, fin;
 
int bfs() {
    queue<tup> que;
    que.push(start);
    visit[get<0>(start)][get<1>(start)][get<2>(start)] = 1;
 
    while (!que.empty()) {
        tup cur = que.front();
        que.pop();
 
        int row = get<0>(cur);
        int col = get<1>(cur);
        int dir = get<2>(cur);
 
        if (row == get<0>(fin) && col == get<1>(fin) && dir == get<2>(fin))
            return visit[row][col][dir];
 
        int newDir[2], newR = row, newC = col; 
        switch (dir) {
            //현재 노드의 방향에 따라
        case 1:
        case 2:
            newDir[0] = 3; newDir[1] = 4; break;
        case 3:
        case 4:
            newDir[0] = 1; newDir[1] = 2; break;
        }
 
        int newVisit = visit[row][col][dir] + 1;
        //방향전환
        for (int i = 0; i < 2; i++) {
            if (visit[row][col][newDir[i]]) continue;
            visit[row][col][newDir[i]] = newVisit;
            que.push({ row, col, newDir[i] });
        }
 
        //k 칸 전진 (해당 줄을 모두 방문)
        for(int i = 0; i < 3; i++) {
            newR += dir_r[dir - 1];
            newC += dir_c[dir - 1];
            if (newR > r || newR < 1 || newC > c || newC < 1) break;
            if (board[newR][newC] == -1) break;
            if (visit[newR][newC][dir]) continue;
            visit[newR][newC][dir] = newVisit;
            que.push({ newR, newC, dir });
        }
    }
    return -1;
}
 
void init() {
    scanf("%d %d", &r, &c);
 
    for (int i = 1; i <= r; i++)
        for (int j = 1; j <= c; j++) {
            int input;
            cin >> input;
            if (input) board[i][j] = -1;
            else board[i][j] = 0;
        }
 
    int row, col, dir;
    for (int i = 0; i < 2; i++) {
        scanf("%d %d %d", &row, &col, &dir);
        if (i == 0) { start = { row, col, dir }; }
        if (i == 1) { fin = { row, col, dir }; }
    }
}
 
int main() {
    init();
    int result = bfs();
 
    if(result != -1) result--;
    printf("%d\n", result);
    return 0;
}