hong4243   4년 전

코드는 정상적으로 돌아가는데 시간초과 문제입니다. 

시간초과가 나는 이유는 

for(int i = 0 ; i < testNumber; i++){
scanf("%d", &testLine);

for(int i = 0 ; i < MAXSIZE; i++){
    for(int j = 0 ; j <MAXSIZE ; j++){
        map[i][j] = 0;
    }
}//initialization


이 부분에서 초기화 할때만 걸리는 시간을 계산했을때 T(총테스트수) * 3000 * 5000^2 여기 부분에서 납니다. 시간을 말도 안대게 잡아먹으니깐요. 근데 이 알고리즘대로라면 초기화 부분이 필요한데, 어떻게 이 문제를 해결하면 좋을까요?

1) 이 알고리즘을 사용하면서 문제 해결

2) 이 알고리즘을 사용해서는 문제를 해결할 수 없다.


전반적인 알고리즘 설명은 

1) map을 0으로 초기화 

2)  한줄씩 들어올때 마다 count++의 값으로 그에 해당하는 범위를 채운다

    (예를들면 처음 들어온거를 계산해 1, 두번째줄의 입력에 따른 범위는 2,...)

    ex) 

1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 
2 0 0 0 0 0 0 0 0 0 0 0 0 0 0         //이 부분에서 1 -> 2 가 되었으므로 둘은 공유하는 범위가 있으므로 --;
2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 
2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
3 3 0 0 0 0 0 0 0 0 0 0 0 0 0 
3 3 3 0 0 0 0 0 0 0 0 0 0 0 0 
3 3 3 3 0 0 0 0 0 0 0 0 0 0 0 
3 3 3 3 3 0 0 0 0 0 0 0 0 0 0 
3 3 3 3 3 3 0 0 0 0 0 0 0 0 0 
3 3 3 3 3 0 0 0 0 0 0 0 0 0 0 
3 3 3 3 0 0 0 0 0 0 0 0 0 0 0 
3 3 3 0 0 0 0 0 0 0 0 0 0 0 0 
3 3 0 0 0 0 0 0 0 0 0 0 0 0 0 

3) 숫자가 변경된다면 즉 원래는 1이었는데 2로 되었다. 이러면 둘의 공유하는 범위가 있는 것임으로 result -- 를 해준다.

4) 최후로 result 를 출력한다.



jwg8679   4년 전

그렇게 하면 초기화에 시간이 너무 오래 걸립니다.

이 문제를 푸는 핵심은 문제의 속성을 파악하는 것입니다.

딱 보면 N이 3000으로 작은 축에 속합니다.

그렇다면 모든 점들과의 거리를 측정하는 코스트는 BF로 해도 3000*3000으로 상당히 작은 축에 속합니다. 

점들과의 거리 측정은 단순히 유클리드 거리를 비교해주시면 됩니다.

하지만 문제는 같은 그룹인지 분류하는 거죠.

문제에서 어떻게든 연결만 되면 하나의 그룹으로 친다고 나와있습니다.

우리는 여기서 그룹이 여러개로 나누어진다는 것을 알 수 있고, Discrete Set을 형성한다는 것을 알 수 있습니다.

Discrete Set이라면 union find 알고리즘을 사용하면 빠르게 두 노드가 같은 그룹에 속하는지 알수 있습니다.

결국 문제는 

연결되는 점들을 찾으면서 연결이 된다면 Union 해주고

맨 마지막에 find로 찾으면서 서로 다른 그룹이 몇 개 나오는지 카운트 해주는 문제가 됩니다.

hong4243   4년 전

아아 알겠습니다!! union이랑 find써서 주소값 으로 풀면 되겠네요!!

저방법으로는 안될것같네요 감사합니다

댓글을 작성하려면 로그인해야 합니다.