본문 바로가기

dfs

[Python] DFS(재귀/반복), BFS 구현 본 내용은 를 참고했습니다. 재귀 DFS def recursive_dfs(v, discovered = []): discovered.append(v) for w in graph[v]: if w not in discovered: discovered = recursive_dfs(w, discovered) return discovered 스택을 이용한 반복 DFS def iterative_dfs(start_v): discoverd = [] stack = [start_v] while stack: v = stack.pop() if v not in discovered: for w in graph[v]: stack.append(w) return discovered 큐를 이용한 반복 BFS def iterative_bs.. 더보기
[BOJ] 2667번 - 단지번호 붙이기 단지번호 붙이기 문제 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오. 입력 첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다. 출력 첫 번째 줄에는 총 단지수를 출력하.. 더보기
[알고리즘] 그래프, DFS, BFS 간단 정리 본 포스팅은 백준 알고리즘 강의 기초2 자료를 바탕으로 작성하였습니다. 그래프 정점(Node, Vertex) 간선(Edge) : 정점간의 관계 G = (V, E) Path Cycle Directed Graph Undirected Graph Multiple Edge Loop : 간선의 양 끝점이 같은 경우 Weight Degree : 정점과 연결되어 있는 간선의 개수 방향 그래프의 경우 In-degree(들어오는), Out-degree(나가는)로 나누어서 차수를 계산 그래프의 표현 정점 : {1,2,3,4,5,6} 간선 : {(1,2), (1,5), (2,5), (2,3), (3,4), (2,4), (4,5), (4,6)} 인접 행렬(Adjacency-matrix) 이차원 배열 이용 A[i][j] = 1 .. 더보기

티스토리툴바