whdnjqls456   4년 전

DFS 커트 조건 써서 시간초과를 넘겼는데,


50%에서 못 넘기겠습니다;;


이미 올라온 질문들에 적힌 반례들도 다 통과하는데 왜 안되는지 도저히 모르겠습니다 ㅜㅜ;;

도와주십시오 ㅜ_ㅜ...;

ehddml3   4년 전

반례

10
1 1 1 0 0 0 0 1 1 1
1 1 1 1 0 0 0 0 1 1
1 0 1 1 0 0 0 0 1 1
0 0 1 1 1 0 0 0 0 1
0 0 0 1 1 0 0 0 0 1
0 0 0 0 1 0 0 0 0 1
0 0 0 0 1 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0

output: 4

ehddml3   4년 전

그리고 왜 안되느냐는... DFS를 써서 그렇습니당.. BFS를 써보세용. DFS를 써도 되게하려면 visit 값을 적당히 큰수로 초기화시킨 다음에 visit[nx][ny]값보다 m+1이 작으면 그 값으로 바꿔주고 들어가는 방식으로 하면 될지도 모르겠네용

visit[x][y] 위치에 3이라는 depth로 이전에 도착을 했었는데 다른 경로로 2라는 depth값으로 접근하고 싶은데 이미 접근했었다고 접근이 차단당한다면...? 을 생각해보시면 될 것 같네용

whdnjqls456   4년 전

아~ 알겠습니다! 참고해서 다시 짜보겠습니다!

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