케이를 만드는 것이 문제입니다. 케이를 어떻게 만들 것인가를 고민해봅니다. 그리고 어디서 틀린지 디버깅을 해보도록 하겠습니다. 케이를 만드는 방법이 다릅니다. 보면, 케이를 만드는 방법에서, |
/* 1. 맵을 받고 2. 먼저 케이를 얼마만큼 가능한지 살펴보고, 3. i,j 를 맵 처음부터 끝까지 돌리고, 하나의 i,j 에 대해서 K =1 ... 할 수 있는데까지 해보고, 그곳에서 가능한 집의 숫자를 체크합니다. */ #include <iostream> #include <queue> #include <algorithm> using namespace std; #define SIZE 25 int map[SIZE][SIZE]; int visit[SIZE][SIZE]; int N, M, K, x, y, nx, ny, T; int dx[] = { 0,0,1,-1 }; int dy[] = { 1,-1,0,0 }; int maxVal; int house_cnt; int house_total; struct points { int x, y; }; queue<points> que; void problemIn() { cin >> N >> M; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) cin >> map[i][j]; } void visit_init() { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { visit[i][j] = 0; } } } void check(int i, int j) { x = i; y = j; visit[x][y] = 1; que.push({ i,j }); if (map[x][y] == 1) house_cnt++; if (house_cnt * M >= 1) { // 이익이 난다면 maxVal = max(maxVal, house_cnt); // 현재 하우스 카운트, 0 을 비교해서 하우스 카운트를 가능하다고 놓고, } for (int k = 2; k <= 21; k++) { while (!que.empty()) { x = que.front().x; y = que.front().y; que.pop(); for (int i = 0; i < 4; i++) { nx = x + dx[i]; ny = y + dy[i]; if (nx >= 0 && ny >= 0 && nx < N && ny < N && visit[nx][ny] == 0) { if (map[nx][ny] == 1) house_cnt++; visit[nx][ny] = visit[x][y] + 1; que.push({ nx,ny }); } } if (!que.empty()) { if (abs(que.front().x - i) + abs(que.front().y - j) == (k - 1)) { if (house_cnt * M >= k*k + (k - 1)*(k - 1)) { // 이익이 난다면 maxVal = max(maxVal, house_cnt); // 현재 하우스 카운트, 0 을 비교해서 하우스 카운트를 가능하다고 놓고, } break; } } } } } void solve() { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { check(i, j); // 맵의 i,j 에서 K를 늘려가면서 확인해보도록 하겠습니다. visit_init(); if (!que.empty()) { int que_length = que.size(); for (int a = 0; a < que_length; a++) { que.pop(); } } house_cnt = 0; } } } int main() { cin >> T; for (int tc = 1; tc <= T; tc++) { maxVal = 0; problemIn(); solve(); cout << "#" << tc << " " << maxVal << endl;
} } |
오께이. 정확하게 설계를 하고 풀이하는 것이 중요합니다. 인덱스 하나 차이에 따라서 오류가 날 수 있으므로, 단순하게 내가 먼저 무엇을 알고 있느냐도 중요하지만, 스타를 어떻게 만들까? 아니면 인덱스를 어떻게 새로 만들고, 새로 활용할 수 있을까도 고민하면 좋습니다. 그리고 스스로 문제를 풀 때, 가져가야 하는 인덱스가 있고, 그것을 머리로 풀 수 있으면? 코딩도 가능합니다. 미는 큐를 사용해서 확장하는 형식으로 만들었으나, 다른 사람의 코드는 인덱스를 만들어서 마름모를 만들어 주었습니다. |