SY DevLog

그래프 탐색에는 두 가지 방법이 있다. DFS(Depth First Search) BFS(Breadth First Search) 이번에는 BFS에 대해서 다뤄볼 것이다. DFS(Depth First Search) - 깊이 우선 탐색 그래프 탐색에는 두 가지 방법이 있다. DFS(Depth First Search) BFS(Breadth First Search) DFS 는 이름 그대로 깊이를 우선시 하여 탐색하는 방법이다. '한 우물만 판다' 라는 느낌처럼 한 길만 계속 깊이.. lotuslee.tistory.com BFS는 너비 우선 탐색으로 특정 노드와 연결된 모든 노드들을 우선적으로 탐색한 뒤, 그 중에 하나를 선택하여 또 다시 그와 연결된 모든 노드들을 탐색하는 방식으로 진행된다. 하나의 경로만을 깊..

그래프 탐색에는 두 가지 방법이 있다. DFS(Depth First Search) BFS(Breadth First Search) DFS 는 이름 그대로 깊이를 우선시 하여 탐색하는 방법이다. '한 우물만 판다' 라는 느낌처럼 한 길만 계속 깊이 파고드는 방식이다. 반면에 BFS 는 넓이를 우선시한다. 특정 노드와 연결된 모든 노드를 한번씩 거친 다음에 다음 노드로 이동하는 방식이다. 예를 들어, 다음과 같은 그래프가 있고 1번부터 탐색을 시작한다고 할 때 왼쪽과 같은 탐색 방법을 DFS, 오른쪽과 같은 탐색 방법을 BFS라고 할 수 있다. DFS : 1 -> 2 -> 4 -> 7 -> 6 -> 3 -> 5 BFS : 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 위의 DFS 방식에서 처음에 꼭..

그래프 관련하여 문제를 풀다보면(가령 DFS, BFS 문제와 같은) 그래프에서 노드간의 연결관계를 저장해야 하는 경우가 있다. 이럴 때 그래프의 연결관계를 표현하는 방법이 대표적으로 두 가지가 있다. 인접 행렬 인접 리스트 인접 행렬 그래프에 N개의 노드가 있으면, N x N 이차원 행렬을 만들어서 노드와 노드 사이의 간선 가중치를 담는 방식이다. 그래프가 무방향 그래프이고, i노드와 j노드가 연결되어 있으며 둘 사이의 간선의 가중치가 w인 경우, graph[i][j] = graph[j][i] = w 로 나타낼 수 있다. 만약 그래프에 가중치가 주어지지 않은 경우에는 두 노드가 연결되어 있으면 1, 연결되어 있지 않으면 0 으로 나타내어 0과 1로만으로 연결관계를 표현할 수 있다. 혹은 boolean형으..