[C++]프로그래머스 게임 맵 최단거리 (BFS)

코딩테스트 연습 - 게임 맵 최단거리 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

완전 탐색으로 풀어야 하는 문제중에 개수가 적은 것은 DFS로 풀어도 되지만, 그렇지 않은 경우에는 BFS로 풀어야지만 효율성을 통과하는 경우가 있다.

게임 맵 최단거리가 그와 같은 경우이다.

 

1.첫 번째 시도 :DFS (효율성 통과 X)

#include<vector>
#include<iostream>
using namespace std;
bool visited[101][101];
int answer = 10001;
void DFS(int x, int y, vector<vector<int>> maps, int count)
{
    if(x < 0 || y < 0 || x >= maps.size() || y >= maps[0].size()) //maps주의 maps[1]아니라 maps라고 해야 길이임.
        return;
    else if(maps[x][y] == 0 || visited[x][y])
        return;
    else if(x == maps.size() - 1 && y == maps[0].size() - 1)
    {
        if (answer > count)
            answer = count;
        return ;
    }
    visited[x][y] = true;
    DFS(x + 1, y, maps, count + 1);
    DFS(x - 1, y, maps, count + 1);
    DFS(x, y + 1, maps, count + 1);
    DFS(x, y - 1, maps, count + 1);
    visited[x][y] = false;
}
    
int solution(vector<vector<int> > maps)
{
    int count = 1;
    DFS(0, 0, maps, count);
    if (answer == 10001)
        answer = -1;
    return answer;
}

지금까지는 DFS가 익숙해서 DFS형태가 먼저 떠올랐고, 그래서 DFS로 먼저 풀어봤다.

결론적으로 풀이 방법은 맞아서 정확성 측면에서는 100/100이 떴지만, 효율성 측면에서는 0/100이 떴다. 

그 이유는, 길이 막혀있는 경우에 조금이라도 배열이 크다면 모든 배열을 다 돌아야 함으로 시간복잡도가 굉장히 커진다.

 

+ 이차원 배열에서 나는 가로와 세로 사이즈를 각각 maps[0].size() , maps[1].size()로 구했었는데 이는 매우 잘못된 방법이다. 둘 다 가로를 나타내기 때문이다. 세로값을 구하려면 maps.size()이렇게 해야한다.

추가적으로, x,y가 각각 무엇을 담당하고 있는지 정확히 알아야 한다.

 

2.두 번째 시도:BFS (통과)

#include<vector>
#include<iostream>
#include<queue>
using namespace std;
bool visited[101][101];
int answer = 10001;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
int solution(vector<vector<int> > maps)
{
    queue <pair<int, pair<int, int>>> q;
    q.push({1, {0, 0}});
    visited[0][0] = true;
    while(!q.empty())
    {
        int count = q.front().first;
        int x = q.front().second.first;
        int y = q.front().second.second;
        q.pop();
        if (x == maps.size() - 1 && y == maps[0].size() - 1)
        {
            cout << count << endl;
            answer = count;
            break;
        }
        for(int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < 0 || ny < 0 || nx >= maps.size() || ny >= maps[0].size())
                continue;
            else if(visited[nx][ny] || maps[nx][ny] == 0)
                continue;
            visited[nx][ny] = 1;
            q.push({count + 1, {nx, ny}});
        }
    }
    if(answer == 10001)
        answer = -1;
    return answer;
}

아직 익숙치 않다는 이유로 더 효율적인 것을 앎에도 불구하고 시도하지 않았던 BFS방법이다.

우선 BFS는 너비탐색 방식이므로 가장 적은 값이 나왔을 경우에는 즉시 while문을 중단하기 때문에 DFS에서처럼 어떤 경우에도 끝까지 가서 시간초과가 날 일이 없다.

 

키포인트는 

1.BFS는 무조건적으로 queue를 사용한다.

while문을 들어가기 전에 queue와 visited와 같은 값의 초기값을 설정한다.

 

2.while문의 반복 조건은 q가 empty가 되지 않을때까지 이다.

이렇게 q가 비었는지 비지 않았는지를 판단하면 어떤 깊이에서 어떤 요소도 값을 만족하지 않을 경우 continue로 더이상 push가 되지 않고 pop만 일어나기 때문에 더이상 진행할 수 없다면 멈출 수 있게 된다.

 

3.while문의 처음에 등장하는 조건은 각 깊이의 값 할당과 깊이 count값 설정, queue의 pop이 일어나야 한다.

그리고 여기서 break 조건도 할당하는 것이 좋다.

count값은 각 queue에 들어있는 방식으로 갱신시키는 것이 좋다.

 

4.while문 안의 for문을 설정한다.

이것이 바로 너비탐색을 하는 부분이다.

DFS와 달리 재귀는 일어나지 않고, 조건에 맞는 값을 queue에 push하는 과정이 여기서 수행된다.

 

---

앞으로 BFS에 더욱 익숙해지도록 하자.