📒활용개념]

BFS를 활용한 Greedy Algorithm 풀이

📌문제설명

• 문제
  ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다.

게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.

• 조건
  - maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.
  n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.
  - maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.
  - 처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.
  

📌구현

• 1차시도

  DFS를 활용하여 문제 풀이를 진행하였습니다. 처음부터 Greedy Algorithm을 활용하여 문제 풀이를 진행하겠다고 생각하여 가장 기초적인 DFS를 사용하였으나 시간복잡도 문제를 해결하지 못하여 100점을 받지 못한 풀이 입니다.

#include<vector>
#include <iostream>

using namespace std;

//false 초기화
bool check[100][100];
//이동방향
int l[4] = {0,0,1,-1};
int c[4] = {1,-1,0,0};

int low;
int col;

//최단경로 저장 변수
int min_size = 10000000;

void dfs(int n, int m, int size, vector<vector<int> > maps){
    if(n==low && m == col){
        if(size < min_size){
            min_size = size;
        }
    }
    for(int i=0; i<4; i++){
        int x = n+l[i];
        int y = m+c[i];
        if(x>=0 && x<maps.size() && y>=0 && y<maps[0].size()){
            if(!check[x][y] && maps[x][y]>0){
                check[x][y]=true;
                dfs(x, y, size+1, maps);
                check[x][y]=false;
            }
        }
    }
}

int solution(vector<vector<int> > maps)
{
    int answer = -1;
    
    low = maps.size()-1;
    col = maps[0].size()-1;
    
    dfs(0, 0, 1, maps);
    
    if(min_size < 1000000){
        answer = min_size;
    }
    
    return answer;
}

• 2차시도

  시간복잡도를 해결하기 위해 다양한 방법을 생각했습니다. 예를 들어 2중 for문을 사용한 부분이 있는지 확인하고 어느 부분이 시간복잡도가 많이 사용되었는지 확인하였습니다. 하지만 별다른 문제점을 찾지 못했고 DFS방법 자체가 잘못되었다는 결과를 도출하였습니다. 결국 Greedy Algorithm의 최적화 알고리즘은 BFS(Breadth-First Search)방법을 사용하였습니다. 그 결과 시간복잡도 문제 해결!

#include<vector>
#include<iostream>
#include<queue>
#include<algorithm>

//경로의 최대값 설정
#define MAX 99999

using namespace std;

//이동 방향
int l[4] = {0,0,1,-1};
int c[4] = {1,-1,0,0};

int solution(vector<vector<int> > maps)
{
    int answer = -1;
    const int n = maps.size();
    const int m = maps[0].size();
    
    //넓이 우선 탐색을 위한 Queue
    queue<pair<int, int>> q;
    //탐색 여부 확인 Vector
    vector<vector<bool> > check(n, (vector<bool>(m,true)));
    //각 칸의 최소 거리 저장 Vector
    vector<vector<int> > dist(n, (vector<int>(m, MAX)));
    
    check[0][0]=false;
    q.push({0,0});
    dist[0][0]=1;
    
    while(!q.empty()){
        pair<int, int> front;
        front = q.front();
        q.pop();
        int nowX = front.first;
        int nowY = front.second;
        
        for(int i=0; i<4; i++){
            int newX = nowX + l[i];
            int newY = nowY + c[i];
            
            //탐색 만족 조건
            if(newX>=0 && newX<n && newY>=0 && newY<m){
                if(check[newX][newY] && maps[newX][newY]>0){
                    check[newX][newY]=false;
                    q.push({newX, newY});
                    dist[newX][newY] = min(dist[newX][newY], dist[nowX][nowY]+1);
                }
            }
        }
    }
    
    if(dist[n-1][m-1] < MAX){
        answer = dist[n-1][m-1];
    }
    
    return answer;
}

📌주의점

• 탐욕법 문제풀이에 대하여 DFS 방법만 생각하고 문제를 풀이하면 시간복잡도 문제가 생길 수 있다는 점을 느꼈다.
• DFS와 BFS의 장단점에 대하여 복습하고 상황에 맞는 구현이 필요하다.