[Jungol] 정올 1912 미로탐색

출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1185&sca=30

 Input 

5 6

1 3

3 4

4 2

2 1

1 4

4 5

 

 Output 

1 2 4 3 5 

N이 작지 않은 숫자이기 때문에 인접행렬 보다는 인접리스트로 그래프 연결 정보를 표시합니다.

그래프 정보에 앞서 주어지는 Input Data 정렬되어 있지 않기 때문에 시간효율을 위해서는

mergeSort나 quickSort를 이용해서 정렬해야 합니다.

 

ex) 정렬 시 양방향 연결을 고려해서 연결정보를 표시한 후 정렬

       (2, 4)  (1, 3)가 주어질 때 → (1, 3) (2, 4) 주어진 것들만 정렬하는 것이 아닌

       → (1, 3) (2, 4) (3 1) (4 2) 양방향 정보를 배열에 저장하여 정렬합니다.

▶ 정렬시킨 정보를 통해서 인접리스트를 보다 빠르게 구성할 수 있습니다.

 

ex) 주어진 Input Data로 아래와 같은 인접리스트를 구합니다. (오름차순 정렬되도록 처리)

    [1]: 2 3 4

    [2]: 1 4

    [3]: 1 4

    [4]: 1 2 3 5

    [5]: 4

* 데이터를 정렬하지 않고, 인접리스트를 구현할 때, 오름차순 되도록 구현할 수 있지만

  연결리스트에서 위치를 탐색하는데 있어서 TLE가 발생합니다.

  (이에 대한 구현은 [제출 코드]에서 push()로 구현)

① Input Data를 양방향 그래프를 반영해서 sort

② 그래프 정보를 인접리스트로 구현

③ DFS 탐색하며 방문하지 않은 방을 방문

    (인접리스트에서는 작은 방 번호로 연결시켰기에 작은 방 순서로 방문)

---

#include <stdio.h>
 
const int INF = 2e9;
const int MAX_N = 100000 + 5;
const int MAX_M = 500000 * 2 + 5;
 
int N, M, x, y;
struct Node {
    int data;
    Node* next;
 
    Node* alloc(int data, Node* next) {
        this->data = data;
        this->next = next;
        return this;
    }
}buf[MAX_M], *head[MAX_N];
int bcnt, totalCnt = 1;
int visited[MAX_N];
 
struct Edge {
    int from, to;
}edge[MAX_M], trr[MAX_M];
int ecnt;
 
int comp(Edge A, Edge B) {
    if (A.from == B.from)
        return A.to >= B.to;
    else
        return A.from < B.from;
}
 
void mergeSort(int start, int end) {
    // 0. base condition
    if (start >= end)
        return;
 
    // 1. divide
    int mid = (start + end) / 2;
 
    // 2. conquer
    mergeSort(start, mid);
    mergeSort(mid + 1, end);
 
    // 3. merge
    int i = start, j = mid + 1, k = start;
    while (i <= mid && j <= end) {
        if (comp(edge[i], edge[j]))
            trr[k++] = edge[i++];
        else
            trr[k++] = edge[j++];
    }
    while (i <= mid) trr[k++] = edge[i++];
    while (j <= end) trr[k++] = edge[j++];
 
    // 4. copy
    for (i = start; i <= end; ++i) {
        edge[i] = trr[i];
    }
}
 
void push(int from, int to) {
    Node* p = head[from];
    if (!p) {
        head[from] = buf[bcnt++].alloc(to, head[from]);
        return;
    }
 
    if (p->data > to) {
        head[from] = buf[bcnt++].alloc(to, head[from]);
        return;
    }
 
    Node* last = NULL;
    for (; p; p = p->next) {
        if (to < p->data) {
            last->next = buf[bcnt++].alloc(to, p);
            return;
        }
        last = p;
    }
 
    last->next = buf[bcnt++].alloc(to, NULL);
}
 
bool dfs(int now) {
    if (totalCnt > N)
        return true;
 
    for (Node* p = head[now]; p; p = p->next) {
        int next = p->data;
        if (visited[next]) continue;
        visited[next] = 1;
        printf("%d ", next);
        totalCnt++;
        if (dfs(next)) return true;
    }
    return false;
}
 
void connect(int from, int to){
    head[from] = buf[bcnt++].alloc(to, head[from]);
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    scanf("%d %d", &N, &M);
    for (int i = 1; i <= M; ++i) {
        scanf("%d %d", &x, &y);
        edge[ecnt++] = { x, y };
        edge[ecnt++] = { y, x };
    }
 
    mergeSort(0, ecnt - 1);
 
    for (int i = 0; i < ecnt; ++i) {
        connect(edge[i].from, edge[i].to);
        // push(edge[i].from, edge[i].to);
    }
 
    visited[1] = 1;
    totalCnt++;
    printf("1 ");
    dfs(1);
}