[Algorithm][BFS][정올] 1661. 미로탈출로봇

I. 문제

<입력 형식>

첫 줄에 미로의 크기 X, Y(1≤X, Y≤100)가 주어진다.
둘째 줄에 출발점 x, y 좌표와 도착점 x, y 좌표가 공백으로 구분하여 주어진다.
셋째 줄부터 미로의 정보가 길은 0, 벽은 1로 공백이 없이 들어온다.

<출력 형식>

첫 줄에 출발점에서 도착점까지 가장 빠른 시간을 출력한다.

입력	출력
8 7 1 2 7 5 11111111 00000111 10110011 10111001 10111101 10000001 11111111	9

 

---

II. 접근

1. 현재 위치 x,y 와 시간t를 담을 수 있는 구조체 생성.
2. 현 위치에서 다음 4방향의 0인 위치의 정보 구조체를 Queue에 저장
3. Queue를 순차적으로 pop()하며 이동 및 2. 반복
4. 목적지 도착하면 return
* visit배열 없이 map을 1로 손상시키면서 확산

 

---

III. Code

<hide/>
#include <queue> // c++의 Queue STL
#include <iostream>
#include <cstring> // memset위해서
using namespace std;

/*
배열의 인덱스, 현재까지의 시간 구조체
Queue에 정보를 다 넣어야하기 때문에 구조체 정의함.
*/
struct stu {
    int y;
    int x;
    int t;
};

int X, Y;
int sx, sy, ex, ey; // 시작s와 끝e
queue<stu> Q;
int map[100 + 10][100 + 10]; // 지도

// 이번 경우에는 map을 0->1로 훼손하며 방문표시함 visit 사용X
// int visit[100 + 2][100 + 2];

void input() {
    cin >> X >> Y;
    cin >> sx >> sy >> ex >> ey;
    for (int i = 1; i <= Y; i++) {
        for (int j = 1; j <= X; j++) {
            scanf("%1d", &map[i][j]);
        }
    }
}

int BFS() {
	// 상하좌우 탐색 위한 dy,dx
    int dy[4] = { 0,0,-1,1 };
    int dx[4] = { 1,-1,0,0 };

    // Q에 초기정보를 stu구조로 push함 (map[0][0]과 time =0)
    Q.push(stu{ sy,sx,0 });
    map[sy][sx] = 1;

    //Q가 텅 빌때까지 반복(모든노드 탐색)
    while (!Q.empty()) {
        stu curstu = Q.front(); //현재정보
        Q.pop(); //큐에서 제거

        //4가지 방향을 모두 확인해본다.
        for (int d = 0; d < 4; d++) {
			// 다음정보를 계산해줌
            int nextx = curstu.x + dx[d];
            int nexty = curstu.y + dy[d];
            int nextt = curstu.t + 1;
            
            if (nexty == ey and nextx == ex) return curstu.t + 1; // 마지막 도착하면 return
            
            if (nexty == 0 or nextx == 0 or
                nexty == Y+1 or nextx == X+1) continue; // 배열 벗어나면 무시
                
                
            // 다음위치가 0이라면 확산
            if (!map[nexty][nextx]) {
                Q.push(stu{ nexty,nextx,nextt }); // 다음 정보 Q에 Push
                map[nexty][nextx] = 1; // map 훼손하며 방문표시 
            }
        }
    }
    return -1; // 해도되고 안해도 됨. 못찾을 때 대비
}

int main() {
    memset(map, 0, sizeof(map));
    
    input();
    
    int ans = BFS();
    cout << ans;

    return 0;
}

 

문제 출처 www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=934&sca=99