[스터디 - 3회차]

2주차 - 그래프이론, DFS, BFS

그래프 이론의 기초

• 정점
  • 노드
  • 그래프를 형성하는 기본 단위
  • 분할할 수 없는 객체이자, “점”으로 표현되는 위치, 사람, 물건 등이 될 수 있음
• 간선
  • 정엄을 잇는 선
  • 관계, 경로
• indegree, outdegree
  • ‘u’ → ‘v’로 가는 경로가 4개이면: u의 outdegree가 4, v의 indegree는 2
• 정점과 간선의 집합을 ‘그래프’라고 한다.
• 가중치

---

Tree(트리)

• 트리는 자식노드와 부모노드로 이루어진 계층적인 구조를 가지며 무방향그래프의 일종이자 사이클이 없는 자료구조를 의미한다.
  • 방향그래프: directed graph
  • 무방향그래프: undirected graph
    • 트리는 무방향그래프를 중심으로 설명
• directed edge → arc라고 부르기도 함
• 트리의 특징은 다음과 같다.
  • 부모, 자식 계층 구조를 가짐
  • V - 1 = E 라는 특징이 있음 (간선 수는 노드 수 - 1)
  • 임의의 두 노드 사이의 (최단)경로는 ‘유일무이’하게 ‘존재’. 즉, 트리 내의 어떤 노드와 어떤 노드까지의 경로는 반드시 있으며 하나밖에 없음
• 루트노드
  • 가장 위에 있는 노드
  • 보통 트리문제가 나오고 탐색할 때 루트노드를 중심으로 탐색하면 쉽게 풀릴 수도…?
• 내부노드
  • 루트 ↔ 리프노드 사이
• 리프노드
  • 자식노드가 없는 노드
• 깊이
  • 각 노드마다 다르며 루트 노드에서 특정 노드까지 최단거리로 갔을 때의 거리
• 높이
  • 트리의 높이는 루트 노드부터 리프 노드까지의 거리 중 가장 긴 거리
• 레벨
  • 깊이와 같은 의미
  • 문제마다 다름
• 숲(forest)
  • 트리로 이루어진 집합

---

이진트리(BT, Binary Tree)

• 각각의 자식노드 수가 2개 이하로 되어있는 트리
• 이진트리의 종류

https://blog.naver.com/jhc9639/222289089015

[알고리즘 강의] 2주차. 그래프이론, 인접행렬, 인접리스트, DFS, BFS, 트리순회

 

• 정이진 트리, 완전 이진 트리, 변질 이진 트리, 포화 이진 트리, 균형 이진 트리
• 균형 이진 트리
  • 모든 노드의 왼쪽 하위트리와 오른쪽 하위트리의 차이가 1이하인 트리
  • map, set을 구성하는 레드블랙트리는 균형이진트리의 일종

 

• 이진탐색트리(BST, Binary Search Tree)
  • 오른쪽 하위트리에는 ‘노드의 값보다 큰 값’, 왼쪽 하위트리에는 ‘노드의 값보다 작은값’이 들어있는 트리
  • 시간복잡도
    • 탐색, 삽입, 숙제, 수정 모두 O(logN)
  • 이진탐색트리는 삽입순서에 따라 영향을 받음
    • 그러나 이를 고려하지 않고 트리의 노드들을 회전시키는 등의 방법을 통해서 ‘균형 잡히게’ 만들 수 있음.
    • e.g: AVL 트리, 레드블랙트리
•  
• 인접
• == 이어져있다.
• 인접배열
  • bool type의 정사각 행렬로 만들기
  • e.g → node 0, node 1이 양쪽으로 이어진 형태

	0	1
0	-	1
1	1	-

• 타고타고 들어간다..?
  • 재귀를 이용 → dfs..
• 인접리스트
  • vector로 구현 → vector<int> adj[V] //벡터가 여러개 있는 거
  • 삽입, 삭제 → O(1)
  • 탐색 → O(n)

• 그래서 인접배열, 인접리스트 중에 뭐 써야함?
  • 그래프가 희소할 때는 인접리스트, 조밀 할 때는 인접행렬이 좋다.
  • 보통은 인접리스트를 쓰면 됨. 문제에서 sparse한 그래프가 많이 나옴
• MAP, 방향벡터
  • 문제에서 지도로 주어지면.. 지도 기반으로 문제를 풀어야 함.
• dy, dx로 방향 설정하기

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

• 연결된 컴포넌트
  • 연결된 하위그래프, 연결된 하나의 덩어리를 의미함
  • “모든 정점을 연결하는 경로가 있다” 라는 특징을 가짐
• DFS (Depth First Search)
  • 어떤 노드부터 시작해 인접한 노드들을 재귀적으로 방문하며 방문한 정점은 다시 방문하지 않으며 각 분기마다 가능한 가장 멀리 있는 노드까지 탐색하는 알고리즘
  • Full Code

void dfs(int u) {
        visited[u] = 1;
        for(int v : adj[u]) {
                if(visited[v] == 0) {
                        dfs(v);
                }
        }
        cout << u << "로부터 시작한 함수 종료\n";
        return;
}

• BFS (Breath First Search)
  • 어떤 정점에서 시작해 다음 깊이의 정점으로 이동하기전 현재 깊이의 모든 정점을 탐색하며 방문한 정점은 다시 방문하지 않는 알고리즘
  • 레벨별로 탐색
  • 최단거리를 나타낼 때

int visited[100];

void bfs(int here) {
        queue<int> q;
        visited[here] = 1;
        q.push(here);
        while(q.size()) {
                int here = qq.front(); q.pop();
                for(int there : adj[here]) {
                        if(visited[there]) continue;
                        visited[there] = visited[here] + 1;
                        q.push(there);
                }
        }
}

• DFS, BFS 비교
  • 둘의 시간복잡도는 동일함
  • DFS: 메모리를 덜 씀. 절단점 등 구할 수 있음. 코드가 좀 더 짧으며 완전탐색의 경우 많이 씀.
  • BFS: 메모리를 더 씀. 가중치가 같은 그래프내에서 최단거리를 구할 수 있음. 코드가 더 김

---

문제풀이

• 미로찾기 - SILVER1

채점 현황

채점 현황

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

string s;
int N, M;
int arr[101][101];
bool visited[101][101];
int dist[101][101];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

void bfs(int x, int y) {
    queue<pair<int, int> > q;
    q.push(make_pair(x, y));
    dist[x][y] = 1;
    visited[x][y] = true;

    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx <= 0 || nx > N || ny <= 0 || ny > M || visited[nx][ny] || arr[nx][ny] == 0) continue;

            q.push(make_pair(nx, ny));
            dist[nx][ny] = dist[x][y] + 1;
            visited[nx][ny] = true;
        }
    }
}
int main() {
    cin >> N >> M;
    for(int i = 1; i <= N; i++) {
        cin >> s;
        for(int j=1;j<=s.length();j++){
            arr[i][j] = s[j-1] - '0';
        }
    }
    bfs(1, 1);

    cout << dist[N][M] << "\n";
    return 0;
}

 

• 유기농 배추 - SILVER1

1012번: 유기농 배추

1012번: 유기농 배추

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stdlib.h>
#include <string.h>

using namespace std;

int N, M, K, cnt, res;
int arr[51][51];
bool visited[51][51];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

void bfs(int x,int y)  {
    if(arr[x][y]!=1||visited[x][y]||x<0||y<0||x>=M||y>=N) {
        return ;
    }

    visited[x][y] = true;
    res++;
    queue<pair<int, int> > q;

    q.push(make_pair(x, y));
    while(!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for(int i=0;i<4;i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(arr[nx][ny]!=1||visited[nx][ny]||nx<0||ny<0||nx>=M||ny>=N) {
                continue;
            }

            q.push(make_pair(nx, ny));
            visited[nx][ny] = true;
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> cnt;
    for(int i=0;i<cnt;i++ ){
        res = 0;
        cin >> M >> N >> K;
        for(int i=0;i<K;i++){
            int x, y;
            cin >> x >> y;
            arr[x][y] = 1;
        }
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                if(!visited[j][i]&&arr[j][i]==1) {
                    bfs(j, i);
                }
            }
        }
        cout << res << "\n";
        for(int i=0;i<51;i++){
            for(int j=0;j<51;j++){
                visited[i][j] = false;
                arr[i][j] = 0;
            }
        }
    }
    return 0;
}

 

• 안전영역 - SILVER1

2468번: 안전 영역

2468번: 안전 영역

#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <queue>
#include <string.h>

using namespace std;

bool visited[101][101];
int map[101][101];
int cpy[101][101];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

int N, res = -2147483647, cnt, cur = -2147483647;

void bfs(int y, int x) {
    if(visited[y][x]||x<0||y<0||x>=N||y>=N) {
        return ;
    }

    visited[y][x] = true;

    queue<pair<int, int> > q;
    q.push(make_pair(y, x));
    while(!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;

        q.pop();
        for(int i=0;i<4;i++){
            int ny = y + dy[i];
            int nx = x + dx[i];

            if(map[ny][nx] < 1||visited[ny][nx]||nx<0||ny<0||nx>=N||ny>=N) {
                continue;
            }
            q.push(make_pair(ny, nx));
            visited[ny][nx] = true;
        }
    }
}

int main() {
    cin >> N;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++) {
            cin >> cpy[i][j];
            cur = max(cur, cpy[i][j]);
        }
    }

    for(int k=0;k<cur;k++){
        cnt = 0;
        for(int i= 0;i<N;i++){
            for(int j=0;j<N;j++){
                map[i][j] = cpy[i][j] - k;
            }
        }

        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(!visited[i][j]&&map[i][j]>=1){
                    bfs(i, j);
                    cnt++;
                }
            }
        }

        res = max(res, cnt);

        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                visited[i][j] = false;
            }
        }
    }
    cout << res << "\n";
    return 0;
}

 

• 영역 구하기 - SILVER1

채점 현황

채점 현황

#include <iostream>
#include <string.h>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

int N, M, K;
int map[104][104];
bool visited[104][104];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
int cnt, res;
vector<int> v;

void bfs(int y, int x) {
    visited[y][x] = true;
    queue<pair<int, int> > q;
    q.push(make_pair(y, x));

    res++;
    cnt = 1;

    while(!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
        for(int i=0;i<4;i++){
            int ny = y + dy[i];
            int nx = x + dx[i];

            if(ny<0||nx<0||ny>=N||nx>=M||visited[ny][nx]==true){
                continue;
            }
            if(map[ny][nx]==0){
                q.push(make_pair(ny, nx));
                visited[ny][nx] = true;
                cnt++;
            }
        }
    }
    v.push_back(cnt);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M >> K;
    for(int i=0;i<K;i++){
        int x1, x2, y1, y2;
        cin >> x1 >> y1;
        cin >> x2 >> y2;
        for(int j=y1;j<y2;j++){
            for(int k=x1;k<x2;k++){
                map[j][k] = 1;
            }
        }
    }

    for(int j=0;j<N;j++){
        for(int k=0;k<M;k++){
            if(!visited[j][k]&&map[j][k]==0){
                bfs(j,k);
            }
        }
    }
    cout << res << "\n";
    sort(v.begin(), v.end());
    for(int i=0;i<v.size();i++){
        cout << v[i] << " ";
    }
    return 0;
}

 

• 쿼드트리 - SILVER1
  • 쿼드트리에 대한 설명은 https://hyo-ue4study.tistory.com/235 을 참고하자.

1992번: 쿼드트리

1992번: 쿼드트리

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N;
int arr[65][65];

void go(int size, int y, int x)
{
    if(size == 1)
    {
        cout << arr[y][x];
        return ;
    }
    int check_one = 0;
    int check_zero = 0;
    for(int i=y;i<y+size;i++){
        for(int j=x;j<x+size;j++){
            if(arr[i][j] == 1)
                check_one = 1;
            if(arr[i][j] == 0)
                check_zero = 1;
        }
    }
    if (check_one == 0){
        cout << 0;
        return;
    }
    if (check_zero == 0){
        cout << 1;
        return ;
    }
    cout << "(";
    go(size/2, y, x);
    go(size/2, y, x + size/2);
    go(size/2, y+size/2, x);
    go(size/2, y+size/2, x+size/2);
    cout << ")";
}

int main() {
    cin >> N;
    for(int i=0;i<N;i++){
        string s;
        cin >> s;
        for(int j=0;j<N;j++){
            arr[i][j] = s[j]-'0';
        }
    }

    go(N, 0, 0);
}

 

• 사과 담기 게임 - SILVER5

2828번: 사과 담기 게임

2828번: 사과 담기 게임

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int N, M, J, cnt;

int main() {
    cin >> N >> M >> J;
    // 그냥 돌리기만 하면 될듯
    int res = 0;

    int start = 1, ed = M;

    for(int i=0;i<J;i++){
        cin >> cnt;
        while(1) {
            if(start <= cnt && cnt <= ed ) {
                break;
            } else if(start > cnt) {
                start--;
                ed--;
            } else {
                start++;
                ed++;
            }
            res++;
        }
    }

    cout << res << "\n";
    return 0;
}

 

• 빈도 정렬 - SILVER3
  • 사실 하다가 도저히 안 풀려서 해설을 보았다.
  • 인덱스를 위한, 빈도수를 위한 자료구조를 2개를 나누는 방법을 생각했어야 되는데, 하나의 map을 바탕으로 다 처리하려니 너무 복잡하게 생각을 하게 된 거 같다.

2910번: 빈도 정렬

2910번: 빈도 정렬

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

int N, C;
// m1 -> 몇 번 입력되었는지
// m2 -> 어떤 인덱스에서 입력되었는지
map<int, int> m1, m2;
vector<pair<int, int> > v; 

bool compare(pair<int, int> i, pair<int, int> j) {
    if(i.first == j.first) {
        return m2[i.second] < m2[j.second];
    }
    return i.first > j.first;
}

int main() {
    cin >> N >> C;
    for(int i=0;i<N;i++){
        int a;
        cin >> a;
        m1[a]++;
        if(m2[a] == 0) {
            m2[a] = i + 1;
        }
    }

    for(auto it : m1) {
        v.push_back(make_pair(it.second, it.first));
    }

    sort(v.begin(), v.end(), compare);
    for(auto i : v){
        for(int j = 0; j < i.first; j++){
            cout << i.second << " ";
        }
    } 
    return 0;

}

 

 

• 연구소 - GOLD4
  • BFS, 빡구현으로 풀리는 문제이다.
  • 처음 조합을 어떻게 뽑을 지 고민을 하다가 -> 좌표 쌍을 vector에 넣어서 조합으로 좌표들을 선택했다.

https://www.acmicpc.net/problem/14502

14502번: 연구소

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

int N, M, res, cnt;
vector<pair<int, int> >v;
int MAP[9][9];
int cpy[9][9]; // 원 상태로 되돌리기 위한 map
bool visited[9][9];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

void bfs(int y, int x) {
    visited[y][x] = true;

    queue<pair<int, int> > q;
    q.push(make_pair(y, x));

    while(!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;

        q.pop();
        for(int i=0;i<4;i++){
            int ny = y + dy[i];
            int nx = x + dx[i];

            if(MAP[ny][nx]==1||ny<0||nx<0||ny>=N||nx>=M||visited[ny][nx]){
                continue;
            }

            q.push(make_pair(ny, nx));
            MAP[ny][nx] = 2;
            visited[ny][nx] = true;
        }
    }

}
int main() {
    ios_base :: sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL);
    
    cin >> N >> M;

    for(int i=0;i<N;i++ ){
        for(int j=0;j<M;j++){
            cin >> MAP[i][j];
            cpy[i][j] = MAP[i][j];
            if(MAP[i][j] == 0) {
                v.push_back(make_pair(i, j));
            }
        }
    }
    
    // 3개를 뽑은 다음에
    for(int a=0;a<v.size();a++){
        for(int b=a+1;b<v.size();b++){
            for(int c=b+1;c<v.size();c++){
                MAP[v[a].first][v[a].second] = 1;
                MAP[v[b].first][v[b].second] = 1;
                MAP[v[c].first][v[c].second] = 1;
                cnt = 0;
                // bfs를 돌림 -> 2인 부분에서만 진입
                for(int i=0;i<N;i++ ){
                    for(int j=0;j<M;j++){
                        if(MAP[i][j] == 2 && !visited[i][j]){
                            bfs(i, j);
                        }
                    }
                }

                // bfs를 돈 후에 
                for(int i=0;i<N;i++){
                    for(int j=0;j<M;j++){
                        if(MAP[i][j] == 0){
                            cnt++;
                        }
                    }
                }
                // cnt를 비교한 후에 map을 다시 원상태로 돌려줌
                res = max(res, cnt);
                for(int i=0;i<N;i++){
                    for(int j=0;j<M;j++){
                        MAP[i][j] = cpy[i][j];
                        visited[i][j] = false;
                    }
                }
            }
        }
    }
    cout << res << "\n";
    return 0;
}