[백준] 2178 미로 탐색 C++

1. 문제 설명

• 링크 : https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

---

2. 풀이 과정

• 문제 해결의 흐름 
  1. 주어진 입력에 대해 시작점 (0,0)부터 bfs를 통해 탐색하자.
  2. visited 배열에 이전 이동 거리에서 1을 더해주며 지나야 하는 최소 칸 수를 구해준다. 
• 나의 코드 

//
// Created by 태윤맥북 on 4/17/24.
//

#include <iostream>
#include <queue>
#include <string>

using namespace std;

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int N, M;
int maze_map[101][101];
int visited[101][101] = {};


int bfs() {
    queue<pair<int, int> > q;
    q.push(make_pair(0,0));
    visited[0][0] = 1;

    while(!q.empty()) {
        int now_x = q.front().first;
        int now_y = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i ++) {
            int new_x = now_x + dx[i];
            int new_y = now_y + dy[i];

            if (new_x >= 0 && new_x < M && new_y >= 0 && new_y < N && !visited[new_y][new_x] && maze_map[new_y][new_x] == 1) {
                q.push(make_pair(new_x,new_y));
                visited[new_y][new_x] = visited[now_y][now_x] + 1;
            }
        }
    }

    return visited[N-1][M-1];
}

int main() {
    // 입력 받기
    cin >> N >> M;

    fill_n(&visited[0][0], N * M, false);

    for (int i = 0; i < N; i++) {
        string line;
        cin >> line;
        for (int j = 0; j < M; j++) {
            maze_map[i][j] = line[j] - '0'; // 문자열로 입력 받은 미로를 정수로 변환하여 저장
        }
    }

    // bfs 호출
    cout << bfs();

    return 0;
}

 

• 이 문제를 통해 얻어갈 수 있는 것들
  • 토마토 문제 풀었을 때와 마찬가지로 visited에 최소 이동 거리를 저장해주었다.
  • ⭐️ '101010'와 같은 문자열을 숫자 배열에 저장하기 위해서는 array[i][j] = str[j] - '0'을 이용하자
  • 큐에 2개의 값을 저장하는데 coordinate 구조체는 더 이상 그만 사용하자. 3개 값 이상 저장할 때는 유용할지도..?

// 만약 2개의 정수, 1과 4를 큐에 저장한다면? 
queue<pair<int, int> > q;
q.push(make_pair(1,4));

 

---

3. 후기 

 배웠던 것들을 제대로 써먹은듯!