dhedaa   5년 전

while 중첩으로 두번쓰면 시간초과가 나는 문제인가요??

제한 값이 크지않은거같아서 while 두번써서 풀어봤는데 시간초과가 나네요


그리고 다른 질문보다가 

1 1

1

이 테스트 케이스를 봤는데 n과 m이 5 이상의 값이고 '모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다. ' 라고 써있으니까 

처음에 공기를 구분하는 bfs를 돌릴때 (0, 0)부터 시작해도 되는게 맞죠?

choko100   1달 전

안녕하세요, 제 생각에는 visited 체크가 덜 되어서 실행이 끝나지 않는 것 같습니다. 외부에 2면 이상 노출된 cheese 의 visited 를 1 로 변경해주는 부분이 누락된 것 같습니다.

테스트로 아래 반례로 실행해봤는데, 실행이 끝나지 않습니다.

(반례 출처: https://www.acmicpc.net/board/...)

입력

8 9
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 1 1 0
0 1 0 1 1 1 0 1 0
0 1 0 0 1 0 0 1 0
0 1 0 1 1 1 0 1 0
0 1 1 0 0 0 1 1 0
0 0 0 0 0 0 0 0 0

정답

3

choko100   1달 전

그리고 마지막 부분에 적어주신 질문은 맞습니다. 가장자리에는 치즈가 없으므로, (0, 0) 부터 BFS 를 시작하셔도 됩니다.

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