jjy1715   4년 전

제가 큐 작성해서 했는데 답 다 그대로 나오는데 자꾸 틀리다고 나오네요

chungma900   4년 전

11 11
0 0 0 0 1 0 -1 -1 0 0 0
0 -1 1 1 0 0 1 1 0 0 0
0 0 0 0 -1 1 0 0 1 0 0
0 0 -1 0 0 -1 -1 0 0 0 -1
1 1 -1 0 0 1 0 0 0 -1 1
-1 0 0 0 0 0 1 0 0 1 0
0 1 0 -1 0 0 0 0 1 1 1
0 0 0 1 0 0 0 0 0 -1 0
0 0 0 0 0 0 0 0 0 0 -1
-1 0 0 0 0 0 1 1 0 0 1
-1 0 0 0 0 -1 -1 0 0 0 -1
26

답은 4입니다. 시작할때 좌표 순회하다가 토마토가 있으면 bfs를 돌리는게 아니라 일단 큐에다가 토마토를 전부넣고 bfs를 돌려야 됩니다.

jjy1715   4년 전

답변 너무 감사드립니다. 큐에 토마토를 전부 넣고하니까 되네요

그런데 좌표를 순회하다가 토마토가 있을때 큐에 넣는거랑 처음부터 토마토를 큐에 넣는거랑 차이점이 뭔가요? 


예를들어

3 3        이라고 할 경우 두가지 전부 방문배열에는  1 2 3   로 채워지게 되는데요ㅠㅠ

1 0 0                                                                                2 3 2  

0 0 0                                                                                3 2 1

0 0 1

chungma900   4년 전

채워지기는 할텐데 큐에다가 토마토 한개를 넣고 시작을 하면 토마토 한개를 기준으로만 퍼지고 만나지 않는 다른 토마토들은 퍼지지 않고 있기에 문제가 원하는 답이 나오지 않죠. 왜냐하면 모든 토마토를 기준으로 첫번째 날부터 일제히 퍼지기 시작해야 되니까요. 시간을 구하는게 아니라 그냥 퍼지게만 할거면 위와 같은 소스로 해도 상관은 없습니다. 다만 시간은 더오래 걸리죠.

jjy1715   4년 전

제가 위에서 작성한 코드에서 count는 bfs 함수 호출할때마다 1부터 시작해서 방문배열 v[i][j]에 차례대로 일수를 넣고 있는데요, 만약 이미 방문한 좌표를 만나게 되면 더 작은 일수로 채워집니다. 결국 모든 토마토를 방문하게 되면 가장 작은 일수들로만 채워지게 되어 답이 틀리지는 않을거라고 생각하는데요,

혹시 문제가 되는 부분이 익은 토마토 하나하나를 방문해야하니 시간이 그만큼 오래걸려서 틀렸다고 하는건가요?

chungma900   4년 전

그렇죠. 배열이 작을때는 답이 잘나오는듯하지만 배열이 커지면 커질수록 오차도 커집니다.

jjy1715   4년 전

네 답변 감사합니다.

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