MXN = 1002 이여야 합니다. [시작점 1개] + [중간 지점 최대 1000개] + [끝점 1개] = 1002 입니다.
N = 1000일 때 끝 점의 번호는 1001이 되고 MXN = 1001 이면 visited[1001] = -23345367737 같은 이상한 값을 가지고 옵니다.
왜냐하면 정적 배열은 컴퓨터 메모리에서 visted의 주소 ~ visted의 주소 + MXN-1 까지만 메모리를 비워둡니다. 그러므로 visted[MXN]의 값은 쓰레기 값인 -23345367737 와 같은 이상한 값을 가지고 오게 됩니다.
이때 아래의 코드는 66번째 줄에서 visited[1001]의 값을 물어보긴 하지만 어차피 61번째 줄에서 node -> N+1 이 val 보다 작거나 같지 않기 때문에
if문 안에 들어가지 않아도 문제가 생기지 않습니다. 그리고 당연하게 visted[1001] != 0이기 때문에 영향이 없는 것이죠.
그리고 기가 막히게 node -> N+1 의 거리가 val 보다 작거나 같으면 true를 출력하면 되기 때문에 결국, visted[1001]의 값을 의미있게 사용하는 경우가 생기지 않기 때문에 무사히 통과가 됩니다.
반면에, 위의 bfs 코드는 visted[1001]을 의미있게 물어보는 경우가 생깁니다. 근데 당연히 visted[1001]에는 우리가 기대했던 값이 저장되지 않기 때문에 이상한 값을 반환하게 되고 이는 bfs함수가 false를 반환하게 만듭니다.
결국 저 코드에서 mxn 을 1002로만 바꿔주면 위의 bfs함수로도 무사히 통과하게 됩니다.
zeratul 2년 전
제가 이해 안 가는 부분은 통과한 코드의 bfs나 처음의 bfs나 같은 코드라 생각되거든요.
윗부분 bfs는 주위 인접 노드를 탐색 할 때 가지 치면서 가고 마지막에 목표 노드가 조건을 충족하는가 참 거짓을 반환하는 것이고
밑에 통과한 bfs는 노드를 하나 꺼냈을 때 그 노드가 목표 지점을 갈 수 있으면 더 탐색 할 필요 없이 참을 반환하고 그렇지 않다면 거짓을 반환하는 데
이 두 코드가 차이가 있나요? 있다면 무엇일까요? 반례가 있다면 어떤 게 있을까요?
전 윗부분 bfs 도 맞다고 생각하는데 중간에 자꾸 틀리다 나오니 힘드네요..
고수님들 잘 부탁드립니다.