#82. [백준_C언어] 2178 : 미로 탐색 \ 그래프 탐색

 

입력 코드

#include <stdio.h>
int i, j, N, M;
 
int map[501][501];
int visit[501][501];
 
//좌표정보를 담을 구조체 선언
typedef struct n {
    int x;
    int y;
}q;    
 
q queue[10001];    //큐의 크기를 넉넉하게    (원형큐를 쓰면 될것도같은데 이건 확인해볼것)
int front, rear, max;    //자료구조 구현을 위한 변수
 
//상 하 좌 우 를 확인하기위한 방향수정용 배열
int vectX[4] = { 0,0,1,-1 };
int vectY[4] = { 1,-1,0,0 };
 
//큐 자료구조를 쓰기위한 선언
q deque();
void enque(int, int);
int isEmpty();
 
void bfs()
{
    int nextX, nextY;    
    while (isEmpty())    //큐가 다 빌때까지 실행함
    {
        q pop = deque();    //일단 꺼내고
        for (i = 0; i < 4; i++)
        {
            nextX = pop.x + vectX[i];    //다음 방문의 방향값을 정함
            nextY = pop.y + vectY[i];    //이하 동문
 
            if (nextX >= 1 && nextX <= N && nextY >= 1 && nextY <= M)    //방향값이 올바른 좌표일 시 만 고려함
            {
                if (map[nextX][nextY] == 1)    //다음 배열의 정보가 1일시만 고려함
                {
                    if(visit[nextX][nextY]==0){    //다음 배열정보의 방문정보가 없을 시 
                        visit[nextX][nextY] = visit[pop.x][pop.y] + 1;    //현재 방문정보에 +1 을 함(결과적으로 상 하 좌 우 전부 +1되어 퍼져나감)
                        enque(nextX, nextY);    //다음 방문할 배열의 좌표값을 큐에 삽입
                    }
                }
                if (visit[pop.x][pop.y] > max)    //이부분은 필요없음. 도착지의 방문값이 항상 최대라는 보장이 없음
                    /*
                    1)                2)
                        1111            1111
                        0001            1010
                        0001            1111
                        1111            0101
                        예를들어 2번과 같은 경우, 도착지의 값이 최대거리라 통과할 수 있으나, 1번인 경우
                        큐의 삽입을 배열에 도착했을 때 끊어주지않으면 아래와 같이 이동
                        1)                        2)
                        [01][02][03][04]        [01][02][03][04]
                        [  ][  ][  ][05]        [02][01][04][01]
                        [  ][  ][  ][06]        [03][04][05][06]
                        [10][09][08][07]        [01][05][01][07]
                            max = 10                max = 7
                            이를 막기위해선, if(nextX == M && nextY ==N) ->큐에 더이상 삽입하지않고 bfs를 마침 
                            과 같이 break를 걸어줘야 할 필요가 있음.
                    */
                    max = visit[pop.x][pop.y];
            }
 
        }
    }
}
int main()
{
    scanf("%d %d", &M, &N);
    for(i=1;i<=M;i++)
        for (j = 1; j <= N; j++)
            scanf("%1d", &map[j][i]);    //배열의 정보값을 1씩 입력받음
        
    visit[1][1] = 1;    //기저조건, 최초 시작은 항상 1.1에서 시작하므로 visit을 1로 변경
    enque(1, 1);        //1.1에 인접한 유효방향을 찾기위해 삽입
    bfs();                //bfs실시
    printf("%d\n", visit[N][M]);    //max값을 출력했다가 변경함. 이 부분때문에 고생 ㅠ
 
}
void enque(int x, int y)
{
    q temp;
    temp.x = x; temp.y = y;
    queue[rear++] = temp;
}
q deque()
{
    q temp = queue[front++];
    return temp;
}
 
int isEmpty() {
    if (front == rear)
        return 0;
    else
        return 1;
}

출처 m.blog.naver.com/sukwoo0711/220902510038

 

코드 설명

#그래프이론 #그래프탐색 #너비우선탐색

 

 

 

문제 출처

www.acmicpc.net/problem/2178

2178번: 미로 탐색