깊이우선 탐색과 별반 다르지않다.
하지만 알고리즘의 1%만 수정되어도 제대로 이해를 하지못한다면 완전 다르게 보일수도있다.
컴퓨터의 알고리즘이란 1%로인해 전체적이 해법과 결과물이 달라지기때문이다.
익히 말한바와 같이 깊이 우선탐색은 재귀의 진행시 계속해서 시작정점을 반환하는 탐색방법이다.
내가 쓴방법은 한번 갔던 곳은 플래그로 표시를 해두었기때문에 판정을통해 다시는 안가도록 해놓았다.
이런경우는 노드와 노드사이의 간선이 하나만 존재할때 가능한일이다.
간선이 2개이상일땐 플래그를 해놓는 방법은 유용하지않다. 직접 행렬상의 간선의 개수를 지우는 방식으로 하겠다.
또한 한붓그리기의 취지에 맞게 모든 간선을 한번에 다 지나가야하므로 판정을 간선을 다 통과했는지 해야하고 이러한 모든 방법의 수를 구하기위해선, 재귀의 회귀시 간선의 복구를 통해 모든 경우를 다 계산하도록한다.
재귀의 진행과 회귀를 합친다면 우리는 모든 경우의 수를 다 구할수 있기때문에 가능한 일이다.
양방양 단방양은 알고리즘은 다음만 주의하면된다.
노드사이의 양방향 이동이 가능한경우 간선을 지울경우 양방향을 다지우고,
단방양인경우는 단방양만 지우는 것의 차이점만 있다.
반응형