BFS

[알고리즘] DFS & BFS - 깊이우선 탐색과 너비우선 탐색

2023.03.06

:: 그래프 탐색 :: dfs와 bfs알고리즘은 대표적인 그래프 탐색 알고리즘이다. 해당 알고리즘은 코딩 테스트에 높은 비율로 출제되기 때문에 꼭 학습해야하는 알고리즘 중 하나이다. DFS(Depth First Search) - 깊이 우선 탐색 깊이 우선 탐색은 재귀를 통하여, 시작 노드부터 그래프의 제일 안쪽 노드까지 깊숙히 방문하며 그래프를 탐색하는 알고리즘이다. 다음 그림 예시를 통해 탐색과정에 대하여 알아보자 1번에서 시작하는 다음과 같은 그래프가 있다고 하자. 그래프는 수가 작은 순으로 탐색하도록 초기 값이 주어진다. 그럼 DFS로 탐색하게 되었을 때, 어떻게 탐색하게 될까? 노드에 방문할 때마다 해당 노드에 방문 처리를 하며, 1과 연결되어 있는 노드2와 노드3 중에 수가 작은 순으로 탐색을 ..

코딩테스트/백준

[백준] 1926번 - 그림 (파이썬)

2023.01.24

" 백준 1926번 그림 문제 파이썬 " " 💡 문제 해결 아이디어 " 1926번 그림 문제는 0과 1로 이루어진 그래프에서 상하좌우가 1로 연결된 그림을 찾아 그 갯수와 그 그림들 중 가장 넓은 넓이를 출력하는 문제이다. for문을 통해 그래프의 0,0 ~ n-1,m-1 까지 전체를 탐색하며 값이 1인 지점을 찾을 때마다 cnt +=1 을 한다. 그리고 값이 1인 지점의 x,y좌표를 bfs로 탐색하여 그 지점에 연결되어 있는 1들을 모두 0으로 변경하며 1이 0으로 변경되는 횟수를 area(넓이) 변수에 +1 해주고 더이상 연결된 1이 없다면 area 변수의 값을 return한다. return받은 area변수는 이전에 서칭한 가장 넓었던 그림의 면적(maxArea 변수)와 비교하여 더 큰 값을 다시 m..

[알고리즘] DFS & BFS - 깊이우선 탐색과 너비우선 탐색

[백준] 1926번 - 그림 (파이썬)

티스토리툴바