seonjoo2030   2년 전

이번 문제 정답이 나왔는데 궁금한 것이 있어서 질문합니다.

제가 처음에 queue배열을 101 로 지정했는데 런타임 에러가 나오더라구요.

그래서 찾아보니까 101*101로 해야 하는 것 같던데 왜 이렇게 설정해야 하는 걸까요?

4방향의 값들을 다 넣어줘야 하니까 배열을 크게 잡아야 하는건가요??

아 그리고 dfs는 최단경로를 구하는 문제에서는 사용할 수 없는건가요??

djm03178   2년 전

그 큐가 무엇을 담기 위한 큐인지 생각해보면 간단합니다. 방문하려는 칸들에 대한 정보를 넣는 거니까, 당연히 칸의 개수 (행 * 열)만큼 있어야겠죠.

그리고 이 코드는 아주 위험한 코드입니다. 56번째 줄에서 tmp.x와 tmp.y는 배열의 범위를 벗어난 인덱스일 수 있는데, 이럴 경우 map[tmp.x][tmp.y]에는 단 한 번이라도 절대로 접근해서는 안 됩니다. 운이 나쁘면 런타임 에러를 받을 수도 있습니다. 배열에 접근하기 전에 해당 좌표가 맵의 안에 있는 좌표인지 반드시 확인해야 합니다.

그리고 최단 경로는 항상 BFS라고 보시면 됩니다. DFS로는 처음 방문한 경로가 최적인지 알 수 없기 때문에 모든 가능한 경로를 탐색해야 하는데, 이것이 상상을 초월할만큼 오래 걸리기 때문입니다.

seonjoo2030   2년 전

답변 감사합니다!!

그 단 한번이라도 접근하지 않은 조건을 

if (tmp.x < 0 || tmp.x >= N || tmp.y < 0 || tmp.y >= M) break;

이렇게 해서 넣어봤습니다

seonjoo2030   2년 전

아, 저게 아니라 for문 안에 이렇게 넣었습니다 ㅎㅎ


if (tmp.x < 0 || tmp.x >= N || tmp.y < 0 || tmp.y >= M) continue;

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