미로 탈출

내가 작성한 BFS코드 이다.

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

int n,m;
int map[201][201];
int visited[201][201];
int dist[201][201];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
queue<pair<int,int>> q;

void bfs(int x,int y){
  q.push(make_pair(x,y));
  visited[x][y]=1;
  while(!q.empty()){
    x=q.front().first;
    y=q.front().second;
    q.pop();
    for(int k=0;k<4;k++){
      int nx=x+dx[k];
      int ny=y+dy[k];
      if(0<nx&&nx<=n&&0<ny&&ny<=m){
        if(map[nx][ny]==1&&visited[nx][ny]==0){
          q.push(make_pair(nx,ny));
          visited[nx][ny]=1;
          dist[nx][ny]=dist[x][y]+1;
        }
      }
    }
  }
}

int main()
{
  freopen("input.txt","r",stdin);
  cin>>n>>m;
  for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
      cin>>map[i][j];
    }
  }
  bfs(1,1);
  cout<<dist[n][m];
}

문제 자체는 굉장히 쉬운편이다. BFS를 이용하면 쉽게 풀 수 있다. 보통 "최단 어쩌구를 구하세요" 라는 문제는 BFS인걸 알고있었으므로 쉽게 접근할 수 있었다.

다음은 책의 모범답안 코드이다.

#include <bits/stdc++.h>

using namespace std;

int n, m;
int graph[201][201];

// 이동할 네 가지 방향 정의 (상, 하, 좌, 우) 
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

int bfs(int x, int y) {
    // 큐(Queue) 구현을 위해 queue 라이브러리 사용 
    queue<pair<int, int> > q;
    q.push({x, y});
    // 큐가 빌 때까지 반복하기 
    while(!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        // 현재 위치에서 4가지 방향으로의 위치 확인
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            // 미로 찾기 공간을 벗어난 경우 무시
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            // 벽인 경우 무시
            if (graph[nx][ny] == 0) continue;
            // 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
            if (graph[nx][ny] == 1) {
                graph[nx][ny] = graph[x][y] + 1;
                q.push({nx, ny});
            } 
        } 
    }
    // 가장 오른쪽 아래까지의 최단 거리 반환
    return graph[n - 1][m - 1];
}

int main(void) {
    // N, M을 공백을 기준으로 구분하여 입력 받기
    cin >> n >> m;
    // 2차원 리스트의 맵 정보 입력 받기
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%1d", &graph[i][j]);
        }
    }
    // BFS를 수행한 결과 출력
    cout << bfs(0, 0) << '\n';
    return 0;
}

거의 똑같은데, 한가지 다른점이 있다. 나는 dist배열을 따로 써서 최단거리를 계산해서 저장하는 용도로 사용 했다. 근데 책의 코드에서는 입력받을 때 썼던 graph배열을 그대로 최단거리 계산하는데에도 사용했다.

이게 왜 되는지 생각해보니까, graph에서 갈 수 있는길은 1로 표현되는데, 그렇다면 갈 수있을때마다 1을 더해주어서 출력하면 그것이 최단거리가 되기 때문이다. 참신하네,,

근데 이 방법은 갈수 있는 공간과 못가는 공간이 0,1 이렇게 두가지 말고 다양하게 표현된다면 사용할 수 없는 방식이니까 내 방법도 알아둬야 한다.