quf9484   4년 전

처음에 7, 22번 줄 처럼 코딩을 했는데 메모리 초과가 났습니다.

그래서 동적할당 하는게 잘못됐나 싶어서 정적할당하고 초기화를 시켜줬더니 런타임 에러가 납니다 ㅜㅜ

제가 애초에 설계를 잘못한건가요??

도저히 모르겠어서 올립니다...

nahwasa   4년 전

늅늅이라 주제넘지만 동일 언어로 진행하시는 분이라 정이 가서(?) 주제넘게도 몇마디 적어봅니다

1. 자바에서 굳이 최대치 배열을 미리 만들어둘 필요는 없습니다. 입력받으신 M값으로 초기화하셔도 됩니다. 

2. Scanner 입력과 System.out 출력은 데이터가 많을 경우 시간을 엄청나게 잡아먹습니다. 
  https://www.acmicpc.net/blog/v... 
  https://www.acmicpc.net/blog/v... 

3. 5000x5000짜리 int 배열 해봐야 100mb 정도입니다. 큐에서 많이쓰셨습니다. 

4. 각 지점에 대해 일단 지도에 그리고 bfs를 진행하는 부분은 아이디어는 좋으시나, 다소 비효율적인 부분이 있습니다.
예를들어 입력이 단 두개 들어오지만 0 0 5000, 5000 5000 5000 이런식이면 시간이 엄청나게 걸리게되겠죠.
   또한 bfs에서 상하좌우 전부 집어넣어야 해서 메모리초과의 가능성도 있구요.
   또한 인접 체크에서 문제가 생길 수 있는데 어제 말씀드렸듯이 이 방식으로는 0 0 1과 0 3 1을 인접하다고 판단합니다.
    오늘 한번 풀어보니 저건 인접하다고 하면 안되는게 맞습니다.
5. 요 문제 해결 정해는 union-find 방식일듯합니다.
일단 전 작성자님과 비슷하게 진행하되, 지도를 미리 그리지 않고 그냥 단순하게 전체 지점에 대해 서로 인접하냐를 체크하는 방식으로 해봤습니다.
( 이 경우 bfs가 매우 간단해짐)
이하 코드 올려두었으니 혹시 참고하지 않고 직접 해보시려면 패스해주세요! 그리고 union-find 찾아보신 후 그걸로 풀어보시는것도 좋을듯합니다.

quf9484   4년 전

먼저 이렇게 정성스럽게 답변을 남겨주시다니 너무나 감사합니다 ㅜㅜ

복받으실거에요 ㅜㅜ

오늘도 좋은 하루되세요!!

p.s 반례적어주신 거는 이해했습니다(원이라고 생각하면 당연한 문제더라고요)

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