그래프

*이 글은 2022년 1월~2월 노션으로 진행한 스터디를 옮긴 글입니다.

220129 그래프 내용정리

• 용어정리
  • G=(V,E)
  • 무방향 그래프 (A, B)
  • 방향 그래프 <A,B> <B,A>
  • 가중 그래프(도시 간 최단 경로, 최단 시간 등)

• 부분 그래프

  ---

• 인접: 두 정점을 연결하는 간선이 존재하는 경우 인접함.

• 차수: 무방향 그래프는 하나의 정점에 연결된 간선의 개수, 방향 그래프는 진입차수와 진출차수

• 경로: 그래프에서 간선을 따라 갈 수 있는 길을 순서대로 나열함.

• 단순경로: 경로 중 반복되는 간선이 없는 경로

• 사이클: 단순경로의 시작 정점과 종료 정점이 동일한 경로

• 연결 그래프: 서로 다른 모든 쌍의 정점들 사이에 경로가 있는 그래프. (#완전 연결 그래프)

• DAG: 사이클 갖지 않는 방향 그래프

  
  

• 트리도 그래프의 일종임.

• 구현

  • 인접행렬
    • n x n 정방행렬 사용함
    • 인접 여부를 값으로 저장함.
    • 무방향 그래프의 인접 행렬은 대칭성을 지님→대칭성 이용하여 일부 값만 저장함
      
      
  • 인접리스트
    • 각 정점에 인접한 정점들을 연결리스트로 표현함
    • 각 정점별 헤드 노드 사용함. 각 정점의 차수만큼 노드를 차례로 연결
      

• 문제

  그래프 순회/탐색

  • 하나의 정점에서 시작해서 그래프에 있는 모든 정점을 한번씩 방문or특정 값을 탐색하는 연산.

    

  • DFS(depth first search-stack)

    • 깊이우선탐색

    • 스택 선호

      void dfs(int v){
          for(int i=0;i<path[v].size();++i){
              if(!visit[path[v][i]]){
                  visit[path[v][i]]=1;
                  printf("%d ",path[v][i]);
                  dfs(path[v][i]);
              }
          }
      }

  • BFS(breadth first search-queue)
    - 너비우선탐색
    - 큐 선호

    ```cpp
    void bfs(int v){
        for(int i=0;i<path[v].size();++i){
            if(!visit[path[v][i]]){
                q.push(path[v][i]);
                visit[path[v][i]]=1;
            }
        }
        while(!q.empty()){
            int t = q.front();
            q.pop();
            printf("%d ",t);
            bfs(t);
        }
    }
    ```

    #include<bits/stdc++.h>
    using namespace std;
    int n,m,v;
    bool visit[1005];
    vector<int> path[1005];
    queue<int> q;
     
    void dfs(int v){
        for(int i=0;i<path[v].size();++i){
            if(!visit[path[v][i]]){
                visit[path[v][i]]=1;
                printf("%d ",path[v][i]);
                dfs(path[v][i]);
            }
        }
    }
    void bfs(int v){
        for(int i=0;i<path[v].size();++i){
            if(!visit[path[v][i]]){
                q.push(path[v][i]);
                visit[path[v][i]]=1;
            }
        }
        while(!q.empty()){
            int t = q.front();
            q.pop();
            printf("%d ",t);
            bfs(t);
        }
    }
    int main(){
        int x,y;
        scanf("%d%d%d",&n,&m,&v);
        for(int i=0;i<m;++i){
            scanf("%d%d",&x,&y);
            path[x].push_back(y);
            path[y].push_back(x);
        }
        for(int i=0;i<n;++i)
            sort(path[i].begin(),path[i].end());
        visit[v]=1;
        printf("%d ",v);
        dfs(v);
        puts("");
        memset(visit,0,sizeof(visit));
        visit[v]=1;
        printf("%d ",v);
        bfs(v);
    }

---

220130 백준20364 부동산 다툼

• 알고리즘구상
  • 배열로 트리를 구상하고 이미 점유된 노드는 bool타입 배열로 true처리함.
  • 어떤 수가 들어왔을 때 그 부모노드가 true인지 확인하고 true이면 탐색 종료 false면 부모노드의 부모노드가 true인지 확인함
  • 작성한 뒤의 문제점
  • 부모노드가 true일 경우 부모노드의 조상노드가 true여서 그 노드를 출력해야 하는데 그냥 부모노드만 출력해버림
  • 자료의 크기가 주어진 조건보다 작아서 런타임오류 발생
• 1차 구현(런타임에러) →배열 사이즈가 너무 작음

  #include<iostream>
  using namespace std;
  bool sola[100] = { false };
  int direct(int a) {
  	//노드가 홀수일때
  	if (a % 2 == 1) {
  		//부모노드가 점유된 노드라면
  		if (sola[a / 2 - 1] == true) {
  			//a는 점유할수 없는 노드임
  			return a/2-1;
  		}
  		//부모노드가 점유되지 않은 노드라면
  		else {
  				sola[a] = true;
  				return 0;
  		}
  	}
  	//노드가 짝수일때
  	else {
  		if (sola[a / 2] == true) {
  			return a / 2;
  		}
  		else {
  			sola[a] = true;
  			return 0;
  		}
  	}
  }
  int main() {
  	int tree, input, bbi;
  	int answer[100] = {};
  	cin >> tree >> input;
  	for (int i = 0; i < input; i++) {
  		cin >> bbi;
  		answer[i + 1] = direct(bbi);
  	}
  	for (int i = 1; i <= input; i++) {
  		cout << answer[i] << endl;
  	}
  }

  • vs에선 해당코드 실행 시 정상작동하지만 배열의 크기가 커지면 제대로 작동하지 않음.
  • 해결책을 찾지 못해 다른 사람의 코드를 참고해 스택 도입하여 코드 재작성
• 2차 구현(스택 활용)(시간초과)

  #include<iostream>
  #include<stack>
  using namespace std;
  
  bool node[1048577];
  int main() {
  	int x, a;
  	cin >> x>> a;
  	
  	for (int i = 0; i < a; i++) {
  		int input;
  		cin >> input;
  		bool judge = false;
  		int temp = input;
  		stack<int>answer;
  		//스택 넣기
  		while (temp!=0) {
  			answer.push(temp);
  			temp /= 2;
  		}
  		//스택 빼면서 점유된 땅 있는지 확인
  		while (!answer.empty()) {
  			temp = answer.top();
  			if (node[temp] == true) {
  				cout << temp << endl;
  				judge = true;
  				break;
  			}
  			else {
  				answer.pop();
  			}
  		}
  		if(judge==false){
  			node[input] = true;
  			cout << 0 << endl;
  		}
  	}
  	return 0;
  }