n*m번을 한번 돌면서 값이 1인 지점을 찾아서 큐에 넣는 과정을 한번 진행하고는 그 초기 큐를 가지고 bfs를 도는데
어떻게 bfs가 n*m번 반복문을 돈게 되는거에요??
7576번 - 토마토
n*m번을 한번 돌면서 값이 1인 지점을 찾아서 큐에 넣는 과정을 한번 진행하고는 그 초기 큐를 가지고 bfs를 도는데
어떻게 bfs가 n*m번 반복문을 돈게 되는거에요??
arr[y][x]=1로 저는 토마토밭에 바로 표시를 해주었고 arr[y][x]가 0인 지점만 큐에 넣는 형식으로 재방문을 피했습니다! 그런데도 시간초과가 나네요..
while문이 n*m에 4번 돌고 토마토밭에 안익은 토마토 있는지 확인을 위해 n*m, 초기 토마토값 입력 n*m해서 6백만정도라 생각했는데 어디가 문젠지 모르겠네요.
bfs를 돌면서 1근처이면서 arr이 0인 곳에 들어가고 d값을 1씩 증가하는데, 이때 들어간 0자리에 값을 1로 바꿔줘서 이미 지나간 자리를 표시했습니다.
저는 처음에 큐에서 뽑고선 방문처리를 해주면 된다고 생각했는데 dldyddlwl분이 언급해주신것처럼
큐에 넣을 때 방문처리를 해야 했습니다. 아니면 큐에서 나오기 전까지 큐에 들어간 그 위치는 0으로 저장 되어있으니까 재방문되어서 시간초과가 나게 된것 같아요.
해결했습니다 감사합니다!
댓글을 작성하려면 로그인해야 합니다.
wnsdud6992 2년 전
다음과 같이 BFS로 코드를 구성하였고 테스트케이스에 대해서 문제없이 동작합니다. 그런데 계속 시간초과가 나옵니다..
읽어보시고 문제있는 부분 지적해주시면 감사하겠습니다.