sonamu94kr   4년 전

bfs방식으로 풀었고 한 번씩 방문이 끝날때마다 방문 배열 초기화 했습니다.

어느 부분을 줄여야 시간초과가 발생하지 않을지 모르겠습니다..

seico75   4년 전

답은 잘 나오나요?57라인 break 가 for 두개를 벗어나지 못해서 -1 이 나와야할 상황에서 양수가 나올 수 있을 것 같습니다.

시간은...
지금 접근은 토마토가 있는 점에 대해서 이것이 어떻게 사방으로 퍼져나가는지 계산을 합니다. 각 점에 대해서 루프를 돌기 때문에 

10000000000000

00000000000000

00000000000000

00000000000001

이런 류의 케이스에 제일 위의 1에서 모든 칸을 다 매우고, 끝나면 다시 마지막 1에서 다시 모든 칸으로 뻣어가며 업데이트 합니다.

82, 84 부분을 조금 조정해도 검색 수를 좀 줄 수 있겠지만....

각 턴에 따라서 1이 어떻게 전파되는지를 계산하면서 도는 것이 일반적인것 같습니다.

즉, 아래 처럼이 아니라 그 아래처럼 채워가는 것이 더 연산량이 적을 것 같습니다.


 toma   check  check

1000     0123    0122

0000     1234    1221

0001     234-     2210

---------------------------------------

 toma   check  check

1000   01--   0122

0000   1--1   1221

0001   --10   2210


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