틀린 이유가 궁금합니다

작성한 질문수 15

0

안녕하세요 wls님 ㅎㅎ 주석을 제가 다 달았는데요. 혹시 이부분 참고해서 다시 짜보시겠어요?

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

int map[51][51];
int dy[4] = { 1,-1,0,0 };
int dx[4] = { 0,0,1,-1 };
int visited[51][51];
//int united[51][51];
int n,l,r,uni_cnt,day;
vector<pair<int, int>> uni;

// 연합한 나라 평균인구수로 변환
void new_person() {
    int sum_people = 0;
    for (pair<int,int> e:uni) {
        sum_people += map[e.first][e.second];
    }
    for (pair<int, int> e : uni) {
        map[e.first][e.second] = sum_people / uni.size();
    }
}

// 연합한 횟수 반환 DFS
// 이게 뭔가 좀 별로임. int 형 dfs자체가 cnt를 반환하는 거아님? 근데 왜 이걸 매개변수로 또 넘겨야 됨?
// 이런식으로 하는게 어떨까요?
int dfs2(int y, int x){
    visited[y][x] = 1;
    int ret = 1; 
    for(int i = 0; i < 4; i++){
        ret += dfs(ny, nx);
    }   
    return ret;
}
int dfs(int y, int x, int cnt) {

    uni.push_back({ y,x });
    visited[y][x] = 1;
    //united[y][x] = 1;
    for (int i = 0; i < 4; i++) {
        int next_y = y + dy[i];
        int next_x = x + dx[i];
        if (next_y < 0 || next_y >= n || next_x < 0 || next_x >= n)
            continue;
        if (visited[next_y][next_x])
            continue;
        /*if (united[next_y][next_x])
            continue;*/
        if (abs(map[next_y][next_x] - map[y][x]) < l ||
            abs(map[next_y][next_x] - map[y][x]) > r)
            continue;
        
        //united[next_y][next_x] = 1;
        cnt = dfs(next_y, next_x, ++cnt);
    }
    return cnt;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n>>l>>r;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
        //map을 변수명으로 쓰는 것은 좋지 않음. map 자료구조.
            cin >> map[i][j];

    while (1) {
        //flag로 바꾸는 게 좋음. flag = 0 > 1 이렇게.
        uni_cnt = 0;
        // 더 이상 연합 없을 때까지모든 나라에 대해 dfs
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int now_cnt = dfs(i, j,0);
                if (now_cnt) {
                    // 연합을 했다면
                    // 인구수 평균
                    uni_cnt++;
                    new_person();
                    // uni 초기화
                    uni.clear();
                }
                else {
                    // 연합 하나도 없으면 uni에서 빼기
                    // dfs 처음에 무조건 uni에 push하고 시작하니까
                    // 이렇게 하지 말고. uni clear를 아래에 놓던가 해야됨. 로직이 중복됨. 
                    uni.pop_back();
                    // 왜? 이 부분 방문했는데 왜 갑자기 0으로?
                    visited[i][j] = 0;
                    //united[i][j] = 0;
                }
            }
        }

        //memset(united, 0, sizeof(united));
        memset(visited, 0, sizeof(visited));
        

        if (uni_cnt == 0)
            break;

        // 날짜 증가
        day++;
    }

    cout << day << "\n";

    return 0;
}

// 틀린 이유
// - 시간초과
//   --> 연합된 나라의 인구를 평균인구수로 바꿀 때
//   --> 처음에는 전부 하나하나 돌면서 연합인지 확인 후 인구수 더했음
// - DFS 반환 후 cnt값 갱신 안 해줌
// - uni 벡터 초기화 위치
// - visited 초기화 위치

0

안녕하세요 wls님 ㅎㅎ

이거 예제 5번이 통과가 안되는데 혹시 확인해보셨나요?

확인부탁드립니다.

감사합니다.