[BFS/DFS] C 프로그래머스 부대복귀 풀이

문제

• 부대복귀

풀이 과정

• 주어진 roads에 따라 양방향 간선을 이어준 후 부대원들의 위치마다 bfs돌려서 리턴하려고 했으나 메모리가 터져서 개같이 실패한 문제

solution0.o: In function enqueue':
solution0.c:(.text+0x3): relocation truncated to fit: R_X86_64_PC32 against symbol rear' defined in COMMON section in solution0.o
solution0.c:(.text+0xa): relocation truncated to fit: R_X86_64_32S against symbol que' defined in COMMON section in solution0.o
solution0.c:(.text+0x11): relocation truncated to fit: R_X86_64_32S against symbol que' defined in COMMON section in solution0.o
solution0.c:(.text+0x1a): relocation truncated to fit: R_X86_64_PC32 against symbol rear' defined in COMMON section in solution0.o
solution0.o: In function dequeue':
solution0.c:(.text+0x23): relocation truncated to fit: R_X86_64_PC32 against symbol front' defined in COMMON section in solution0.o
solution0.c:(.text+0x2c): relocation truncated to fit: R_X86_64_PC32 against symbol front' defined in COMMON section in solution0.o
solution0.c:(.text+0x34): relocation truncated to fit: R_X86_64_32S against symbol que' defined in COMMON section in solution0.o
solution0.o: In function bfs':
solution0.c:(.text+0x4f): relocation truncated to fit: R_X86_64_PC32 against symbol front' defined in COMMON section in solution0.o
solution0.c:(.text+0x6d): relocation truncated to fit: R_X86_64_PC32 against symbol que' defined in COMMON section in solution0.o
solution0.c:(.text+0x73): relocation truncated to fit: R_X86_64_PC32 against symbol que' defined in COMMON section in solution0.o
solution0.c:(.text+0x7d): additional relocation overflows omitted from the output
clang: error: linker command failed with exit code 1 (use -v to see invocation)

• 내가 만난 오류... 전역변수가 너무 커서 박살났다
  • 하긴 n크기가 100000 이라서
    • 필요한 메모리는 100,000 x 100,000 x 4byte = 40gb ㄷㄷ

틀린 코드

• 틀린 이유: 최적화 실패
  • 메모리 터짐
  • bfs 호출이 많으며 bfs 중복탐색 함

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

#define MAX 100001

typedef struct Que {
    int x;
    int dist;
} Q;

int road[MAX];
int visit[MAX];
int flag[MAX][MAX];
int cnt[MAX];

Q que[MAX];
int front;
int rear;

void enqueue(int x, int dist) {
    que[rear].x = x;
    que[rear].dist = dist;
    rear++;
}

Q dequeue() {
    return que[front++];
}

int bfs(int start, int destination, int n) {
    front = rear = 0;
    memset(visit, 0, sizeof(visit));
    enqueue(start, 0);
    visit[start] = 1;
    
    while (front < rear) {
        Q cur = dequeue();
        
        if (cur.x == destination) return cur.dist;
        
        for (int i=0; i<cnt[cur.x]; i++) {
            int nx = flag[cur.x][i];
            if (visit[nx] == 0) {
                visit[nx] = 1;
                enqueue(nx, cur.dist+1);
            }
        }
    }
    return -1;
}

int* solution(int n, int** roads, size_t roads_rows, size_t roads_cols, int sources[], size_t sources_len, int destination) {
    int* answer = (int*)malloc(sources_len * sizeof(int));
    
    for (int i=1; i<=n; i++) {
        road[i] = i;
    }
    
    for (int i=0; i<roads_rows; i++) {
        int a = roads[i][0];
        int b = roads[i][1];
        
        flag[a][cnt[a]++] = b;
        flag[b][cnt[b]++] = a;
    }
    
    for (int i=0; i<sources_len; i++) {
        answer[i] = bfs(sources[i], destination, n);
    }
    
    return answer;
}

개선 코드

• 개선 이유:
  1. 메모리 최적화
     • 기존 코드의 2차원 배열(flag[MAX][MAX])은 노드 수와 간선 수가 큰 입력에서 메모리 초과를 유발하므로 이를 인접 리스트(head, edges, next_edge)로 변환하여 메모리 사용량을 줄임
  2. 시간 최적화
     • 기존 코드에서는 각 source마다 BFS를 호출하여 동일한 경로를 반복 탐색하므로 목적지에서 단일 BFS를 수행하여 모든 노드의 최단 거리를 계산함으로써 시간 복잡도를 (O(n + m))으로 감소.
  3. 코드 유지보수성 향상
     • add_edge 함수를 사용해 그래프 초기화를 간소화하여 코드의 반복과 오류 가능성을 줄임

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_NODES 100001
#define MAX_EDGES 500001

typedef struct {
    int node;
    int dist;
} Queue;

int head[MAX_NODES];       // 각 노드의 간선 시작 인덱스
int edges[MAX_EDGES * 2];  // 간선 정보
int next_edge[MAX_EDGES * 2]; // 다음 간선 인덱스
int dist[MAX_NODES];       // 목적지까지의 최단 거리
Queue que[MAX_NODES];      // BFS를 위한 큐
int front, rear;           // 큐 포인터

void add_edge(int u, int v, int* edge_idx) {
    edges[*edge_idx] = v;
    next_edge[*edge_idx] = head[u];
    head[u] = (*edge_idx)++;
}

void bfs(int destination) {
    front = rear = 0;
    memset(dist, -1, sizeof(dist)); // 최단 거리 초기화
    que[rear++] = (Queue){destination, 0}; // 목적지에서 BFS 시작
    dist[destination] = 0;

    while (front < rear) {
        Queue cur = que[front++];
        for (int i = head[cur.node]; i != -1; i = next_edge[i]) {
            int next = edges[i];
            if (dist[next] == -1) { // 아직 방문하지 않은 노드
                dist[next] = cur.dist + 1;
                que[rear++] = (Queue){next, cur.dist + 1};
            }
        }
    }
}

int* solution(int n, int** roads, size_t roads_rows, size_t roads_cols, int sources[], size_t sources_len, int destination) {
    int* answer = (int*)malloc(sources_len * sizeof(int));
    memset(head, -1, sizeof(head)); // 초기화

    int edge_idx = 0;
    for (int i = 0; i < roads_rows; i++) {
        int u = roads[i][0];
        int v = roads[i][1];
        add_edge(u, v, &edge_idx); // 양방향 연결
        add_edge(v, u, &edge_idx);
    }

    // 목적지에서 출발하는 BFS 실행
    bfs(destination);

    // 각 source에 대해 결과 저장
    for (int i = 0; i < sources_len; i++) {
        answer[i] = dist[sources[i]];
    }

    return answer;
}

인접리스트

• 인접리스트는 그래프를 저장하는 방법 중 하나로 연결된 노드들을 리스트 형태로 저장하는 방식을 말함

예제: 그래프 표현

그래프 입력
1 -- 2
|    |
4 -- 3

인접 행렬로 표현
1과 2가 연결, 1과 4가 연결 등 연결된 노드를 1로 표시
   1  2  3  4
1 [0, 1, 0, 1]
2 [1, 0, 1, 0]
3 [0, 1, 0, 1]
4 [1, 0, 1, 0]

인접 리스트로 표현
각 노드가 자신과 연결된 노드 목록을 저장
1: [2, 4]
2: [1, 3]
3: [2, 4]
4: [1, 3]