init 2주차 과제 - 그래프

1. 2주차 주제 & 복습

2주차 주제 : 그래프

(복습 내용은 제가 다시 알게 된 중요 내용 위주로 작성하였습니다)

그래프의 정의

• 정점/노드(V)
• 간선(E) : 정점을 연결
• 그래프 G(V,E) : 정점 집합 V와 간선 집합 E로 구성된 그래프
• 경로 : 한 정점인 시작점에서 다른 정점인 도착점으로 가는 간선이 연속되게 연결된 것
• 순환 : 경로의 시작점과 도착점이 동일

그래프의 종류

• 방향/무방향
• 가중치/비가중치
  기준에 따라서 4가지로 구분 가능

그래프의 구현 방법

• 그래프

• 인접 행렬 표현

  • 인접정점을 행렬로 표현
    
    (사진 출처 : https://sarah950716.tistory.com/12)
    
  • 정점 i, j이 간선이 연결되어 있으면 a[i][j] = 1
    연결되어 있지 않으면 a[i][j] = 0
    
  • 무방향 그래프 : 대각선을 기준으로 대칭
  • 방향 그래프 : 대각선을 기준으로 대칭이 아닐 수 있음

• 인접 리스트 표현

  • 인접 정점을 연결리스트로 표현
    
    (사진 출처 : https://sarah950716.tistory.com/12)

    • 각 정점으로부터 연결된 정점들을 연결하는 연결리스트를 일일이 만드는 방식

  • n개의 연결리스트 adjList[n] (n : vertex의 수)

• 인접행렬 vs 인접리스트

  • 인접행렬

    • 장점 : 두 정점을 잇는 간선이 있는지를 한 번의 배열 접근만으로 확인 가능
    • 단점 : 2차원 배열을 사용하므로 실제 간선 개수와 상관 없이 항상 O(|V^2|) 크기의 공간을 사용한다

  • 인접리스트

    • 장점 : |V|개의 연결 리스트에 실제 간선 수만큼의 원소가 들어 있으므로, 전체 O(|V| + |E|)의 공간만을 사용한다.
      • 단점 : 두 정점을 잇는 간선이 있는지를 알기 위해 연결 리스트를 일일이 뒤져야 한다.

그래프의 탐색

• DFS (깊이 우선 탐색)

  • 장점 : 최선의 경우, 가장 빠른 알고리즘 (ex : 그래프에서 맨 왼쪽 라인에 있을 때)
  • 단점 :
    • 찾은 해가 최적이 아닐 가능성이 있음 (ex : 찾으려는 노드가 루트노드에서 가깝게 있는데, 왼쪽에 있지 않다는 이유로 왼쪽 노드 다 돌고 와서 찾게 되는 경우)
    • 최악의 경우 해에 도달하는데 가장 오랜 시간이 걸림 (ex : 그래프에서 맨 오른쪽 라인에 있을 때)

• BFS (너비 우선 탐색)

  • 장점 : 최적해 보장 (ex : 루트노드에서 가까운 경우부터 찾으므로)
  • 단점
    • 최소 실행시간보다는 오래 걸린다는 것이 거의 확실
      • 최악의 경우, 실행에 가장 긴 시간이 걸릴 수 있음

2. 과제 풀이

문제

백준 5567번 결혼식

• 문제
• 풀이

혼자 힘으로는 막혀버렸고.. 다른 분의 설명과 코드를 참고하면서 공부를 하면서 해결방법을 익혔다.

참고한 글 : https://scarlettb.tistory.com/95

해결 포인트

• 인접행렬로 구현한 후, 상근이와 가까운 친구(상근이 친구, 상근이 친구의 친구)까지만 초대하는 것이므로 BFS 방법을 생각해내야 한다.
• 친구관계이면 ++을 하는 방식의 친구 수를 세어나가는 것과 방문하는 친구 수를 세는 것은 같은 친구를 중복해서 셀 수 있기 때문에 조금 접근이 다르다. 이 코드의 풀이를 작성하신 분께서는 방문한 친구인지를 담는 배열을 생성함으로써 방문한 친구들의 목록을 따로 관리했다.
• 꼭 동적 할당 배열이 아니어도 괜찮다.
  원래 처음 생각으로는 동적 할당으로 배열을 만드려고 했는데... 친구 인접행렬, 방문한 친구 배열을 모두 동적 할당으로 만들었으나 메모리 초과가 떠버렸다. 이 코드의 풀이를 작성하신 분께서는 그냥 아예 배열 크기를 501로 잡음으로써 간단하게 해결하셨다. 꼭 동적 할당 배열이 아니어도 풀이에는 큰 지장이 없는 것 같다. 너무 어렵게 생각하지 말고 최대한 일단 쉽게 구현해보자!!

풀이

#include <iostream>
using namespace std;
//#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable:4996)

const int MAX = 501;
int num_ppl; // 동기 수
int num_list; // 리스트 수
int arr[MAX][MAX]; // 인접행렬
bool visited[MAX]; // 방문 여부
bool sFriend[MAX]; // 상근이와 친구 여부
int count_num = 0; // 초대할 친구 수

void count() {
	// 상근이의 친구
	for (int i = 2; i <= num_ppl; i++) {
		if (arr[1][i] == 1) {
			visited[i] = true; // 방문
			sFriend[i] = true; // 상근이와 친구
		}
	}

	// 상근이의 친구의 친구
	for (int i = 2; i <= num_ppl; i++) {
		if (sFriend[i]) { // 상근이의 친구인 경우
			for (int j = 1; j <= num_ppl; j++) {
				if (arr[i][j]) { // 친구의 친구인 경우
					visited[j] = true;
				}
			}
		}
	}

	// 초대 인원 계산
	for (int i = 2; i <= num_ppl; i++) {
		if (visited[i]) count_num++;
	}
}

int main() {
	scanf("%d", &num_ppl);  // 동기 수
	scanf("%d", &num_list); // 리스트 수
	
	while (num_list--) {
		int f1, f2;
		scanf("%d %d", &f1, &f2);
		//cin >> f1 >> f2;
		arr[f1][f2] = 1;
		arr[f2][f1] = 1;
	}

	count();
	printf("%d", count_num);
	

	return 0;
}

추가 내용

• scanf를 사용할 때,
  • 앞에 #pragma warning(disable:4996)를 쓰자.
  • 파일 맨 앞에 #define _CRT_SECURE_NO_WARNINGS를 쓰자.
    (아 맨 앞에 안 써서 계속 오류가 난 것이였다..... 이제 알았다... 계속 빌드 오류나길래 다른 곳이 문제인 줄 알고 조금 답답했는데 맨 앞에 안 쓴 게 문제였다.. 다음에는 맨 앞에 잘 쓰자!!)
  • 출처 : https://programmerjoon.tistory.com/4

• 동적 할당으로 2차원 배열 만들기

int** arr = new int*[row]; //선언하고자 하는 이차원 배열의 행의 수 만큼 동적 할당 
for(int i = 0; i < row; i++) //각각의 인덱스에 선언하고자 하는 배열의 크기만큼을 가르키게 함. 
	arr[i] = new int[col];

출처 : https://ya-ya.tistory.com/101

• 비주얼스튜디오에서 작업한 후 한글이 깨질 때
  • 유니코드로 인코딩해서 저장해야 함
  • 참고 : https://bornsoul.tistory.com/26

3. 백준 결과 화면