그냥 게임개발자

너비우선탐색이란 그래프를 탐색하는 알고리즘 어떠한 정점에서 시작해 다음 깊이의 정점으로 이동하기 전에 현재 깊이의 모든 정점을 탐색하여 방문한 정점은 다시 방문하지 않는 알고리즘 같은 가중치를 가진 그래프에서 최단거리 알고리즘으로 자주 쓰입니다. 여기서 가중치는 무엇일까요? 지금 여기서 보면 0에서 1을 가는데 가중치는 10이 듭니다. 1에서 5를가는데 가중치는 5입니다. 즉 이 가중치가 같아야만! 너비우선 탐색 알고리즘을 사용할 수 있습니다. 그래서 BFS로 탐색을 한다는 것은 레벨별로 탐색한다는 뜻입니다. 이렇게 1레벨 2레벨 순 1. 빨강의 레벨에 속하는 노드 검사 2. 주황의 레벨에 속하는 노드 검사 3. 노랑의 레벨에 속하는 노드 검사 4. 초록의 레벨에 속하는 노드 검사 이런식으로 검사하는 방..

이거는 좀 진지하게 적을 생각입니다. 이거 매우 중요하거든요 진짜 열심히 쓸거에요 이거 이쁘게 찬란하게 깊이 우선 탐색(DFS, Depth First Search) 깊이 우선 탐색 DFS라고도 불립니다. DFS는 그래프를 탐색할 때 쓰는 알고리즘인데요. 어떤 노드부터 시작해서 인접한 노드들을 재귀적으로 방문해서 방문한 정점은 다시 방문하지 않고 각 분기마다 가능한 가장 멀리 있는 노드까지 탐색하는 알고리즘입니다. 즉, 그래프를 탐색할 때 쓰는 알고리즘 중 하나입니다. 루트노드부터 시작해 왼쪽부터 제일 멀리있는 노드까지 순차적으로 검사한 다음 다시 올라와서 분기점에서 다시 내려와서 검사하는 알고리즘입니다. 각 분기점은 어디냐면 자식이 2개인 노드인 것들이 분기점이라고 합니다. 근데 DFS의 핵심은 방문한 ..

연결된 컴포넌트란 이거다 오 뭔가 그거같다. 아 피곤해서 이해좀 해주세요:) 그래서 연결된 컴포넌트는 연결된 하나의 덩어리라고 보시면 됩니다. 이렇게 연결된 컴포넌트에 속한 "모든 정점을 연결하는 경로가 있다!" 라는 특징을 가져요. 1과 2는 연결되어 있고 모든 정점은 1과 2밖에 없죠 그러면 연결된 컴포넌트입니다. 그래서 이는 연결된 컴포넌트의 개수는 3개이며 각 정점은 2개 3개 2개입니다. 그러면 이것을 각각 번호를 매겨봅시다. 이런식으로 번호를 부여한 알고리즘을 flood fill이라고합니다. 우리는 저번 포스팅에서 맵을 배웠었죠? 위 사진과 같은 맵이 있을 때 1은 갈 수 있는 곳 0은 갈수 없는 곳이라고 했을 때 연결된 컴포넌트의 개수는 몇개일까요? 이렇게 3개의 연결된 컴포넌트를 발견했습니..

N * M 크기의 배열로 표현되는 미로가 있습니다. 이럴 때 맵을 기준으로 탐색을 해야 합니다. 이걸 인접행렬로 생각하면 안됩니다. 맵은 맵입니다. 아 map이 아니고 행렬로 풀긴하는데 인접행렬 뭐 이런걸로 바꾸지 말라는 소리입니다. 보통 여기서 4가지방향을 탐색하라고 하는데 4가지 방향은 위, 아래, 오른쪽, 왼쪽이라고 칩시다. 그러면 Map에는 y와 x가 있을텐데요. y, x를 중심으로 상하 좌우 4가지 방향 탐색을 해봅시다. 만약 1, 1이 중심이라고 치면 이런식으로 상 하 좌 우의 값들을 알겠죠? 그래서 보통 이것들을 dy, dx라고 합니다. directionY, directionX해서 dy dx 그렇다면 여기서 시계방향으로 보았을 때 dy는 dy[-1, 0, 1, 0]이 될테구요. dx는 dx[..

졸리네요 항상 지하철 만석이니 피곤이 가시질 않네요. 뭐 어쨌든 인접행렬과 인접리스트 중 어느 것을 써야 할까요? 뭐 그냥 편한 거 쓰면 됩니다. 근데 차이는 한번 비교해보죠. 공간복잡도의 차이 인접 행렬 : O(V^2) 인접 리스트 : O(V + E) V는 Vertex(정점)이며 E는 Edge(간선)입니다. 행렬은 정점이 10개라면 10 * 10 배열이 생기는 것이며 리스트는 정점이 10개의 그 10개의 간선이 2개라면 12개의 리스트가 생깁니다. 시간복잡도의 차이 간선 한개 찾기 인접행렬 : O(1) 인접리스트 : O(V) for (int i = 0; i < V; ++i) { // 인접행렬 for (int j = 0; j < V; ++j) { if (arr[i][j]) { } } // 인접리스트 fo..

우리는 저번 포스팅에 인접행렬을 배웠습니다. 2차원 배열이죠 그렇다면 인접리스트는 무엇일까요? 연결리스트 여러개 묶은 것이 인접리스트입니다. 이러한 그래프가 있습니다. 그렇다면 이것을 인접리스트로 어떻게 표현할까요? 각 인덱스의 정점을 넣는겁니다. list0[1, 4] list1[0, 2, 3, 4] list2[1, 3] list3[1, 2, 4] list4[0, 1, 3] 이런식으로 말이죠. 그렇다면 진짜 코드를 짜보죠. #include #include using namespace std; const int VERTEX = 5; vector adj[VERTEX]; int main() { adj[0].push_back(1); adj[0].push_back(4); adj[1].push_back(0); ad..

회사 퇴근하고 작성하려니 몸이 스르르 녹네요. 그래도 해야죠 자 아무튼 우리는 인접행렬에 대한 개념을 조금 배워봤어요. 그렇다면 한 번 다시 해봅시다. 만약에 정점의 갯수가 10개인 그래프가 있습니다. 이를 인접행렬로 표현하면 어떻게 될까요? bool arr[10][10]; 가 되겠죠. 그러면 0번부터 9번까지 10개인 노드가 있습니다. 1 - 2 / 1 - 3 / 3 - 4라는 경로가 있습니다. 이를 인접행렬로 표현한다면 어떻게 될까요? bool arr[10][10]; arr[1][2] = 1; arr[2][1] = 1; arr[1][3] = 1; arr[3][1] = 1 arr[3][4] = 1; arr[4][3] = 1; 이렇게 되겠죠? 그럼 이어서 0번부터 방문안한 노드를 찾고 해당 노드부터 방문..

좋아요 우리는 아주 차근차근 열심히 공부하고 있어요. 코딩 잘하는 사람이 되는 그날까지 열심히해봅시다! 우리는 저번 포스팅에서 그래프와 트리 이진트리에 대해서 배웠었죠? 그렇다면 간선 정점 뭐 이런 개념을 알고 있는데, 이것을 컴퓨터에게 전달할 때 어떻게 전달을 해야 할까요? 그럴때 사용하는게 인접행렬, 인접리스트 이렇게 두가지가 있습니다. 인접이란 연결되어있다는 소리입니다. 오늘은 인접행렬을 공부할거에요! 인접 행렬 인접 행렬은 그래프에서 정점과 간선의 관계를 나타내며 bool 타입의 정사각형 행렬을 의미합니다. 정사각형 행렬의 각 요소가 0 또는 1이라는 값으로 가지는데, 0은 두 정점 사이의 경로가 없음을 의미합니다. 또한 1은 두 정점 사이의 경로가 있음을 의미하는 그런 행렬입니다. 그림을 보면서..