1260 DFS BFS

벡터를 사용해 인접리스트를 해볼까 했지만

나중에 비교하거나 할때 인접행렬이 편할 것 같아서 인접행렬로 풀어보겠음

밑에는 C++ 2차원배열 동적할당 하는 방법

 

알고리즘보다 배열때문에 힘들ㅇㅓㅆ음

이지윤이 동적할당하는거 도와줘서 어찌어찌 함

#include <iostream>
#include <stack>
#include <string.h>
#include <queue>

using namespace std;
int **arr;
int *visit;
void dfs(int start, int size_arr_num, bool flag) {

	stack<int> st;

	visit = new int[size_arr_num];
	memset(visit, 0, sizeof(int)*(size_arr_num));

	st.push(start);
	visit[start] = 1;
	cout << start << " ";

	while (!st.empty()) {
		int peek = st.top();
		flag = false;
		for (int i = 1;i <= size_arr_num;i++) {
			if (arr[peek][i] == 1 && visit[i]==0) {  //방문하지 않은걸 들려야하니까
				st.push(i);
				cout << i << " ";
				flag = true;
				visit[i] = 1;
				break;
			}
		}
		if (!flag)
			st.pop();
	}

}
void bfs(int start, int size_arr_num) {
	queue<int> que;
	memset(visit, 0, sizeof(int)*(size_arr_num));
	
	que.push(start);
	visit[start] = 1;
	while (!que.empty()) {
		int peek = que.front(); //front쓰면 나오지는 않아서 peek 역할이고 우리는 poll을 해야하니까 pop
		que.pop();
		cout <<peek << " ";
		for (int i = 1;i <= size_arr_num;i++) {
			if (arr[peek][i] == 1 && visit[i] == 0) {
				que.push(i);
				visit[i] = 1;
			}
		}

	}

}
int main(void) {
	int node_num = 0;
	int line_num = 0;
	int start_num = 0;
	int v1, v2 = 0;
	bool flag_m = true;

	cin >> node_num >> line_num >> start_num;

	int node_num_s = node_num + 2;
	arr = new int*[node_num_s];          //2차원 배열 동적할당 방법 -1이게 첫부분
	for (int i = 0;i < (node_num + 2);i++) {
		arr[i] = new int[node_num_s];    //-2 이게 두번째 배열 부분
		memset(arr[i], 0, sizeof(int)*(node_num_s));
		//memset으로 초기화하는법
	}
	
	for (int i = 0;i < line_num;i++) {
		cin >> v1 >> v2;
		arr[v1][v2] = 1;
		arr[v2][v1] = 1;
	}
	dfs(start_num,node_num_s,flag_m); //배열은 0부터 시작하니까 넘겨줄땐 계산 편하게 할려고 -1해줌
	cout << endl;
	bfs(start_num, node_num_s);
	//동적할당 해제
	for (int i = 0;i < node_num + 1;i++) {
		delete[]arr[i];
	}
	delete[]visit;
	return 0;
	
}

런타임에러는 배열때문에 났던것 같다.

이 예제가 배열이 1부터 시작해서 그것때문에 배열 크기 설정하는게 중간에 잘못된것 같음

무튼 고쳐서 맞았다

행복ㅎ

+++추가 수정(달라진건 별로 없지만..다시 풀어봄)

#include <stdio.h>
#include <iostream>
#include<cstring>
#include<stack>
#include<queue>

using namespace std;
int **arr;
int *visit;
void dfs(int start_num, int size){
    stack<int> st;
    int top;
    bool flag=false;
    int st_size=0;
    visit=new int[size];
    memset(visit,0,sizeof(int)*size);
    
    visit[start_num]=1;
    st.push(start_num);
    cout<<start_num+1<<" ";
    
    while(!st.empty()){
        top=st.top();
        flag=false;
        for(int i=0;i<size-1;i++){
            if(arr[top][i]==1&&visit[i]==0){
                st.push(i);
                cout<<i+1<<" ";
                visit[i]=1;
                st_size++;
                flag=true;
                break;
            }
        }
        //밑에까지 가고 없으면 다시 돌아와서 그 노드에서 dfs를 시작해야 하니까
        if(!flag)
            st.pop();
        
    }
    
}
void bfs(int start, int size){
    queue<int> que;
    int front;
    memset(visit,0,sizeof(int)*size);
    que.push(start);
    visit[start]=1;
    
    while(!que.empty()){
        front=que.front();
        cout<<front+1<<" ";
        que.pop();
        for(int i=0;i<size-1;i++){
            if(visit[i]==0&&arr[front][i]==1){
                //que에 bfs탐색과정대로 노드가 들어간다.
                que.push(i);
                visit[i]=1;
            }
            
        }
    }
    
}
int main()
{
    int n;
    int m;
    int start_num;
    int arr_size;
    int v1,v2;
    
    cin>>n>>m>>start_num;
    arr_size=n+1;
    arr=new int*[arr_size];
    for(int i=0;i<n;i++){
        arr[i]=new int[arr_size];
        memset(arr[i],0,sizeof(int)*(n));
    }

    for(int i=0;i<m;i++){
        cin>>v1>>v2;
        arr[v1-1][v2-1]=1;
        arr[v2-1][v1-1]=1;
    }
    
    dfs(start_num-1,arr_size);
    cout<<endl;
    bfs(start_num-1,arr_size);

for(int i=0;i<arr_size;i++){
    delete[]arr[i];
}
    return 0;
}