[정올] 1661 : 미로 탈출 로봇

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=934&sca=99&page=7 

JUNGOL

문제 이해

최단 거리를 구하는 문제이므로 BFS를 사용하면 된다. 

 

출발지로부터 모든 상하좌우를 탐색하면서 방문하다가 목적지에 도착하면 거기까지의 거리를 return해주면 된다. 

여기서 주어진 map의 0인 부분만 탐색해야 한다. 

 

시간복잡도는 맵의 모든 부분이 0이어서 모든 곳을 탐색하는 경우 (100*100) 정도 이다. 충분히 시간 내에 해결할 수 있다. 

작성 코드

#include <iostream>
#include <queue>

using namespace std;

int Y, X;
int sy, sx, ey, ex;
char map[100 * 10][100 * 10];

int dx[] = { 0, 0, -1, 1 };
int dy[] = { -1, 1, 0, 0 };

typedef struct POS {
    int y;
    int x;
    int t;
}POS;

queue<POS> q;

int BFS(int y, int x, int t) {

    POS s = { y, x, t };
    q.push(s);
    map[y][x] = '1';

    while (!q.empty()) {
        POS cur = q.front();
        q.pop();

        if (cur.y == ey-1 && cur.x == ex-1) return cur.t;

        for (int i = 0; i < 4; i++) {
            int ny = cur.y + dy[i];
            int nx = cur.x + dx[i];

            if (nx < 0 || nx >= X) continue;
            if (ny < 0 || ny >= Y) continue;
            if (map[ny][nx] == '1') continue;

            POS next = { ny, nx, cur.t + 1 };
            map[ny][nx] = '1';
            q.push(next);
        }
    }
    return 0;
}

int main(void) {

    int ans;
    // 입력 받기
    cin >> X >> Y;
    cin >> sx >> sy >> ex >> ey;
    for (int i = 0; i < Y; i++) {
        cin >> map[i];
    }

    ans = BFS(sy-1, sx-1, 0);

    cout << ans;

    return 0;
}

주의할 점: 입력을 0, 0 부터 받기 때문에 출발 좌표랑 도착 좌표를 조정해줘야 한다. (각 -1씩)