안녕하세요. 방문 체크를 해주는 이유가 있을까요?

저는 몇 줄 위에서 방문 체크 안해주어도 몇 줄 아래에 있는 open 에서 걸러지는 것이 연산 시간에 있어 큰 차이가 없을 것이라고 판단해서 오히려 closed 를 두어 일일이 방문 기록 및 검사를 하는게 코드도 늘어나고 연산시간이나 메모리면에 있어 더 비효율적이진 않을까 하고 조심스레 생각을 했었습니다. (사실 이것도 별 차이 없겠지만요!)

근데 g + h 계산을 미처 생각하지 못했네요! 꼭 간단한 최단경로 + 1 계산이 아니라 복잡한 계산이 따라오는 최소 비용을 구하는 문제일 수도 있을텐데 그런 경우엔 방문 체크를 하면 미리 계산 전부터 스킵되기 때문에 이처럼 복잡한 계산을 피할 수 있게 되겠네요.. 또한 방문 체크를 따로 두어 역할을 분리하는게 논리성이나 가독성 면에서도 더 좋을 것 같단 생각이 드네요. 

답변 정말 감사드립니다. 속 시원히 해결 되었네요. 즐거운 주말 되세요!

아하~ 그 의미군요.
1을 넣지 않더라도 2에 의해 같이 체크가 되기 때문에
1은 생략해도 결과는 똑같지 않느냐!
이 질문을 주신 것으로 보입니다.

알고리즘 자체로 봤을 때 딱히 차이는 없습니다만.
그럼에도 1을 추가하는 것이 조금 더 낫다고 생각하는 이유는
우선 논리적 역할 구분 차원인데
1은 방문한 곳을 스킵, 2는 비용 계산 후 OpenList 확인하는 역할을 담당하고 있습니다.
추가적으로 1의 연산은 훨씬 더 가볍기 때문에
1에서 미리 걸러낼 수 있다면
공식에 따라 복잡해질 수 있는 g + h 계산을 할 필요가 없어집니다.
마지막으로 A* 구현에 따라, 데이터가 너무 많아질 경우에
closed, list를 2차 배열로 하는게 아니라 다른 자료구조 (Dictionary 등)로 관리하고
closed에 들어가는 순간 open에서 빼주는 경우도 더러 있는데,
그런 경우를 생각해서도 closed를 먼저 체크하는게 유리할 것 같습니다.

알고리즘 문제 풀이라면 사실 별다른 차이가 없을 것 같네요.

링크의 질문글과 제 질문이 동일한 케이스는 아닌 것 같습니다. 제 요점이 잘 전달되지 못한 것 같네요.

링크의 질문자님께서는 예약 된 정점은 이미 방문 되었을 것이라고 생각을 하셔서 이미 예약 진행하는 for 문 들어오기 전 과정에서 해주는  if (closed[node.Y, node.X]) continue; 를 통해 이미 continue 되었을 텐데 이 if (open[nextY, nextX] < g + h) continue; 검사를 왜 하는지에 대해 질문을 주셨습니다.

저는 이와는 정반대로 if (open[nextY, nextX] < g + h) continue; 을 통해 이미 방문 된 정점은 걸러질텐데  예약 for문 전에 하는 i f (closed[node.Y, node.X]) continue; 을 굳이 해줄 필요 없을 것 같아 문의 드린 질문이였습니다..! 즉, closed 자체가 필요가 없다고 판단이 되서 선생님께서는 왜 closed 를 두고 방문 체크를 하신 것인지, 제가 놓치는 것이 있는 것인지 싶어 드린 질문입니다ㅠㅠ

말씀해주신 것처럼 우선순위 큐는 이미 넣은 값을 수정할 수가 없기 때문에 동일한 좌표의 정점을 이미 큐에 넣어 예약한적이 있더라도 더 좋은 가중치합을 찾아낸 정점을 아예 별개의 인스턴스로서 또 큐에 넣습니다. 근데 우선순위 큐는 더 좋은 해를 가진 정점을 먼저 내뱉기 때문에 같은 정점이라도 가장 좋은 해를 가진 정점부터 빠져나오므로 이미 방문한 적이 있는지 if (closed[node.Y, node.X]) continue; 를 통해 체크하지 않아도 어차피 이미 방문한적이 있는 "좌표"라면 해당 노드 구조체 인스턴스는 동일한 좌표를 가져서 이미 빠져나간 구조체 인스턴스보다는 더 안좋은(더 큰) 해를 가지고 있을 것이 분명하므로 if (open[nextY, nextX] < g) continue; 를 통해 알아서 걸러진다고 생각이 됩니다.

해당 링크에서 선생님께서 예로 드신 그래프로 제가 문의드리고 싶은 것을 설명하자면

closed를 두지 않고, 방문체크를 하지 않는다고 가정했을 때

1) 0 방문, 우선순위큐에 2 (1),  1 (10) 를 넣어 예약, 우선순위 큐 상태는 [ 2 (1),  1 (10) ] 

2) 2 방문, 우선순위큐에 3 (1000) 을 넣어 예약. 0 (1) 은 if (open[0] < 1 + 1 ) continue;  을 통해 알아서 걸러지므로 예약되지 못함. open[0] 은 출발지라 이미 0 인 상태이기 때문. 우선순위 큐 상태는 [  1 (10), 3 (1000) ] 

3) 1 방문, 우선순위큐에 0 (10) 을 예약할 수 있는지 확인해보려는데 if (open[0] < 10 + 10 ) continue; 을 통해 알아서 걸러지므로 예약되지 못함.(즉, 0이 방문된 정점인지 아닌지 굳이 검사하지 않더라도 이 과정 하나만으로 알아서 걸러집니다.)  3 (10) 은  if (open[3] < 10 + 10 ) continue; 에 해당되지 않기때문에 예약 가능. open[3] 은 현재 1001 이기 때문. open[3]은 20 으로 업데이트 되고  우선순위 큐 상태는 [   3 (1000), 3(20) ] 이 됨. (큐에 해가 다른 동일한 두 정점 3 이 들어가있는 상태)

4) 3 방문 (3(20)) , 우선순위큐에 2 (1000)을 예약할 수 있는지 확인해보려는데 if (open[2] < 20 + 1000 ) continue; 을 통해 알아서 걸러지므로 예약되지 못함. open[2]는 1이기 때문. 우선순위큐에 1 (10)을 예약할 수 있는지 확인해보려는데 if (open[1] < 20 + 10 ) continue; 을 통해 알아서 걸러지므로 예약되지 못함. open[1]는 10이기 때문. 3 과 연결되어있는 1 과 2 둘 다 예약되지 못함. 우선순위 큐 상태는 [  3 (1000) ] 

5) 3 방문 (3(1000)), 어차피 앞서 3(20) 방문을 통해 2 와 1 은 3(1000) 에서 가는 것 보다는 더 짧은 경로로 업데이트가 되어 있는 상태이므로 어차피 3(1000)을 통한 2 와 1은 if (open[2] < 1000 + 1000 ) continue;  if (open[2] < 1000 + 10 ) continue; 에 걸려 예약되지 못함. 우선순위큐는 비게 되어 종료.

이처럼 방문체크를 굳이 해주지 않아도 if (open[nextY, nextX] < g) continue; 로 재방문된 정점은 어차피 더 크고 안좋은 해를 가진 것이기 떄문에 어차피 여기서 걸러지게 되어 있는 것을 확인할 수 있었습니다.

어차피 예약 후보 정점이 예약 말고 이미 '방문'한적이 있는 정점이라면 if (open[nextY, nextX] < g) continue; 에 걸릴게 뻔합니다. 그리고 큐에서 방금 빠져나온 이번 방문 정점 또한 이미 방문한적이 있는 정점이라면 그의 자식 정점들인 예약 후보들은  if (open[nextY, nextX] < g) continue; 에 전부 걸릴게 뻔하므로 재방문 정점이라도 그 자식 정점들은 아무것도 예약되지 못합니다. 결론적으로 정점들마다 일일이 방문 체크를 해줄 이유가 없다고 그렇게 이해를 하고 있습니다.

그래서 closed 방문체크를 강의에서는 다 해주셨는데 제가 생각하지 못했던, 꼭 해주신 이유가 있는지 싶어 문의 드리러 찾아온 것이였습니다.  😭

https://www.inflearn.com/questions/100852

위 질문과 동일한 케이스 같네요.
예약할 때 체크를 하긴 하지만,
점점 더 좋은 케이스를 뒤늦게 발견할 수도 있습니다.
그리고 우선순위 큐 특성상 이미 넣은 값을 빼는 것은 힘들기 때문에
뒤늦게 덜 좋은 케이스로 판별된 점들은 skip하고 있습니다.