질문 - 인프런 | 커뮤니티 질문&답변

안녕하세요. ㅎㅎ

void dfs(int y, int x, vector<pair<int,int>>&v)
{
    // 열렸으면, dfs를 실행 한 경우, 평균을 내야하는데..
    
    visited[y][x]=1;

여기에 visited를 걸었는데

                if(!visited[i][j])
                {
                    v.clear();
                    visited[i][j] = 1;
                    v.push_back({i,j});

이렇게도 걸었다.

이부분 말씀하시는 거죠?

네 로직상은 문제가 없습니다. 왜냐면

        if(visited[ny][nx]) continue;

ny, nx를 기반으로 continue가 수행되기 때문에 y, x에 관해 중복으로 처리했어도 괜찮습니다.

다만,

이렇게 하시는게 더 깔끔할 거같아요.

#include<bits/stdc++.h>
using namespace std;

int a[54][54], visited[54][54];
int n, l, r, ret, cnt;
const int dy[]={-1,0,1,0}, dx[]={0,1,0,-1};
int sum;
vector<pair<int,int>>v;

void dfs(int y, int x, vector<pair<int,int>>&v)
{
    // 열렸으면, dfs를 실행 한 경우, 평균을 내야하는데..
     
    for(int i = 0 ; i < 4 ;i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
        
        int tmp_cha = abs(a[y][x] - a[ny][nx]);
        
        if(ny < 0 || nx < 0 || n <= ny || n <= nx)  continue;
        if(visited[ny][nx]) continue;
        if(tmp_cha < l || r < tmp_cha)   continue;
        
        // 여기다가 하는데..
        // 한 바퀴가 다 돈 다음에 평균 내야 하잖아..
        // 여기다가 bool type을 둬서, 새로운 함수 만들어서 평균 내야하나??
         
        v.push_back({ny,nx});
        sum += a[ny][nx];
    	visited[ny][nx]=1;
        dfs(ny,nx,v);
    }
}

int main(void)
{
    cin >> n >> l >> r;
    
    for(int i = 0 ; i < n ; i++)
    {
        for(int j = 0 ; j < n ; j++)
        {
            cin >> a[i][j]; // i는 y , j는 x
        }
    }
    
    // 논리는 엇비슷하게 생각해냈는데.. 
    // 이 밑의 것은 아예 구현 방법을 떠올리지 못했어..
    // 구현은 다시 한 번 연습해볼 것!
    
    while(1){   // 끝날때까지 dfs 반복이니까, while이 필요하구나..
        bool flag = 0 ; // 이걸로 dfs 여부 확인이구나..
        // fill(visited[0][0],0,sizeof(visited));
        fill(&visited[0][0],&visited[0][0]+54*54,0);
        for(int i = 0 ; i < n ; i++)
        {
            for (int j = 0 ; j < n ; j++)
            {
                if(!visited[i][j])
                {
                    v.clear(); 
                    v.push_back({i,j});
                    sum = a[i][j];
                    visited[i][j] = 1;
                    dfs(i,j,v);
                    if(v.size()==1) continue;
                    for(pair<int,int> b : v)
                    {
                        a[b.first][b.second] = sum / v.size();
                        flag = 1;
                    }
                }
            }
        }
        if(!flag) break;
        cnt++;
    }
    cout << cnt << '\n';
    return 0;
}

/*
처음에 n l r  입력 받아.
n * n 만큼 입력 받고
인구 차이가 l이상 r이하인 곳은 국경선을 열어서 서로 평균 낼 수 있어.
열린 것은 열린 곳까지의 평균을 나눠 갖는다.
국경선을 처음에 다 열고, 그 다음에 한번에 해야할 듯?
- 한번 열은 것을 재개방 불가능 -> visited 써야하는데?

전체 탐색 dfs인가? - 시간복잡도 봅시다. 50 * 50 || 1<= <= 100
2500C2 인 듯?

하루에 한번만 열리는 것, 이거 fill이나 memset으로 visited 초기화 필요
dfs해도 되겠다.

평범한 dfs에다가 l이상 r 이하 이 조건만 넣으면 될 듯?


connected component..?
*/

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

인프런 커뮤니티 질문&답변

질문