dfs2 알고리즘 | 음료수 얼리기 문제 (BFS와 DFS로 각각 풀어보기) 더보기 N by M 크기의 얼음 틀이 있습니다. 구멍이 뚫려 있는 부분은 0 칸막이가 존재하는 부분은 1입니다. 구멍이 뚫려있는 부분끼리 상, 하, 좌, 우로 붙어있는 경우 서로 연결되어 있는 것으로 판단합니다. 이러한 경우에서 얼음 틀의 모양이 그래프로 주어진다면 생성되는 아이스크림의 갯수는 몇 개일까요? graph_45 = [ [0,0,1,1,0], [0,0,0,1,1], [1,1,1,1,1], [0,0,0,0,0] ] n = 4 m = 5 첫째 / BFS 방식으로 풀기 출발점에서부터 점진적으로 진행해가는 방식으로 접근하는 경우 BFS를 고려해볼 수 있습니다. 일단 BFS니까 아묻따 디큐부터 임포트해주고 시작합니다. from collections import deque 1. 함수를 작성합니다. 입력받.. 2024. 4. 2. 알고리즘 | 탐색 기본, DFS / BFS 엣지를 따라 모든 노드를 방문하는 것을 그래프 탐색이라고 한다. 대표적으로 DFS(깊이 우선 탐색), BFS(너비 우선 탐색)이 있다. Depth First Search (깊이 우선 탐색) 깊이 우선 탐색은 기본적으로 Stack이다. (Last In First Out) 오른쪽 왼쪽 상관은 없음 예제 graph_list = [ [], # 0번 도시(없음) [2, 3, 8], # 1번 도시 [1, 7], # 2번 도시 [1, 4, 5], # 3번 도시 [3, 5], # 4번 도시 [3, 4], # 5번 도시 [7], # 6번 도시 [2, 6, 8], # 7번 도시 [1, 7] # 8번 도시 ] 1번 도시 방문 To do : [2, 3, 8] 2번 도시 방문 To do : [1, 7] -> 1번은 됐고 7번 .. 2024. 4. 1. 이전 1 다음
