저번에는 DFS를 다루었으니, 이젠 그래프 탐색 알고리즘 중 BFS를 다뤄봅시다 ! BFS (Breadth First Search)너비우선탐색, 특정 노드부터 시작해 다음 깊이의 노드로 이동하기 전에 현재 깊이의 모든 정점을 탐색합니다.이때, 방문한 정점은 다시 방문하지 않으며 보통 "같은" 가중치를 가진 그래프에서 최단거리 알고리즘으로 쓰입니다. pseudocode (수도코드 - 의사코드) - 2가지 버전이 존재합니다. ver1. 방문처리만 하는 BFS 코드BFS(G, u) u.visited = true q.push(u); while(q.size()) u = q.front() q.pop() for each v ∈ G.Adj[u] ..

그동안 3개의 포스팅을 통해 그래프를 다뤘습니다. 이제 그래프를 탐색하는 알고리즘 중 가장 유명한 DFS, BFS 중 DFS 먼저 다뤄봅시다.DFS (Depth First Search)깊이우선탐색, 특정 노드부터 시작해 인접한 노드들을 재귀적으로 방문합니다.이때, 방문한 정점은 다시 방문하지 않으며 각 분기마다 가능한 가장 멀리 있는 노드까지 탐색합니다.(분기란? : 2개 이상으로 정점이 쪼개지는 지점)  pseudocode (수도코드 - 의사코드)DFS(u, adj) u.visited = true for each v ∈ adj[u] if v.visited == false DFS(v, adj) 시작 정점 u부터 방문하여, u와 인접한 모든 노드들에 대해 방문하지..

종종 알고리즘 문제에서 그래프가 맵으로 주어지는 경우가 존재합니다.이런 형태로요! 이렇게 주어진 맵은 그 맵을 기준으로 탐색을 이어가야만 합니다.굳이 인접리스트나, 인접행렬로 바꾸려고 하면 머리만 아파요! 아, 그리고 위에서 주어진 표는 인접 행렬이 아니라 맵임을 명심하세요. 위의 맵에서 1은 갈 수 있는 지역, 0은 갈 수 없는 지역이라고 합시다. (육지 == 1 && 바다 == 0 혹은 길 == 1 && 벽 == 0 등등의 예시)그럼 이걸 그래프로 표현하면 아래와 같은 모습이 됩니다.   4방향 탐색과 방향 벡터4방향 탐색은 위, 아래, 오른쪽, 왼쪽을 탐색하는 것을 의미합니다. 그리고 보통 (y,x) 로 표현하곤 합니다. → 행, 열을 표현하기에 더욱 적합하기 때문아래의 그림에서, dy, dx는 방..

저번 포스트에서는 그래프에 대한 전반적인 개념을 살펴봤습니다.그럼 그래프는 컴퓨터로 어떻게 구현할 수 있을까요? 그래프에서 가장 중요한 2가지 개념을 뽑는다면 정점과 간선이었습니다.그럼 컴퓨터로 구현하려면, 정점과 간선의 관계를 나타내는 자료구조가 필요하겠네요!바로 인접 행렬과 인접 리스트입니다. 일단 예시를 하나 들어보도록 하겠습니다.  인접 행렬 ( adjacency matrix )위의 예시는 아래의 표로 나타낼 수 있습니다.  i / j012300111110102110031000 형식이 대략 이해가 가시나요? 2차원 배열의 형식(행렬)로 표현을 했는데,a[i][j] 는 i번 노드에서 j번 노드로 향하는 경로(간선)이 있는지를 알려줍니다. 예를 들어, a[0][1] == 1 이므로 0번에서 1번으로 ..

그래프이론은 오일러경로, SCC, 단절점 등 어려운 개념과 넓은 범위를 다루는 이론이지만,해당 포스트에서는 그래프의 기초에 대해 다뤄보도록 하겠습니다. 우선 그래프의 기초 요소에 대해 알아봅시다.Graph, Vertex, Edge, WeightVertex (정점) : 하나의 지점Edge (간선) : 정점을 잇는 선 - 즉 경로Weight (가중치) : 간선에 부여된 값 (일종의 비용)정점과 간선의 대표적 예시는 지하철 노선도를 들 수 있겠네요. 지하철 역 = Vertex,역 사이의 경로 = Edge,경로를 지날 때 걸리는 시간(or 경로 교통비) = Weight 간선은 단방향 간선, 양방향 간선으로 분류되기도 합니다.또한 그래프 자체는 Undirected Graph 와 Directed Graph 로 분리..