알고리즘/DFS6 [DFS] 틀 모양의 아이스크림 찍어내기 문제 0과 1로된 2차원 배열 모양의 아이스크림 판이 있다. 0인 부분은 뚫려 있고 1인 부분은 뚫려있지 않은 아이스크림 판이다. 이 판을 아이스크림에 올리면 모양이 나오게된다 예를 들어서 ) 00001111 00111000 111000111 처럼 판이 생겼다면 두개의 아이스크림 탄생한다 아이스크림의 개수를 구하는 알고리즘을 만들라 해결 하나의 모양을 만들려면 0들이 이어져야 한다. 이어진 0들을 찾기 위해서는 0을 하나 발견했을 때 위/오/왼/아래 방향으로 탐색하여 0이 있는지 확인하며 꼬리에 꼬리를 물고 늘어져야 한다. 단, 모양이 여러개 나올 수 있기 때문에 우리는 모든 틀 하나하나를 다 봐야한다 그러기 위해서는 visited를 만들어서 이미 방문한 노드는 다시 방문하지 않고 넘어갈 수 있도록 조치.. 2021. 8. 19. Depth First Search 깊이 우선 탐색 알고리즘 어떤 노드에서 다른 연관있는 노드로 이동하고 이동해서 도착한 노드에서 그 노드와 연관된 노드로 이동하고 .... 꼬리 물기 식으로 어떠한 관계가 있는 노드로 끝까지 물고 늘어지는 탐색 알고리즘이라고 나는 이해했다. DFS 알고리즘이 이용하는 자료구조는 STACK stack의 용도는 되돌아가기 위해서이다. (돌아갈까바그래~) 깊이 탐색하기 위해서 낮은애들부터 정복할 건데 다 정복하면 다시 위로 올라와서 정복하지 않은 아이들을 정복해 나가야 한다. 2번 노드에서 DFS를 시작한다고 가정한다면 (여러개가 이어져 있다면 노드 번호가 가장 낮은 것부터 탐색 한다) 1번을 stack에 Push -> 3번을 stack에 Push -> 2번은 방문했으니 3번을 pop 하고 -> 되돌아와서 다시 1번이랑 연결되어 있는 .. 2021. 8. 18. 이전 1 2 다음
