[코트트리] 우리는 하나 C++

문제

https://www.codetree.ai/missions/2/problems/we-are-the-one?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

계획 세우기

아래 그림에서 빨간색은 처음 선택한 좌표. 노란색, 초록색은 BFS로 추가되는 좌표

 

[재귀] 도시 k개를 선택하는 모든 경우의 수를 찾아보기

 

[BFS] *전역으로 선언된 visitedBFS 배열을 계속 재사용하기 때문에 BFS를 시작할 때 초기화 해줘야 함*

선택한 k개의 도시를 queue에 넣음

queue에 들어있는 좌표의 상하좌우를 살핌

 

아래 3가지 조건을 만족한다면 queue에 넣기

• 배열의 범위를 벗어난 좌표가 아님
• 이미 방문한 좌표가 아님
• 현재 좌표와 다음 좌표의 차이가 u이상 d이하

방문 체크하고, numOfCity 1 증가

 

풀이

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

using namespace std;

int n, k, u, d, answer;
int arr[10][10];

vector<pair<int,int> > selectedCity;
bool visitedDFS[10][10]={false, };
bool visitedBFS[10][10]={false, };

bool InRange(int x, int y){
    return x>=0 && x<n && y>=0 && y<n;
}

bool CanGo(int x, int y, int diff){
    if(!InRange(x, y)) return false;
    // 방문한 칸 || !(u이상 && d이하)
    if(visitedBFS[x][y] || !(diff>=u && diff<=d)) return false;
    return true;
}

int BFS(){
    // 상(-1,0) 하(1,0) 좌(0,-1) 우(0,1)
    int dx[4]={-1, 1, 0, 0};
    int dy[4]={0, 0, -1, 1};

    int numOfCity = k; // k개의 도시를 선택했으니까 최소 k개
    queue<pair<int,int> > q;
    
    // visited 배열 초기화
    for(int i=0; i<n; ++i){
        for(int j=0; j<n; ++j){
            visitedBFS[i][j]=false;
        }
    }

    //선택한 도시들(selectedCity)을 모두 queue에 넣어줌
    for(size_t i=0; i<selectedCity.size(); ++i){
        q.push(selectedCity[i]);
        visitedBFS[selectedCity[i].first][selectedCity[i].second]=true;
    }

    while(!q.empty()){
        int x=q.front().first, y=q.front().second;
        q.pop();
        for(int dir=0; dir<4; ++dir){
            int nx=x+dx[dir], ny=y+dy[dir], diff=abs(arr[x][y]-arr[nx][ny]);
            if(CanGo(nx, ny, diff)){
                q.push({nx, ny});
                numOfCity++;
                visitedBFS[nx][ny]=true;
            }
        }
    }
    
    return numOfCity;
}

// 재귀로 k개의 도시를 선택
void SelectCity(int curr_num){
    //종료 조건
    if(curr_num==k){
        answer=max(answer, BFS());
        return;
    }

    // 재귀 호출
    for(int row=0; row<n; ++row){
        for(int col=0; col<n; ++col){
            if(visitedDFS[row][col]) continue;
            
            selectedCity.push_back({row, col});
            visitedDFS[row][col] = true;
            SelectCity(curr_num+1);

            selectedCity.pop_back();
            visitedDFS[row][col] = false;
        }
    }
}

int main() {
    // input
    cin >> n >> k >> u >> d;
    for(int i=0; i<n; ++i){
        for(int j=0; j<n; ++j){
            cin >> arr[i][j];
        }
    }
    
    // solution
    SelectCity(0);
    
    //output
    cout << answer << '\n';
    return 0;
}