bfs 알고리즘이란 & 게임 맵 최단거리 c++

bfs = 너비 우선 탐색

1. Breadth First Search란?

: 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법.

• dfs(깊게)와 달리 넓게 탐색하는 방법!
• 사용하는 경우
  • 두 노드 사이의 최단 경로 찾기
  • 두 노드 사이의 임의의 경로 찾기
• 재귀적으로 동작하지 않음!
• 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 함
  => 무한루프에 빠질 수 있음.
• Queue를 사용

2. bfs 구현

• 절차
  a. 시작 노드를 방문 후 방문 노드로 체크
  b. 큐에 방문된 노드를 삽입.
  c. 큐에서 노드를 꺼내고 방문.
  d. 꺼낸 노드와 인접한 노드들을 모두 방문.
  e. 인접한 노드가 없다면 큐에서 다시 노드를 꺼냄.
  f. 방문된 노드를 큐에 삽입.
  g. 큐에 모든 값이 소진될 때 까지 반복.

3. 프로그래머스 게임 맵 최단거리 문제 (bfs)

- 첫 번째 시도

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

int solution(vector<vector<int> > maps)
{
    int answer = 0;
    int n = maps.size();
    int m = maps[0].size();
    int go[3] = {-1, 0, 1};
    int **visited = new int*[n];
    queue<pair<int, int>> q;
    
    for (int i = 0; i < n; i++)
        visited[i] = new int[m]();
    if ((maps[n - 1][m - 2] == 0) && (maps[n - 2][m - 1] == 0)) // 출구 없는 경우
        return -1;

    q.push(make_pair(0,0));
    visited[0][0] = 1;
    pair<int, int> tmp;
    
    while (q.size())
    {
        tmp = q.front();
        q.pop();
        if ((tmp.first == n - 1) && (tmp.second == m - 1))
            break;
        for (int i = 0; i < 3; i++)
        {
            if ((tmp.first + go[i] >= 0) && (tmp.first + go[i] < m) && (maps[tmp.first+go[i]][tmp.second]) && visited[tmp.first + go[i]][tmp.second] == 0)
            {
                q.push(make_pair(tmp.first+go[i], tmp.second));
                visited[tmp.first + go[i]][tmp.second] = visited[tmp.first][tmp.second] + 1;
            }
            if ((tmp.second + go[i] >= 0) && (tmp.second + go[i] < m) && (maps[tmp.first][tmp.second+go[i]]) && visited[tmp.first][tmp.second+go[i]] == 0)
            {
                q.push(make_pair(tmp.first, tmp.second + go[i]));
                visited[tmp.first][tmp.second+go[i]] = visited[tmp.first][tmp.second] + 1;
            }
        }
    }
    return visited[n-1][m-1];
}

- 두 번째 시도

• segementation falut? 배열 범위가 벗어난게 있나?
  => 확인 해 보니 tmp.first는 범위가 < n이어야 하는데, m으로 되어있었음!
  
  m을 n으로 바꾸고 돌린 결과, 12, 15, 16번 제외하고 전부 성공으로 바뀜!

  if ((tmp.first + go[i] >= 0) && (tmp.first + go[i] < n) && (maps[tmp.first+go[i]][tmp.second]) && visited[tmp.first + go[i]][tmp.second] == 0)

  
  

- 세 번째 시도

• 아무리 생각해도 틀릴 곳이 보이지 않음. 그럼 -1 예외상황 문제가 아닐까?
  => 만약 마지막 visited[n-1][m-1] == 0이면 -1을 추가로 넣어줌.
  

  • 이전 코드에서는 출구 바로 위, 옆만 살피고 -1을 줌!
  • 하지만, 바로 옆이 아닌 곳에서도 다 막혀있으면 못오는 경우가 있다는 걸 파악

• 최종 코드

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

int solution(vector<vector<int> > maps)
{
    int answer = 0;
    int n = maps.size();
    int m = maps[0].size();
    int go[2] = {-1, 1};
    int **visited = new int*[n];
    queue<pair<int, int>> q;
    
    for (int i = 0; i < n; i++)
        visited[i] = new int[m]();
    if ((maps[n - 1][m - 2] == 0) && (maps[n - 2][m - 1] == 0))
        return -1;

    q.push(make_pair(0,0));
    visited[0][0] = 1;
    pair<int, int> tmp;
    
    while (q.size())
    {
        tmp = q.front();
        q.pop();
        if ((tmp.first == n - 1) && (tmp.second == m - 1))
            break;
        for (int i = 0; i < 2; i++)
        {
            if ((tmp.first + go[i] >= 0) && (tmp.first + go[i] < n) && (maps[tmp.first+go[i]][tmp.second]) && visited[tmp.first + go[i]][tmp.second] == 0)
            {
                q.push(make_pair(tmp.first+go[i], tmp.second));
                visited[tmp.first + go[i]][tmp.second] = visited[tmp.first][tmp.second] + 1;
            }
            if ((tmp.second + go[i] >= 0) && (tmp.second + go[i] < m) && (maps[tmp.first][tmp.second+go[i]]) && visited[tmp.first][tmp.second+go[i]] == 0)
            {
                q.push(make_pair(tmp.first, tmp.second + go[i]));
                visited[tmp.first][tmp.second+go[i]] = visited[tmp.first][tmp.second] + 1;
            }
        }
    }
    if (visited[n-1][m-1] == 0) 
        return -1;
    else
        return visited[n-1][m-1];
}

• 풀이

  if ((maps[n - 1][m - 2] == 0) && (maps[n - 2][m - 1] == 0))
         return -1;

  이 코드에서는 바로 주변이 막혀있는 경우만 판단. 없어도 정답이지만, 이 경우에는 불필요하게 while을 돌 필요가 없으므로 남겨둠.

  while(q.size())
  {
  	...
  }

  bfs를 시작함.
  0과 n-1사이 또는 0과 m-1사이인지 체크하고, 벽이 아니면서 방문된 상태인지 판단.
  모든 조건을 만족하는 경우 queue에 넣고 방문처리.
  모든 큐에 있는 값들이 없어지거나, 도착지에 도착하면 종료!

  한가지 중요한 점은, 각 위치마다 최소값을 저장하고 있다는 점.
  이전까지의 최솟값 + 1을 현재 위치에 저장시키며 최종 목적지에 도착했을 때 값을 return하는 형식!