[백준] 2178번: 미로 탐색

 

 

---

 

문제

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

 

 

개념

그래프, BFS

 

 

실행 결과

 

 

 

 

 

구현 코드(c++)

#include <iostream>
#include <queue>
using namespace std;

int n, m;
int arr[100][100];   // 미로 배열
int dist[100][100];  // 최단 거리 배열

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  // 미로의 크기 입력
  cin >> n >> m;

  // dx,dy: 상, 우, 하, 좌 방향 벡터
  int dx[4] = {1, 0, -1, 0};
  int dy[4] = {0, 1, 0, -1};

  // 미로 입력 받기 (행->렬)
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      // 먼저 문자로 처리하고 0을 빼서 숫자로 변환
      char c;
      cin >> c;
      arr[i][j] = c - '0';
    }
  }

  // BFS에 사용할 큐
  queue<pair<int, int>> q;
  // 시작점 (0, 0) 큐에 넣고, 거리 초기화
  q.push({0, 0});
  dist[0][0] = 1;  // 시작점의 거리를 1로 설정 (첫 칸 포함)

  // BFS 탐색 시작
  while (!q.empty()) {
    auto cur = q.front();
    q.pop();

    // 현재 위치에서 4방향으로 이동
    for (int dir = 0; dir < 4; dir++) {
      int nx = cur.first + dx[dir];
      int ny = cur.second + dy[dir];

      // 범위 체크
      if (nx < 0 || nx >= n || ny < 0 || ny >= m)
        continue;

      // 벽이거나 이미 방문한 곳이면 건너뛰기
      if (arr[nx][ny] == 0 || dist[nx][ny] != 0)
        continue;

      // 새로운 곳이면 거리 갱신하고 큐에 넣기
      dist[nx][ny] = dist[cur.first][cur.second] + 1;
      q.push({nx, ny});
    }
  }

  // 도착 지점에서 거리 출력
  cout << dist[n - 1][m - 1];

  return 0;
}

 

 

 

 

코드 설명

최단 경로 -> bfs + 상하좌우 이동이므로 dx, dy 테크닉을 이용한다.

 

문제에서 주어진 2차원 배열의 미로를 살펴보자.

1은 갈 수 있는 길이고 0은 갈 수 없는 길이다.

 

2차원 배열 arr은 미로, dist는 이동한 거리를 저장하도록 한다.

dx, dy 테크닉을 활용하여 상, 우, 하, 좌 순서대로 x, y 좌표를 저장하는 배열을 만들어둔다.

 

첫칸 설정

첫번째 좌표인 (0, 0)을 큐에 넣고, dist에 1을 넣는다. 

큐가 비어있을 때까지, 즉 더이상 방문할 곳이 없을 때까지 bfs를 반복한다.

이 반복문 내에서 현재 위치인 cur에서 4방향으로 이동할 수 있는지 확인하고, 이동할 수 있는 경우만 이동한다. 

 

      // 범위 체크
      if (nx < 0 || nx >= n || ny < 0 || ny >= m)
        continue;

      // 벽이거나 이미 방문한 곳이면 건너뛰기
      if (arr[nx][ny] == 0 || dist[nx][ny] != 0)
        continue;

 

다음과 같은 경우 continue를 통해 건너뛴다.

1. 미로를 벗어나는 범위인 경우 (x, y좌표가 음수이거나 n,m 크기 벗어나는 경우)
2. arr에서 해당 칸이 막혀있는 경우(0) or 해당 칸을 이미 방문한 경우

      // 새로운 곳이면 거리 갱신하고 큐에 넣기
      dist[nx][ny] = dist[cur.first][cur.second] + 1;
      q.push({nx, ny});

 

위에 해당하지 않으면 아직 방문하지 않은 곳이므로,

dist 배열에 집어넣고 +1을 통해 거리를 갱신하고 방문처리한다.

 

---

 

 

[실전 알고리즘] 0x09강 - BFS