10216 Count Circle Group

메모리 초과 난 코드.

애초에 모든 점들을 방문하는건 무리!

dfs에서 스택을 엄청나게 잡아먹기 때문에 2500 2500 5000 이런 식으로 입력하면 메모리가 날라간다.

#include <iostream>

#include <queue>

//#include<cstring>

using namespace std;

int map[5001][5001];

int visited[5001][5001];

int R[5001];

int px[4] = { 1, 0, -1, 0 }; // down right up left

int py[4] = { 0, 1, 0, -1 };

bool flag = false;

struct pos{

int x;

int y;

};

pos arr[5001];

queue<pos> Q;

int cnt;

int index = 0;

int N;

void F(int xt, int yt, int R){

for (int i = xt - R; i <= xt + R; i++){

for (int j = yt - R; j <= yt + R; j++){

if (i < 0 || j < 0 || i >= 5001 || j >= 5001 || (i==xt && j==yt)) continue;

if (map[i][j] != 1) map[i][j] = 1;

}

}

}

void dfs(int x, int y){

if (index >= N) return;

if (x == arr[index].x && y == arr[index].y){

cnt--;

flag = true;

return;

}

if (flag) return;

if (visited[x][y] == 1) return;

else visited[x][y] = 1;

for (int i = 0; i < 4; i++){

int x_ = x + px[i];

int y_ = y + py[i];

if (x_ < 0 || x_ >= 5001 || y_ < 0 || y_ >= 5001) continue;

if (map[x_][y_] == 0) continue;

if (map[x_][y_] == 1 && visited[x_][y_] == 0){

dfs(x_, y_);

}

}

}

void init(){

for (int i = 0; i < 5001; i++){

for (int j = 0; j < 5001; j++){

visited[i][j] = 0;

map[i][j] = 0;

}

}

for (int i = 0; i < 5001; i++){

arr[i].x = 0;

arr[i].y = 0;

}

}

int main(){

int T;

cin >> T;

while (T--){

init();

int x, y;

cin >> N;

cnt = N;

for (int i = 0; i <N; i++){

cin >> x >> y >> R[i];

arr[i].x = x;

arr[i].y = y;

map[x][y] = 1;

}

int i = 0;

int j = 0;

while (j < N){

int nx = arr[j].x;

int ny = arr[j].y;

F(nx, ny, R[i++]);

j++;

}

j = 0;

while (j < N){

int nx = arr[j].x;

int ny = arr[j].y;

index = ++j;

dfs(nx, ny);

flag = false;

}

cout << cnt << endl;

}

system("pause");

return 0;

}

구글링을 통해 가장 이해하기 쉽고 유익한 코드를 발견하였다.

DFS와 문제를 코드화 시키는데 있어서 매우 큰 도움을 준 코드이다.

1. 문제 자체를 적군의 진영(A)을 기준으로 접근 (기존에 내가 짠 코드는 2차원 배열로 map을 설정해놓고 불필요한 계산들이 많았다.)

2. Ai 에서 Aj로 갈 수 있는지만 확인(2차원 벡터 사용) 

    ex) 0 0 1 // 2 0 1 이면 ad[0] 에 1을 push_back , ad[2] 에 0을 push_back. 즉 0과 1이 연결 되어 있다/아니다 자체가 아니라 인접한 An의 인덱스를 넣어준다. 여기서 ad[0] , ad[2] 에 들어가는 인덱스는 S[0] 과 S[2] 를 뜻한다. 즉 S는 애초에 x,y,d 값을 모두 가졌다. 즉, 대부분 인덱스(i/j)는 x나 y 좌표 중 하나가 아니라 한 쌍으로 생각해야 한다!

3. dfs 짠 부분이 매우 대박이다. 난 절대 생각하지 못했을 방법이다. dfs가 return value 가 있지만 무시할 수 도 있다는 점!

즉, 문제에서는 연결되어 있다면 한 개의 진영으로 보기 때문에 특정 좌표에서 연결된 다른 진영까지 모두 dfs로 탐색하되 count 에 전달되는 return 값은 한 번 뿐이다!!! 

#include <iostream>

#include <queue>

#include <cstring>

#include <vector>

//#include<cstring>

using namespace std;

#define INF 987654321

typedef long long lld;

struct spot {

int y, x, d;

};

int dist(spot a, spot b){

return (b.x - a.x)*(b.x - a.x) + (b.y - a.y)*(b.y - a.y);

}

bool isConnected(spot a, spot b){                           // 이런 방법을 왜 고려하지 않았을까.

return (a.d + b.d)*(a.d + b.d) >= dist(a, b);

}

bool visit[3001];

int dfs(vector<int> adj[], int pos){

if (visit[pos]) return 0;

visit[pos] = true;

for (int i = 0; i<adj[pos].size(); ++i)

dfs(adj, adj[pos][i]);

return 1;

}

int main(){

int T, i, j, k;

scanf("%d", &T);

while (T--){

int N, x, y, r;

scanf("%d", &N);

spot s[3001];

for (i = 0; i<N; ++i){

scanf("%d %d %d", &x, &y, &r);

s[i] = { x, y, r };

}

vector<int> adj[3001];   // i번째 진영과 연결되는 다른 진영

for (i = 0; i<N; ++i){

for (j = 0; j<N; ++j){

if (i == j) continue;

if (isConnected(s[i], s[j])){    // 여기서 연결되어있는지 확인했으니 그 후에는 확인할 필요가 없다.

adj[i].push_back(j);    // i 번째 진영 - j 번째 진영

}

}

}

memset(visit, false, sizeof(visit));

int count = 0;

for (i = 0; i<N; ++i){

count += dfs(adj, i);   // i 의 값은 row 값으로 Ai ~ Aj를 찾기 위함. 

}

printf("%d\n", count);

}

//system("pause");

return 0;

}

[참고 - http://joonas-yoon.blogspot.kr/2016/03/10216-count-circle-groups.html]