[BOJ] - 2178. 미로 탐색

[URL]

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

[풀이 과정]

* BFS queue 최단거리

 

1. input()

 

2. bfs(x, y)

 

출발 위치(x, y)

(1) 큐에 push

(2) visited[x][y] = true

(3) dist[][]

 

큐가 빌때 까지 --> x, y에서 더이상 갈 곳이 없을 경우 종료

큐에서 현재 위치(x, y) pop

 

다음 위치 (nx, ny)

4방향 탐색(상하좌우) --> [조건 1] [조건 2] 둘 다 만족 하는 경우

가능하면 ??

(1) 큐에 push

(2) visited[nx][ny] = true

(3) dist[nx][ny] = 이전 위치 + 1

 

 

[소스 코드]

 

 

#include <stdio.h>
#include <queue>
using namespace std;
 
int N, M;
int map[105][105];
bool visited[105][105];
 
int dist[105][105];
 
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { -1, 1 , 0, 0 };
 
struct info
{
    int x;
    int y;
};
 
void input()
{
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            scanf("%1d", &map[i][j]);        // 꿀팁! 한 글자씩 입력 받을떄 유용
        }
    }
}
 
void BFS(int indexI, int indexJ) {
    queue <info> q;
 
    info temp;
    temp.x = indexI;
    temp.y = indexJ;
 
    q.push(temp);
    visited[indexI][indexJ] = true;
    dist[indexI][indexJ] = 1;
 
    while (!q.empty())
    {
        int cx = q.front().x;
        int cy = q.front().y;
        q.pop();
 
        for (int k = 0; k < 4; k++)        // 4방향 탐색 nx, ny
        {
            int nx = cx + dx[k];
            int ny = cy + dy[k];
 
            if (nx >= 0 && nx < N && ny >= 0 && ny < M)                // [큐 조건.1] nx, ny  << map 범위 안에 있는가? isInside??
            {
                if (map[nx][ny] == 1 && visited[nx][ny] == false)    // [큐 조건.2] map[nx][ny]가 갈 수 있는 위치 && 방문하지 않은 위치
                {
                    info nextTemp;
                    nextTemp.x = nx;
                    nextTemp.y = ny;
 
                    q.push(nextTemp);
                    visited[nx][ny] = true;
                    dist[nx][ny] = dist[cx][cy] + 1;
                }
            }
        }
    }
 
    printf("%d\n", dist[N - 1][M - 1]);        //마지막에 최단거리가 저장된 dist[][]의 해당 위치값 출력
}
 
int main() {
 
    input();        //N, M, map[N][M] 입력받는다.
    
    BFS(0, 0);        // 0,0에서 출발하여 map[N-1][M-1]위치까지의 최단거리(dist[][]에 거리 저장) 계산
 
    return 0;
}