BFS visited 사용시점

visited 배열을 사용하는 것과 최소값 갱신 로직을 사용하는 것은 서로 다른 목적을 가지고 있습니다. 아래에서 각각의 차이점을 설명하겠습니다.

1. visited 배열 사용:
   • 목적: 중복 방문을 방지하여 불필요한 계산을 줄이고, 무한 루프를 방지합니다.
   • 활용: 그래프나 맵에서 특정 노드나 위치를 방문했는지 여부를 체크합니다.
   • 예시: 미로 찾기에서 특정 위치를 이미 방문했는지 확인하고, 이미 방문한 곳은 다시 방문하지 않도록 합니다.
   • 효과: 중복 방문을 방지하여 탐색 속도를 향상시키며, 무한 루프를 방지하여 프로그램이 정상적으로 종료될 수 있습니다.
2. 최소값 갱신 로직 사용:
   • 목적: 최단 경로나 최소 비용을 찾을 때, 현재까지의 최소값을 갱신하며 탐색합니다.
   • 활용: BFS나 다익스트라 알고리즘에서 최소값을 갱신하면서 특정 목적지까지의 최단 경로를 찾습니다.
   • 예시: 길찾기 문제에서 최소 비용 경로를 찾을 때, 현재까지의 최소 비용을 갱신하면서 탐색합니다.
   • 효과: 최단 경로나 최소 비용을 찾을 때 정확한 결과를 얻을 수 있습니다.

일반적으로, 최소값 갱신 로직을 사용하는 것은 최단 경로를 찾거나 최소 비용을 계산할 때 주로 활용되며, visited 배열은 그래프나 맵에서 특정 노드를 중복 방문하지 않기 위해 사용됩니다. 

 

visited 배열을 사용할지 말지 헷갈리는 경우가 많습니다.

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD

SW Expert Academy

다음 문제와 같이, 보급로를 확보하기위한 최소 비용 경로를 찾을때는 visited를 선언해버리면 최소 비용 경로로 돌아가지 못하는 문제가 발생하기 때문에 visited를 사용하면 안됩니다.

 

 

하지만, 단순히 최단경로를 찾고싶을때는 visited를 사용해서 사이클을 방지한다던지, 처음 도착한 것이 중요하면 visited를 사용하는 것이 좋겠습니다.