[백준] 2178. 미로 탐색 풀이 (C++)

백준 2178. 미로 탐색 (Silver I)

Type : bfs

 

문제

N×M크기의 배열로 표현되는 미로가 있다.

 

 

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

 

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

 

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

 

예제 입력 및 예제 출력

 

풀이

이번에는 Silve I 난이도 중에서 bfs 문제를 풀어보았다.

이 문제는 최단 거리를 구하는 문제로서 난이도가 그렇게 높지는 않은데도 불구하고, C++에서 bfs 구현 방법을 까먹은 내게 참 고역이었다,,,

 

최단 거리를 구하는 문제는 거의 대부분 bfs 문제라고 생각하면 된다. 지문을 해석해보면 다음 3가지에 신경 써야 한다는 것을 알 수 있다.

 

1. 입력 값이 붙어서 나온다

2. 격자 위에서 동서남북으로 움직일 수 있다.

3. 목표 지점까지의 최단 거리를 계산해야 한다.

 

따라서 위 3가지 내용을 기반을 코드를 구현해주면 된다.

 

1. 입력 값 분할 저장하기

입력 값을 분할하여 저장하는 것에는 여러 가지 방법이 있다. string을 써서 배열의 인덱스를 슬라이싱 해도 되고, 정수의 각 자릿수에 해당하는 값을 구하기 위해 10의 지수로 나누는 방법도 있을 것이다. 하지만, 가장 간단한 방법은 입력받을 때 한 글자씩 입력받는 것이다. 포맷 지정자를 이용해서 간단하게 이를 구현해준다.

 

2. 이동 가능한 다음 좌표 계산

격자 위에서 동, 서, 남, 북으로 움직일 수 있는데, 이때 동, 서, 남, 북은 2차원 배열의 관점에서 다음과 같이 표현할 수 있다.

 

동 : (0, 1)

서 : (0, -1)

남 : (1, 0)

북 : (-1, 0)

 

따라서 for문을 이용해 동, 서, 남, 북으로 (총 4차례) 이동한 좌표를 계산해준다.

 

3. 총 이동 거리 계산

이전 지점까지의 거리를 누적하여 총 이동 거리를 계산해준다.

 

/*
* Author : Kwangrok Baek (zester926@gmail.com)
* memory, time : 2104 KB, 0ms
* URL : https://www.acmicpc.net/problem/2178
* type : bfs
*/

#include <iostream>
#include <queue>

using namespace std;

int n, m;
bool check[100][100]; // 방문 여부 저장
int a[100][100];
int length[100][100]; // 이동 거리 저장
int dx[4] = {0, 0, 1, -1}; // x 축 이동 (열 이동)
int dy[4] = {1, -1, 0, 0}; // y 축 이동 (행 이동)

void bfs(int x, int y) {
    queue<pair<int, int>> q;
    q.push(make_pair(y, x));
    length[y][x] = 1;
    check[y][x] = true;

    while (!q.empty()) {
        int x = q.front().second;
        int y = q.front().first;
        q.pop();

        for (int i = 0; i < 4; i++) {
            int next_x = x + dx[i]; // 2. 이동 가능한 다음 좌표 계산
            int next_y = y + dy[i];

            if (next_x >= 0 && next_y >= 0 && next_x < m && next_y < n && a[next_y][next_x] == 1 && check[next_y][next_x] == false) {
                length[next_y][next_x] = length[y][x] + 1; // 3. 총 이동 거리 계산
                check[next_y][next_x] = true;
                q.push(make_pair(next_y, next_x));
            }
        }
    }
}

int main(void) {
        scanf("%d %d", &n, &m);
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < m; k++) {
                scanf("%1d", &a[j][k]); // 1. 붙어있는 수 나눠서 저장
            }
        }
        bfs(0, 0);
        printf("%d\n", length[n - 1][m - 1]);
}

 

문제에 바로바로 적용할 수 있도록 기본 알고리즘을 cpp로 구현하는 연습을 해야겠다.

 

zester926/Algorithm-challenge