[Algorithm] C++ 부분 영역 넓이 구하기(Graph, DFS)

세계인의 타임킬링게임 "지뢰찾기"게임에서 특정 블럭을 눌렀을때 막혀있지 않은 최대 면접을 구하여 OPEN해줄때 사용할 수 있는 면적구하기 알고리즘 입니다. Graph, DFS에 관련해서는 미로찾기(graph traversal)을 먼저 읽고 오면 도움이 됩니다.

 

 

이전 포스트에서 언급한바와 같이 Graph - DFS ( Depth First Search ) 알고리즘은 완전 탐색 즉 모든 노드를 방문할 수 있는 알고리즘입니다. 이 알고리즘은 조금 응용해서 방문할 수 있는 모든 노드를 방문하면 결국은 방문수가 해당 node group의 넓이가 됩니다.

 

 문제

아래와 같은 지도가 존재할때 빈칸으로 이루어진 영역중 최대 크기 영역의 크기를 구해봅시다.

 

사전 정의

다음의 설명들에 사용된 코드들은 아래와 공통 코드들은 미로찾기(graph traversal)의 공통코드들을 재활용합니다.

 

최대 넓이 구하기

일단 DFS함수를 하나 만들고 각 노드별로 넓이를 구합니다 ( 방문노드의 합 ), 이때 방문한 노드는 넓이를 구하지 않습니다.

int dfs_area(vector<vector<int>> & map, vector<vector<int>> & visited, int x, int y){
    int theWays = 1;
    
    visited[y][x] = 1;
    
    if(moveable(map, visited, x-1, y))
        theWays += dfs_area(map, visited, x-1, y); // left
    if(moveable(map, visited, x+1, y))
        theWays += dfs_area(map, visited, x+1, y); // right
    if(moveable(map, visited, x, y-1))
        theWays += dfs_area(map, visited, x, y-1); // up
    if(moveable(map, visited, x, y+1))
        theWays += dfs_area(map, visited, x, y+1); // down
    
    return theWays;
}

int main(int argc, const char * argv[]) {
    
    vector<vector<int>> map = {
        {0, 0, 0, 1, 1, 0, 0},
        {0, 0, 0, 1, 1, 0, 0},
        {0, 1, 1, 1, 1, 1, 1},
        {1, 0, 0, 1, 0, 0, 0},
        {1, 0, 0, 1, 0, 0, 0},
    };
    
    print_map("MAP", map);
    cout << endl;
    
    vector<vector<int>> visited(map.size(), vector<int>(map[0].size()));
    
    int max_area = 0;
    // 모든 노드의 최대 넓이를 구합니다.
    for(int y=0;y<map.size();y++){
        for(int x=0;x<map[0].size();x++){
            if(map[y][x] == 1) continue;
            if(visited[y][x] == 1) continue;
            
            auto area = dfs_area(map, visited, x, y);
            if(max_area < area) max_area = area;
        }
    }
    
    cout << "Max Area Size : " << max_area << endl << endl;
    
    print_map("VISTED", visited);
    
    return 0;
}

 

출력값은

결과	방문지

지도상에 방문할수있는 모든 노드를 방문하였고 최대 크기 area도 찾아 냈습니다.

 

지뢰찾기

이 프로그램을 지뢰찾기에 응용해 봅시다.

사용자가 (1, 1) 좌표 를 클릭했다 하면 main program만 조금 수정합니다.

int main(int argc, const char * argv[]) {
    
    vector<vector<int>> map = {
        {0, 0, 0, 1, 1, 0, 0},
        {0, 0, 0, 1, 1, 0, 0},
        {0, 1, 1, 1, 1, 1, 1},
        {1, 0, 0, 1, 0, 0, 0},
        {1, 0, 0, 1, 0, 0, 0},
    };
    
    print_map("MAP", map);
    cout << endl;
    
    vector<vector<int>> visited(map.size(), vector<int>(map[0].size()));
    
    int x = 1, y = 1;
    auto area = dfs_area(map, visited, x, y);
    cout << "Area Size from (" << x << "," << y << ") is " << area << endl << endl;
    
    print_map("VISTED", visited);
    
    return 0;
}

결과	방문지

(1,1) 좌표를 클릭했을때 속해 있는 area의 넓이를 구했고 방문지 노드도 모두 구했다.

 

이제!!! 지뢰게임을 만들어 보시라...

 

아래에 full source를 올려둡니다. 여러가지 테스트 해봅시다.

//
//  main.cpp
//  area
//
//  Created by Jack Kim on 2023/06/09.
//

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

class location{
public:
    int x;
    int y;
    shared_ptr<location> prev;
public:
    location(int x, int y, shared_ptr<location> prev)
    : x(x), y(y), prev(prev) {}
};

bool moveable(vector<vector<int>> & map, vector<vector<int>> & visited, int x, int y){
    if(x < 0 || x > map[0].size()-1) return false;
    if(y < 0 || y > map.size()-1) return false;
    if(map[y][x] != 0) return false;
    if(visited[y][x] != 0) return false;
    
    return true;
}

void print_map(const string & title, vector<vector<int>> & map){
    int width = (int)map[0].size();
    int height = (int)map.size();
        
    cout << "[" << title << "]" << endl;
    for(int x=0;x<width*2+1;x++)cout << "─"; cout << endl;
    for(int y=0;y<height;y++){
        cout << "│";
        for(int x=0;x<width;x++){
            string ch = " ";
            switch(map[y][x]) {
                case 1: ch  = "▒"; break;
                case 0: ch  = " "; break;
                case 9: ch  = "+"; break;
            }
                        
            cout << ch ;
            if(x != width-1)
                cout << " ";
        }
        cout << "│" << endl;
    }
    for(int x=0;x<width*2+1;x++)cout << "─"; cout << endl;
}

int dfs_area(vector<vector<int>> & map, vector<vector<int>> & visited, int x, int y){
    int theWays = 1;
    
    visited[y][x] = 1;
    
    if(moveable(map, visited, x-1, y))
        theWays += dfs_area(map, visited, x-1, y); // left
    if(moveable(map, visited, x+1, y))
        theWays += dfs_area(map, visited, x+1, y); // right
    if(moveable(map, visited, x, y-1))
        theWays += dfs_area(map, visited, x, y-1); // up
    if(moveable(map, visited, x, y+1))
        theWays += dfs_area(map, visited, x, y+1); // down
    
    return theWays;
}

int main(int argc, const char * argv[]) {
    
    vector<vector<int>> map = {
        {0, 0, 0, 1, 1, 0, 0},
        {0, 0, 0, 1, 1, 0, 0},
        {0, 1, 1, 1, 1, 1, 1},
        {1, 0, 0, 1, 0, 0, 0},
        {1, 0, 0, 1, 0, 0, 0},
    };
    
    print_map("MAP", map);
    cout << endl;
        
    // 최대 넓이 영역 크기 구하기
    {
        vector<vector<int>> visited(map.size(), vector<int>(map[0].size()));
        
        int max_area = 0;
        // 모든 노드의 최대 넓이를 구합니다.
        for(int y=0;y<map.size();y++){
            for(int x=0;x<map[0].size();x++){
                if(map[y][x] == 1) continue;
                if(visited[y][x] == 1) continue;
                
                auto area = dfs_area(map, visited, x, y);
                if(max_area < area) max_area = area;
            }
        }
        
        cout << "Max Area Size : " << max_area << endl << endl;
        
        print_map("VISTED", visited);
    }
    
    // 특정지점에서 넓이 구하기 (1,1)
    {
        vector<vector<int>> visited(map.size(), vector<int>(map[0].size()));

        int x = 1, y = 1;
        auto area = dfs_area(map, visited, x, y);
        cout << "Area Size from (" << x << "," << y << ") is " << area << endl << endl;

        print_map("VISTED", visited);
    }

    
    return 0;
}