벌꿀채취 문제, dfs 와, 최대값을 구하는 것을 어떻게 할 것인지에 대해서 처리하는 문제입니다. 어떤 자료 구조를 써주어야 하는지, 그리고 값은 어떻게 저장을 하고 있어야 하는지에 대해서 헷갈렸습니다. 그리고 임의로 첫번째 간것에 대해서 0 처리를 해줬는데, 이렇게 했을 경우 반례가 생깁니다. 그러므로 정확히 코딩을 하기 위해서 visit 를 해주고, 그것에 대해서도 visiit map 을 넣어두고 코딩에 적용을 해야 합니다. find_max_2 함수에 대해서 정리를 해보도록 하겠습니다. 그럼 2차원 배열이 되서 헷갈릴 수도 있는데? 오께이. 최대한 헷갈리지 않도록... 만약 다른 문제에서 여러번 3회 이상이면 동시에 짜줄 텐데 그러지 않기 때문에. 그리고 dfs 로 풀기 위해서 가져가야하는 것이 인덱스 그리고 섬과 스퀘어 입니다. 그리고 최대값을 계속해서 가져가야 합니다. 리턴해주는 구문이 인덱스가 끝에 갔을 때 입니다. 계산을 모두 마춰준다음에, 그 다음에 현재것을 적용하는 것과 적용하지 않고 다음칸으로 가는 경우 2가지 경우에 대해서 풀이를 하였습니다. dfs 와 세세한 구현을 위해서 시간이 .3시간 30분 소요되었습니다. a형의 경우에 3시간에 시간분배에 대해서도 생각을 하겠습니다. 그런데 설계가 되지 않으면 풀이가 안되니... 한번 함수에 대해서 그리고 함수의 변수는 어떻게 들어가야 좋을지에 대해서도 말로 풀어놓고 시작하면 좋을 것 같습니다. |
/* 1300 */ #include <iostream> #include <algorithm> #include <queue> #include <memory.h> #include <vector> #define SIZE 15 // 11; using namespace std; int map[SIZE][SIZE]; int visit[SIZE][SIZE]; int N, M, C, x, y, ny; int ans_1, ans_2, ans; int get_1[11], get_2[11]; int max_ans_1, max_ans_2; struct points { int x, y; }; queue<points> que; points que_store[5], max_store[5]; void problemIn() { cin >> N >> M >> C; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) cin >> map[i][j]; } void que_init() { queue<points> empty; swap(que, empty); } void init() { memset(get_1, 0, sizeof(get_1[0])*M); memset(get_2, 0, sizeof(get_1[0])*M); max_ans_1 = max_ans_2 = ans = 0; ans_1 = ans_2 = 0; que_init(); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { map[i][j] = 0; visit[i][j] = 0; } } for (int i = 0; i < 5; i++) { que_store[i].x = 0; que_store[i].y = 0; max_store[i].x = 0; max_store[i].x = 0; } } /* i,j 로 돌면서, 0,0 일때 검사를 들어옵니다. 큐에 넣어야 겠네. 그리고 0,1 를 검사합니다. 맵안에 들어오는지, 방문한 적은 없는지, 오케이 그리고 큐에 들어온 숫자가 M 의 숫자와 동일하면 반복문을 종료합니다. 큐에는 x,y 좌표가 들어있습니다. 만약 큐에 들어온 숫자가 M 의 숫자와 동일하기 전에 break 가 되면? que를 리셋하고, 다시 다음 i,j 부터 숫자를 찾기 시작합니다. 찾았으면, 그 벌꿀의 위치와 숫자만 저장하고 리셋합니다. 비지트? 안해줘도 되는 이유가 어차피 뒤에서 부터 찾기 때문에, que_store 에 저장을 해야 하는데... 어떻게 저장을 하고 바꿔치기를 할 수 있을까? 잠깐 0이 되더라도, 앞에것과 짝을 이룰수가 있겠구나, 아닌데, 3이라고 하면, 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 */ void take_area(int x, int y) { while (1) { if (que.size() == M) { // 벌통연결할 것을 찾았으면, 이제 que_1에 첫 일꾼 정보가 담김, for (int i = 0; i < M; i++) { que_store[i].x = que.front().x; que_store[i].y = que.front().y; get_1[i] = map[que.front().x][que.front().y]; que.pop(); } return; } if (y + 1 < N && visit[x][y+1] == 0) { que.push({ x,y + 1 }); y += 1; } else { // 벌통이 연결이 안되면, que_init(); return; } } } /* */ void find_max_1(int pos, int sum, int square) { sum += get_1[pos]; square += get_1[pos] * get_1[pos]; ans_1 = max(ans_1, square); if (pos + 1 == M) { return; } if (sum + get_1[pos + 1] <= C) { find_max_1(pos + 1, sum, square); } // 현재 pos 는 건너뛰기. sum -= get_1[pos]; square -= get_1[pos] * get_1[pos]; if (sum + get_1[pos + 1] <= C) { find_max_1(pos + 1, sum, square); } } void find_max_2(int pos, int sum, int square) { sum += get_2[pos]; square += get_2[pos] * get_2[pos]; ans_2 = max(ans_2, square); if (pos + 1 == M) { return; } if (sum + get_2[pos + 1] <= C) { find_max_2(pos + 1, sum, square); } // 현재 pos 는 건너뛰기. sum -= get_2[pos]; square -= get_2[pos] * get_2[pos]; if (sum + get_2[pos + 1] <= C) { find_max_2(pos + 1, sum, square); } } /* 먼저 get_1 행렬을 완성하기. 그리고 그 get_1 을 완성했으면, 바로 최대값을 구하고 그 값을 저장하고 다시 get_1 행렬을 하고, 다시 최대값을 찾아서 비교하기. 그렇게 해서 제일 첫번째로 가장 큰 값을 구하고, 그곳을 제외한 곳에서 위에 것을 반복하도록 하겠습니다. 처음 찾은 곳을 어떻게 제거 할 수 있을까? 처음 찾았을 때의 영역에 대해서 위치를 저장해두어야 하는가? */ void solve() { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { que.push({ i,j }); take_area(i, j); find_max_1(0, 0, 0); if (ans_1 > max_ans_1) { for (int i = 0; i < M; i++) { max_store[i].x = que_store[i].x; max_store[i].y = que_store[i].y; } max_ans_1 = ans_1; } } } // 위에서 구한 최대값 영역을 지우기 for (int i = 0; i < M; i++) { visit[max_store[i].x][max_store[i].y] = 1; } // 2번째로 큰 영역 구하기 ans_1 = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (visit[i][j] == 0) { que.push({ i,j }); take_area(i, j); find_max_1(0, 0, 0); if (ans_1 > max_ans_2) { for (int i = 0; i < M; i++) { max_store[i].x = que_store[i].x; max_store[i].y = que_store[i].y; } max_ans_2 = ans_1; } } } } ans = max_ans_1 + max_ans_2; max_ans_1 = 0; max_ans_2 = 0; } int main(void) { int T; cin >> T; for (int tc = 1; tc <= T; tc++) { problemIn(); solve(); cout << "#" << tc << " " << ans << endl; init(); ans = 0; } return 0; } |