글 읽기 - 10216 런타임 에러 질문입니다.

quf9484 4년 전 0

다른 질문을 봐도 이해가 되지 않아 올립니다.

25%정도에서 런타임 에러가 나와서 수정했더니 50%에서 런타임 에러가 나옵니다.

고수분들 부탁드립니다 ㅜㅜ

import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;

public class Main {
    static int[][] map;
    
    public static void main(String args[]){
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        
        for(int i = 0; i < N; i++){
            int M = in.nextInt();
            int xArr[] = new int[M];
            int yArr[] = new int[M];
            map = new int[5000][5000];
    
            for(int j = 0; j < M; j++){
                int x = in.nextInt();
                int y = in.nextInt();
                int r = in.nextInt();
                xArr[j] = x; yArr[j] = y;
                denoteCommunicationArea(x, y, r);
            }
            //각 진영의 통신센터 중심지에서만 BFS
            BFS(xArr, yArr);
        }
    }
    
    public static void BFS(int[] x, int[] y){
        Queue<Camp> q = new LinkedList<>();
        int[] dx = {0, 0, 1, -1};
        int[] dy = {1, -1, 0, 0};
        int cnt = 0;
        
        for(int i = 0; i < x.length; i++){
            int x1 = x[i];
            int y1 = y[i];
            
            //다른 진영에서 통신가능 한 곳이라 하나의 진영이라고 생각
            if(map[x1][y1] == 0){
                continue;
            }
            
            q.offer(new Camp(x1, y1));
            map[x1][y1] = 0;
            cnt++;
            while(!q.isEmpty()){
                Camp camp = q.poll();
                for(int k = 0; k < 4; k++){
                    int dirX = camp.x + dx[k];
                    int dirY = camp.y + dy[k];
                    if(dirX >= 0 && dirX < 5000 && dirY >= 0 && dirY < 5000){
                        if(map[dirX][dirY] == 1){
                            q.offer(new Camp(dirX, dirY));
                            map[dirX][dirY] = 0;
                        }
                    }
                }   
            }
        }       
        System.out.println(cnt);         
    }
    
    //각 진영에서 r거리 안에 있는 좌표를 1로 바꾸어 BFS로 1이 있는 곳을 모두 탐색
    public static void denoteCommunicationArea(int x, int y, int r){
        for(int i = x-r; i <= r+x; i++){
            for(int j = y-r; j <= r+y; j++){
                if(i >= 0 && i <5000 && j >=0 && j < 5000){
                    if(getDistance(x, y, i, j) <= (double)r){
                        map[i][j] = 1;
                    }
                }
            }
        }
    }
    
    public static double getDistance(int x1, int y1, int x2, int y2){
        return Math.sqrt(Math.pow(Math.abs(x1 - x2), 2) + Math.pow(Math.abs(y1 - y2), 2));
    }
}

class Camp{
    int x;
    int y;
    
    Camp(int x, int y){
        this.x = x;
        this.y = y;
    }
}

nahwasa 4년 전 1

x, y (0 ≤ x, y ≤ 5,000)

이면 x, y 는 5001개입니다.

map = new int[5000][5000];

에서 문제가 생겼을듯싶네요.

따로 처리하셨는지는 안봤지만, 어쨌든 어떤방식으로든 문제가 생길듯합니다.

일단 x가 5000, r이 0이면(0이상이므로 가능)

69번째줄에서 i<5000으로 튕기겠군요.

nahwasa 4년 전 0

추가로

이 방식으로 하실 경우, 닿아있지 않아도 그룹으로 판단할 여지가 있습니다.

반례입니다.

전 아직 안풀어보긴 했는데 저거 답이 2가 나와야 맞는거죠?!

quf9484 4년 전 1

감사합니다

바운더리 영역을 제대로 체크하지 못했네요ㅜㅜ

quf9484 4년 전 1

그리고 두번째 반례를 들어주신거는 문제지문의

'만약 임의의 통신영역 A_i와 A_j가 닿거나 겹치는 부분이 있다면 진영 i와 진영 j는 직접적으로 통신이 가능하다' 라는 부분으로 미루어보아

닿는다고 생각하기 때문에 통신이 가능한 부분 아닌가요?

nahwasa 4년 전 0

음 애매하네요 말이 좀.

0 0 1
0 2 1

이러면 서로 간격 0으로 닿는거고

0 0 1

0 1 1

이러면 겹치는거구요.

0 0 1

0 3 1

이러면 0 0에서 범위 1, 0 3에서 범위 1이니

사실 0 1 ~ 0 2 부분이 빈다고 봐야하지 않을까 싶긴합니다.

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

문제

문제

출처

ICPC

10216 런타임 에러 질문입니다.

quf9484 4년 전 0

nahwasa 4년 전 1

nahwasa 4년 전 0

quf9484 4년 전 1

quf9484 4년 전 1

nahwasa 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말