그냥 게임개발자

연결된 컴포넌트란 이거다 오 뭔가 그거같다. 아 피곤해서 이해좀 해주세요:) 그래서 연결된 컴포넌트는 연결된 하나의 덩어리라고 보시면 됩니다. 이렇게 연결된 컴포넌트에 속한 "모든 정점을 연결하는 경로가 있다!" 라는 특징을 가져요. 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번부터 방문안한 노드를 찾고 해당 노드부터 방문..