wnsdud6992   2년 전

다음과 같이 BFS로 코드를 구성하였고 테스트케이스에 대해서 문제없이 동작합니다. 그런데 계속 시간초과가 나옵니다..

읽어보시고 문제있는 부분 지적해주시면 감사하겠습니다.

wnsdud6992   2년 전

n*m번을 한번 돌면서 값이 1인 지점을 찾아서 큐에 넣는 과정을 한번 진행하고는 그 초기 큐를 가지고 bfs를 도는데

어떻게 bfs가 n*m번 반복문을 돈게 되는거에요??

dldyddlwl   2년 전

같은 곳을 재방문하게 됩니다. 방문을 표시해주는 방법을 쓰시면 좋을 것 같습니다!

wnsdud6992   2년 전

arr[y][x]=1로 저는 토마토밭에 바로 표시를 해주었고 arr[y][x]가 0인 지점만 큐에 넣는 형식으로 재방문을 피했습니다! 그런데도 시간초과가 나네요..

while문이 n*m에 4번 돌고 토마토밭에 안익은 토마토 있는지 확인을 위해 n*m, 초기 토마토값 입력 n*m해서 6백만정도라 생각했는데 어디가 문젠지 모르겠네요.

dldyddlwl   2년 전

그런데 그렇게 되면 원래 arr이 0인 곳도 들어가지는 것 아닌가요?

저는 여기서 아예 visited 이차원배열을 해서 하니까 바로 정답나오더라고요

wnsdud6992   2년 전

bfs를 돌면서 1근처이면서 arr이 0인 곳에 들어가고 d값을 1씩 증가하는데, 이때 들어간 0자리에 값을 1로 바꿔줘서 이미 지나간 자리를 표시했습니다.

dldyddlwl   2년 전

아앗 이유를 찾은 것 같습니다!!!

wnsdud6992   2년 전

저는 처음에 큐에서 뽑고선 방문처리를 해주면 된다고 생각했는데 dldyddlwl분이 언급해주신것처럼

큐에 넣을 때 방문처리를 해야 했습니다. 아니면 큐에서 나오기 전까지 큐에 들어간 그 위치는 0으로 저장 되어있으니까 재방문되어서 시간초과가 나게 된것 같아요.

해결했습니다 감사합니다! 

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