[C++] 백준 2178번 문제 풀이 ( 미로 탐색 )

정민경·2023년 7월 28일
0

baekjoon

목록 보기
42/57
post-thumbnail

- 문제 ( 2178번 ) : 미로 탐색

  • 미로를 탈출할 때 지나는 칸의 최소 개수를 구하는 프로그램 작성.
    • 1은 지날 수 있는 칸, 0은 지날 수 없는 칸
    • 이동은 상, 하, 좌, 우 의 인접한 칸으로만 이동 가능.

- 입력 및 출력

[ 입력 ]

  • 첫째 줄에 미로의 크기 N(가로), M(세로) 입력.
  • 다음 N 개 줄에 M 개의 정수로 미로 입력.
    • 각각의 수들은 붙어서 입력.
  • 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어짐.

[ 출력 ]

  • 지나야 하는 최소의 칸 수 출력.

- 문제 풀이

  • 이번 최단 칸수 구하기와 같은 유형의 문제는 그래프 탐색 방법중에서도 BFS 를 사용하면 쉽게 해결이 가능하다.

    BFS 는 현재 노드와 연결된 모든 노드 탐색 후 방금 탐색한 노드들을 기준으로 또 연결되어있는 모든 노드 탐색 . . . 해서 모든 노드를 전부 탐색하는 방법이다.

    이러한 유형의 문제를 BFS 로 풀면 하나의 노드마다 접근할 수 있는 곳을 알 수 있게 되고, 그 칸은 현재 노드 + 1 의 칸을 추가하면 접근할 때 거치는 최소 칸의 수를 저장할 수 있게 된다.

    이번 미로찾기 문제 역시 처음 시작지점부터 BFS 로 탐색을 시작한 후 마지막 최종 노드 위치에 저장된 방문한 칸의 개수를 출력하면 문제가 해결된다.

  • 정리하면 아래와 같은 방식으로 해결할 수 있다.
  1. 입력받은 시작점부터 BFS 탐색을 하는데, 현재 위치에서 상, 하, 좌, 우 를 탐색해 방문 가능하다면 현재 위치에 저장되어있는 방문 칸수 + 1 을 다음위치에 저장해준다.
  2. 1번의 과정을 모든 노드에 대해서 반복한다. ( BFS 다보니 queue 에 push - pop 을 해주면서 queue 가 빌 때까지 반복 )
  3. 최종적으로 도착위치 ( N, M ) 의 방문 칸수를 출력하면 해결!
  • 문제를 풀면서 구현 상 신경써야 할 부분
    1. grid 의 입력이 공백 없이 붙어서 입력
      • 이 부분은
      scanf("%1d", &graph[i][j]);

      와 같이 입력받으면 해결


    2. 상, 하, 좌, 우 를 탐색하는 방법
    • 이 부분은 dx, dy technique 을 사용해 간단히 해결!


- 최종 코드

#include <iostream>
#include <queue>

#define N_MAX 100
#define M_MAX 100

using namespace std;

// 전역변수 설정
int N = 0, M = 0; // grid size (N x M)

// grid 선언
int graph[N_MAX][M_MAX] = {0, };

// 지나야 하는 최소의 칸 수 저장 배열
int result [N_MAX][M_MAX] = {0, };

// 상, 하, 좌, 우 를 탐색하기 위한 dx, dy 선언
int dx[4] = {-1, 1, 0, 0}; 
int dy[4] = {0, 0, -1, 1};

// 방문 확인 배열
bool is_visit[N_MAX][M_MAX] = {false, };

// 가능한 범위인지 확인
bool inRange(int x, int y) {
    // grid 를 벗어나지는 않았는지 확인
    bool ingrid = (0 <= x && x < N && 0 <= y && y < M);

    // 그 위치에 갈수없는 즉, 값이 0인지 확인
    bool possible_pos = (graph[x][y] != 0);

    return (ingrid && possible_pos);
}

// BFS 에서 사용할 queue
queue< pair <int, int> > q;


// BFS 탐색
void BFS(int x, int y) {

    // queue 가 빌 때까지 반복
    while(!q.empty()) {
        int a = q.front().first;
        int b = q.front().second;
        q.pop();

        // 현재 (a, b) 위치에서 상, 하, 좌, 우 4가지 방향 확인
        for(int i = 0; i < 4; i++) {

            // 다음 위치의 좌표 구하기
            int nx = a + dx[i];
            int ny = b + dy[i];

            // 가능한 범위라면 방문 확인 후 방문하지 않았다면 queue 에 위치 저장 후 
            // 이동할 때 지나야 하는 칸을 이전 방문 위치 (a, b) 의 값에 1 추가해 현재 좌표에 저장
            if(inRange(nx, ny) && (is_visit[nx][ny] == false)) {
                q.push(make_pair(nx, ny));
                is_visit[nx][ny] = true;
                result[nx][ny] = result[a][b] + 1;
            }

        }
    }
}

int main() {
    // grid size 입력
    cin >> N >> M;

    // grid 입력 (공백없이 붙어서 입력으로 주어지므로 정수 하나씩 받아서 처리)
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            scanf("%1d", &graph[i][j]);
        }
    }

    // 첫번째 위치 queue 에 저장 후 방문 표시
    q.push(make_pair(0, 0));
    is_visit[0][0] = true;

    // 시작위치도 칸을 세므로 시작위치의 결과값 1 저장
    result[0][0] = 1;

    // BFS 로 방문하며 지나야 하는 최소의 칸수 구하기
    BFS(0, 0);

    // 도착 위치의 방문 칸 수 출력 (result)
    cout << result[N-1][M-1] << endl;

    return 0;
}

0개의 댓글