'll Hacker

EVI$ION 겨울방학 코테스터디 3주차 과제 본문

Dev

EVI$ION 겨울방학 코테스터디 3주차 과제

씨이오가 되자 2025. 1. 18. 23:55
Contents
728x90

그래프란?

노드(Node)와 간선(Edge)으로 표현되며 이때 노드를 정점이라고도 말한다.

그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다.

또한, 두 노드가 간선으로 연결되어있다 = 두 노드는 인접하다

 

인접행렬(Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현하는 방식

연결리스트라는 자료구조를 이용해 구현하는데, C++이나 자바와 같은 프로그래밍 언어에서는 별도로 연결 리스트 기능을 위한 표준 라이브러리를 제공 

 

인접 리스트(Adjacency List) : 리스트로 그래프의 연결 관계를 표현하는 방식 

vector의 배열을 사용하면 편리함.

유향 그래프
무향 그래프

실제로 연결된 노드들에 대한 정보만 저장하기 때문에, 모든 벡터들의 원소의 개수의 합이 간선의 개수와 같음. 간선의 개수에 비례한다. 각 노드에 연결된 모든 노드들을 방문해야되는 경우, 인접 리스트로 연결 관계를 저장하는 것이 시간상 큰 이점을 가진다. 

 

인접 행렬은 모든 관계를 저장하므로 노드 개수가 많을수록 메모리가 불필요하게 낭비된다.

인접 리스트는 연결된 정보만 저장하기 때문에 메모리를 효율적으로 사용한다. 하지만 이런 속성때문에 인접행렬에 비해 특정한 두 노드가 연결되어있는지에 대한 정보를 얻는 속도가 느리다. 왜냐하면, 연결된 데이터를 하나씩 확인해야하기 때문이다.

 

[[(1, 7)], [(2, 5)], [(0,7)], [(0, 5)]]

위의 예를 봤을때, 노드1과 노드7이 연결되어있는 상황을 생각해보면

인접 행렬에서는 graph[1][7]만 확인하면 된다. 

인접 리스트에서는 노드1에 대한 인접 리스트를 앞에서부터 차례대로 확인해야한다. 

특정한 노드와 연결된 모든 인접 노드를 순회해야 하는 경우, 인접 리스트 방식이 인접 행렬 방식에 비해 메모리 공간의 낭비가 적다.

 

DFS(Depth-First Search = 깊이 우선 탐색)

그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘이다. 

 

기본적으로 DFS는 스택을 사용한다

step1) 탐색 시작 노드를 스택에 삽입하고 방문처리한다

step2) 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문처리한다.

방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼낸다.

step3) step2의 과정을 더 이상 수행할 수 없을때까지 반복한다.

일반적으로 인접한 노드 중에서 방문하지 않은 노드가 여러 개 있으면 번호가 낮은 순서부터 처리함 

 

1) 시작노드인 '1'인 스택에 삽입하고 방문처리한다

 

2) 스택의 최상단 노드인 '1'에 방문하지 않은 인접 노드 '2', '3', '8'이 있다.

이 중에서 가장 작은 노드인 '2'를 스택에 넣고 방문처리한다.

 

3) 스택의 최상단 노드인 '2'에 방문하지 않은 인접 노드 '7'이 있다. 따라서 '7'번 노드를 스택에 넣고 방문 처리를 한다.

 

4) 스택의 최상단 노드인 '7'에 방문하지 않은 인접 노드 '6'과 '8'이 있다. 이 중에서 가장 작은 노드인 '6'을 스택에 넣고 방문처리를 한다.

 

5) 스택의 최상단 노드인 '6'에 방문하지 않은 인접 노드가 없다. 따라서 스택에서 '6'번 노드를 꺼냄

 

6) 스택의 최상단 노드인 '7'에 방문하지 않은 인접 노드 '8'이 있다. 따라서 '8'번 노드를 스택에 넣고 방문 처리를 한다.

 

7) 스택의 최상단 노드인 '8'에 방문하지 않은 인접 노드가 없다. 따라서 스택에서 '8'번 노드를 꺼낸다.

 

8) 스택의 최상단 노드인 '7'에 방문하지 않은 인접 노드가 없다. 따라서 스택에서 '7'번 노드를 꺼낸다.

 

9) 스택의 최상단 노드인 '2'에 방문하지 않은 인접 노드가 없다. 따라서 '2'번 노드를 껀내다.

 

10) 스택의 최상단 노드인 '1'에 방문하지 않은 인접 노드 '3'을 스택에 넣고 방문 처리한다.

 

11) 스택의 최상단 노드인 '3'에 방문하지 않은 인접 노드 '4'와 '5'가 있다. 이 중에서 가장 작은 노드인 '4'를 스택에 넣고 방문처리한다. 

 

12) 스택의 최상단 노드인 '4'에 방문하지 않은 인접 노드 '5'가 있다. 따라서 '5'번 노드를 스택에 넣고 방문 처리를 한다.

 

13) 남아있는 노드에 방문하지 않은 인접 노드가 없다. 따라서 모든 노드를 차례대로 꺼내면 

1 -> 2 -> 7 -> 6 -> 8 -> 3 -> 4 -> 5

스택을 이용하는 알고리즘이기 때문에 실제 구현은 재귀 함수를 이용했을 때 매우 간결하게 구현할 수 있다. 

BFS(Breadth First Search = 너비 우선 탐색)

가까운 노드부터 탐색하는 알고리즘이다. 최대한 멀리 있는 노드를 우선으로 탐색하는 방식으로 동작한다. 

 

기본적으로 큐를 이용한다.

step1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.

step2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리

step3. step2의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

1) 시작 노드인 '1'을 큐에 삽입하고 방문처리를 한다. 방문처리된 노드는 회색으로, 큐에서 꺼내 현재 처리하는 노드는 하늘색으로 표현했다.

 

2) 큐에서 노드 '1'을 꺼내고 방문하지 않은 인접 노드 '2', '3', '8'을 모두 큐에 삽입하고 방문 처리를 한다.

 

3) 큐에서 노드 '2'를 꺼내고 방문하지 않은 인접 노드 '7'을 큐에 삽입하고 방문 처리를 한다.

 

4) 큐에서 노드 '3'을 꺼내고 방문하지 않은 인접 노드 '4'와 '5'를 모두 큐에 삽입하고 방문처리한다.

 

5) 큐에서 노드 '8'을 꺼내고 방문하지 않은 인접 노드가 없으므로 무시한다. 

 

6) 큐에서 노드 '7'을 꺼내고 방문하지 않은 인접 노드 '6'을 큐에 삽입하고 방문처리한다.

 

7) 남아있는 노드에 방문하지 않은 인접 노드가 없다. 따라서 모든 노드를 차례대로 꺼내면 최종적으로 아래와 같다.

 

노드의 탐색 순서: 1 - 2 - 3 - 8 - 7 - 4 - 5 - 6 

deque 라이브러리를 사용하는 것이 좋다고 하고, 탐색을 수행하는데 O(N)의 시간이 소요된다. 

1260, DFS와 BFS, C++ 

우리가 그림은 그릴 수가 없으니까 

트리를 인접행렬이나 인접리스트로 표현할 수가 있다.

for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    graph[u].push_back(v);
    graph[v].push_back(u); // 무방향 그래프
}
for (int i = 0; i < graph.size(); i++)
{
    sort(graph[i].begin(), graph[i].end());
}

 

DFS 코드

fill(visited.begin(), visited.end(), false);
dfs_recursive(startNode);
cout << endl;

 ⏫ 함수 호출부분

// DFS (재귀 방식)
void dfs_recursive(int node) {
    visited[node] = true;
    cout << node << " ";

    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs_recursive(neighbor);
        }
    }
}

⏫ DFS 재귀방식 연산

// DFS (스택 방식)
void dfs_stack(int start) {
    stack<int> s;
    s.push(start);

    while (!s.empty()) {
        int node = s.top();
        s.pop();

        if (!visited[node]) {
            visited[node] = true;
            cout << node << " ";
        }

        // 인접 노드를 역순으로 스택에 추가
        for (auto it = graph[node].rbegin(); it != graph[node].rend(); ++it) {
            if (!visited[*it]) {
                s.push(*it);
            }
        }
    }
}

 ⏫DFS 스택연산

 

BFS 코드

fill(visited.begin(), visited.end(), false);
bfs(startNode);
cout << endl;

 ⏫함수호출 부분 

// BFS
void bfs(int start) {
    queue<int> q;
    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        cout << node << " ";

        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}

 

 

 

2606, 바이러스, C++

 

컴퓨터의 수 = 노드의 수

네트워크 연결 = 간선의 수

1부터 시작

 

DFS 그래프를 사용하여 코드 구현 ⏬

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

// 그래프의 인접 리스트 표현
vector<vector<int>> graph;
vector<bool> visited;

// DFS (스택 방식)
void dfs_stack() {
	stack<int> s; int count = 0;
	s.push(1);

	while (!s.empty()) {
		int node = s.top();
		s.pop();
		

		if (!visited[node]) {
			visited[node] = true;
		}

		// 인접 노드를 역순으로 스택에 추가
		for (auto it = graph[node].rbegin(); it != graph[node].rend(); ++it) {
			if (!visited[*it]) {
				s.push(*it);
			}
		}
	}
	for (int i = 2; i < visited.size(); i++)
	{
		if(visited[i]==true)
			count++;
	}
	cout << count;
}


int main() {
	int n, m; // 노드와 간선의 개수
	cin >> n;
	cin >> m;

	graph.resize(n + 1);
	visited.resize(n + 1, false);

	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		graph[u].push_back(v);
		graph[v].push_back(u); // 무방향 그래프
	}
	for (int i = 0; i < graph.size(); i++)
	{
		sort(graph[i].begin(), graph[i].end());
	}
    
	fill(visited.begin(), visited.end(), false);
	dfs_stack();

	return 0;
}

 

2644, 촌수계산, C++

 

전체 사람의 수 n = 노드의 수

서로 다른 두 사람의 관계 = 출력

부모 자실들 간의 관계의 개수 = 간선의 수 

 

 

코드 구현 ⏬

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

// 그래프의 인접 리스트 표현
vector<vector<int>> graph;
vector<int> visited;

// BFS를 이용한 촌수 계산
int bfs(int start, int target) {
    queue<int> q;
    q.push(start);
    visited[start] = 0; // 시작 노드의 촌수는 0

    while (!q.empty()) {
        int node = q.front();
        q.pop();

        // 연결된 노드 탐색
        for (int neighbor : graph[node]) {
            if (visited[neighbor] == -1) { // 방문하지 않은 경우
                visited[neighbor] = visited[node] + 1; // 촌수 갱신
                if (neighbor == target) { // 목표 노드에 도달하면
                    return visited[neighbor];
                }
                q.push(neighbor);
            }
        }
    }
    return -1; // 목표 노드에 도달할 수 없는 경우
}

int main() {
    int n, m, start, target; // 노드, 간선 개수, 시작 노드, 목표 노드
    cin >> n >> start >> target >> m;

    graph.resize(n + 1);
    visited.resize(n + 1, -1); // 초기화: -1 (방문하지 않음)

    // 간선 입력
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u); // 무방향 그래프
    }

    // BFS를 이용하여 촌수 계산
    int result = bfs(start, target);
    cout << result << endl;

    return 0;
}

 

시작노드를 큐에 삽입하고, 촌수를 0으로 설정

큐에서 노드를 하나씩 꺼내면서, 해당 노드와 연결된 모든 노드를 탐색한다

연결된 노드 중 방문하지 않은 노드를 큐에 삽입하고, 촌수를 현재 노드의 촌수 +1로 갱신한다 (삽입개수를 말함.)

탐색 중 목표 노드(target)에 도달하면, 해당 노드의 촌수를 반환한다.

큐가 empty()이어도 목표 노드에 도달하지 못한 경우 01을 반환한다.

목표노드와 연결되지 않은 경우 함수는 -1을 반환한다.

참고

https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html

이것이 코딩 테스트다 with 파이썬, 나동빈, 한빛미디어

 

 

 

728x90
저작자표시 비영리 변경금지

'Dev' 카테고리의 다른 글

EVI$ION 겨울방학 코테스터디 2주차 과제  (0) 2025.01.11
EVI$ION 겨울방학 코테스터디 1주차 과제  (5) 2025.01.03
BOJ 1543 문서검색 문제  (2) 2024.09.27
BOJ - 11399 ATM 문제 풀이  (0) 2024.09.26
GitHub 사용법  (0) 2024.09.20
'Dev' Related Articles more