백준[24479] 알고리즘 수업 - 깊이 우선 탐색 1

DFS를 응용한 첫 문제인데.. 실전으로 처음 접하다 보니 너무 어렵다;;

 

재귀함수가 100,000번 이상 중첩되다 보면 메모리 오류가 나기도 하고 cout, cin을 사용하면 대량 데이터를 입력받다 보니 시간초과가 뜨기도 한다. 

여러 가지로 너무 힘든 문제다...

 

#include <bits/stdc++.h>

int dfsN, dfsM, dfsR;

bool* dfsResList;
vector<int> dfsList[100001];
int dfsRes24479[100001];
int cnt = 0;

void dfs24479(int v){
    
    if(dfsResList[v])
        return;
    
    dfsResList[v] = true;
    cnt++;
    dfsRes24479[v] = cnt;
    
    for(int i=0;i<(int)dfsList[v].size();i++){
        int next = dfsList[v][i];
        dfs24479(next);
    }
}

void DFS1(){
    scanf("%d%d%d",&dfsN,&dfsM,&dfsR);
    
    dfsResList = new bool[dfsN+1]{false};
    for(int i=1;i<=dfsM;i++){
        int in1,in2;
        scanf("%d%d",&in1,&in2);
        dfsList[in1].push_back(in2);
        dfsList[in2].push_back(in1);
    }

    for(int i=1;i<=dfsN;i++){
        sort(dfsList[i].begin(),dfsList[i].end());
    }
    
    dfs24479(dfsR);
    
    for(int i=1;i<=dfsN;i++)
        printf("%1d\n",dfsRes24479[i]);
    
}

 

해결 방법

핵심적인 부분만 설명하자면 dfs와 대부분 유사하지만 진입하는 순서를 기억하는 것과 오름차순으로 정렬하는 것이 핵심이다.

 

문제 자체의 난이도 보다 메모리 오류, 시간문제가 제일 어려웠다.

데이터가 크면 2차원배열은 사용하지말기...ㅠ( 벡터 사용해서 push 하세요..)