88. 미로의 최단거리 [BFS]

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다.

문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅

 

 

풀이 

- 앞서 푼 섬나라 아일랜드 문제와 매우 유사한 BFS 문제

- 상하좌우 좌표를 배열로 미리 명시해 두고 이동할 좌표를 계산해 놓아야 함

- 첫 위치를 큐에 넣고 map[1][1]=1로 체크 한다.

- 큐의 첫번째 요소를 tmp에 저장해 놓고 Q에서 pop한다.

- 4번의 반복으로 상하좌우 좌표값을 xx, yy로 만들며 0(도로)인 곳을 탐색

=> 이때 좌표가 정해진 7*7을 벗어나지 않도록 if문 안에 조건 추가

- 만약 도로라면 dis배열의 값을 업데이트하는데 이때값은 dis[tmp.x][tmp.y]+1의 값을 가짐

#include <stdio.h>
#include <algorithm>
#include <queue>
using namespace std;
int n, map[10][10], dis[10][10];
int dx[4]={0, 1, 0, -1};
int dy[4]={-1, 0, 1, 0};

//88. 미로의 최단거리 통로(BFS)

struct Loc{
    int x;
    int y;
    Loc(int a, int b){
        x=a;
        y=b;
    }
};

queue<Loc> Q;

int main(){
    for(int i=1;i<=7;i++){
        for(int j=1;j<=7;j++){
            scanf("%d", &map[i][j]);
        }
    }
    Q.push(Loc(1,1));
    map[1][1]=1;
    while(!Q.empty()){
        Loc tmp=Q.front();
        Q.pop();
        for(int i=0;i<4;i++){
            int xx=tmp.x+dx[i];
            int yy=tmp.y+dy[i];
            if(map[xx][yy]==0 && xx>=1 && xx<=7 && yy>=1 && yy<=7){
                Q.push(Loc(xx, yy));
                map[xx][yy]=1;
                dis[xx][yy]=dis[tmp.x][tmp.y]+1;
            }
        }
    }
    printf("%d", dis[7][7]);
    return 0;
}