Computer Science & Engineering

https://programmers.co.kr/learn/courses/30/lessons/17678

이 문제는 조건을 차근차근 맞춰나가면 충분히 풀 수 있는 문제이다. 핵심은 버스의 수, 버스 1대당 탈 수 있는 인원의 수를 생각해야한다는 점이다. 시간관련 문제를 풀 때 모든 시간을 가장 작은 단위로 통일하는 것이 굉장히 편하다. 이 문제에서는 가장 작은 단위가 분이므로 모든 시간을 몇분인지 계산하면 쉽게 구할 수 있다. 특히 소수점이 나오는 시간문제는 부동 소수점으로 계산할 경우 계산 과정에서 원하는 값이 나오지 않을 수 있으므로 integer형으로 계산하는 것이 가장 좋다. 코드는 다음과 같다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool cmp(string a, string b) { //내림차순 정렬
    return a > b;
}

int part(string a) { //string을 시간으로 변경
    pair<int,int> hm;
    hm.first = stoi(a.substr(0, 2)); //hour 분리
    hm.second = stoi(a.substr(3, 2)); //minute 분리
    int ret = hm.first * 60; //분으로 합치기
    ret += hm.second;
    return ret;
}

string timetostring(int time) { //시간을 string으로 변경
    string ret = "";
    int h = time / 60; //hour 분리
    int m = time % 60; //minute 분리
    if(h < 10) //1자리 수인 경우 앞에 '0' 붙이기
        ret += '0';
    ret += to_string(h);
    ret += ':';
    if(m < 10) //1자리 수인 경우 앞에 '0' 붙이기
        ret += '0';
    ret += to_string(m);
    return ret;
}

string solution(int n, int t, int m, vector<string> timetable) {
    string answer = "";
    sort(timetable.begin(), timetable.end(), cmp); //내림차순으로 정렬
    int now = 540; //9시 정각
    int end = now + (t * (n-1)); //버스 마지막 시간
    int cnt = 0; //마지막 버스 탑승자 카운트
    for(int i = 0; i < n; i++) { //n개의 버스
        if(i == n - 1) { //마지막 버스일 경우
            if(cnt == m - 1) break; //1자리 남은 경우 break
        }
        if(timetable.empty()) break; //모두 탄 경우 break
        for(int j = 0; j < m; j++) { //m개의 탑승자 수 만큼
            if(timetable.empty()) break; //모두 탄 경우 break
            int hm = part(timetable.back()); //가장 빨리온 사람 시간으로 변경
            if(hm <= now) { //현재 버스를 탈 수 있는 경우
                timetable.pop_back(); //버스에 탑승
                if(i == n - 1) { //마지막 버스인 경우
                    cnt++; //탑승자 수 증가
                    if(cnt == m-1) break; //마지막 버스 1자리 남은 경우 break
                }
            }
            else { //가장 빨리온사람도 현재 버스를 탈 수 없는 경우 break
                break;
            }
        }
        now += t; //다음 버스
    }
    if(timetable.empty()) { //모두 버스에 타고도 자리가 남은 경우
        answer = timetostring(end); //마지막 버스 탑승
    }
    else {
        int back = part(timetable.back()); //남은 탑승자 중에 가장 빠른 사람
        if(back > end) { //마지막 버스보다 뒤에 오는 경우
            answer = timetostring(end); //콘은 마지막 버스 탑승
        }
        else { //남은 탐승자 중에 가장 빠른 사람이 버스를 탈 수 있는 경우
            back--; //콘은 1분 일찍 도착해서 버스 탑승
            answer = timetostring(back);
        }
    }
    return answer;
}

이 문제에서 중요한 것은 마지막 버스이다. 마지막 버스에 자리가 있는지 없는지를 판단하는 것이다. 각 버스에 최대 m명을 태울 수 있으므로 버스가 오는 시간까지 기다리고 있는 사람은 버스에 태워 보낸다. m명이 모두 차지 않더라도 정류장에 도착한 사람이 없는 경우 버스는 출발한다. 마지막 버스가 도착했을 때 m-1명까지만 버스에 태운다. 마지막 1자리는 콘이 타야하기 때문이다. 그리고 프로그램 마지막에 판단한다. 이때 경우의 수가 3가지가 있다.

    1. 만약 정류장에 기다리는 사람이 없는 경우 콘은 마지막 버스가 출발하는 시간에 도착하면 된다.

    2. 만약 정류장에 사람이 기다리고 있지만 그 사람은 마지막 버스가 출발하는 시간보다 늦게 오는 경우 1번과 마찬가지로 마지막 버스의 시간과 같으면 된다.

    3. 마지막으로 남은 탑승자가 마지막 버스가 출발하는 시간보다 먼저 와서 기다리는 경우 그 사람보다 1분 먼저 도착하면 된다. 그렇다면 가장 높은 우선순위이기 때문에 마지막 1자리를 탈 수 있다.

이렇게 버스는 n개, 버스 하나 당 m명 탑승 가능이라는 조건을 하나하나 맞춰 나가고 마지막 1자리를 콘이 탈 수 있는 조건으로 위의 3가지 경우만 생각할 경우 문제를 쉽게 풀 수 있다. 이 문제의 핵심은 string으로 주어진 시간을 integer형으로 바꾸어 계산을 편하게 한 점과 조건을 하나하나 맞춰 경우의 수를 나누어 풀은 부분이라고 생각한다.

https://programmers.co.kr/learn/courses/30/lessons/77486

이 문제는 읽어보면 아주 간단한 문제이다. 문제를 읽고 DFS방식으로 풀면 금방 풀릴 것이라는 생각이 바로 들 것이다. 다단계에서 판매하는 칫솔의 수익의 10퍼센트를 자신을 추천한 사람에게 줄 때 사람들의 수익을 구하는 문제이다. 코드는 다음과 같다.

#include <string>
#include <vector>
#include <map>
using namespace std;

map<string,string> graph; //누구에게 추천받았는지를 저장
map<string, int> cost; //각 사람이 번 돈을 저장할 map

void dfs(string now, int amount) { //현재 사람이 번 돈
    string ref = graph[now]; //추천인이 누군지 찾음
    int nxt = amount / 10; //10퍼센트 떼서
    if(ref == "-") { //center를 만날 경우
        cost[now] += (amount - nxt); //자기 자신은 10퍼센트를 떼고 얻음
        return;
    }
    else { //추천인이 center가 아닌 경우
        int nxt = amount / 10; //10퍼센트를 떼서
        cost[now] += (amount - nxt);  //자기 자신은 나머지를 갖고
        if(nxt == 0) return; //만약 10퍼센트가 1원도 안나올 경우 dfs 멈춤
        dfs(ref, nxt); //추천인에게 줄 돈이 남은 경우 추천인의 추천인 계속 탐색
    }
}

vector<int> solution(vector<string> enroll, vector<string> referral, vector<string> seller, vector<int> amount) {
    vector<int> answer;
    for(int i = 0; i < enroll.size(); i++) { //모든 사람에 대하여
        graph[enroll[i]] = referral[i]; //자신을 추천한 사람 map으로 연결
    }
    
    for(int i = 0; i < seller.size(); i++) { //판매한 사람 모두 dfs로 추천인에게 10퍼센트씩 부여
        dfs(seller[i], amount[i] * 100); //칫솔 1개에 100원이므로 판매 수에 100을 곱한다
    }
    
    for(int i = 0; i < enroll.size(); i++) {
        if(cost.find(enroll[i]) == cost.end()) //만약 수익이 없는 사람을 발견할 경우
            answer.push_back(0); //0원 push_back
        else
            answer.push_back(cost[enroll[i]]); //map에 저장한 수익 push_back
    }

    return answer;
}

    DFS를 이용하여 자신의 추천인에게 10퍼센트를 계속 떼어 주는 것이다. 만약 현재 돈이 10원 미만이어서 10퍼센트를 떼었을 경우 1원도 나오지 않을 경우 DFS를 빠져나오게 된다. 저 조건을 뺄 경우 몇몇 테스트 케이스에서 시간초과가 발생한다. 불필요한 탐색을 거르는 장치인 것이다.

    그래프와 각 사람이 번 돈들을 map으로 표현하는 것이 핵심이었다. 다른 표현 방법으로 각 사람을 인덱스 번호로 표현하여 각각 사람의 인덱스를 가지고 있고 찾아봐야할텐데 map을 이용하여 그러한 시간을 줄이고 더 편하게 이름으로 사람을 찾을 수 있었다.

    문제의 설명이 길어 긴장했지만 읽어보니 굉장히 단순하게 풀 수 있는 방법이었다. DFS 재귀 방식 말고도 while문을 이용하여 더 빠른 시간에 풀 수 있는 방법도 있으니 그 방법도 생각해보면 좋을 것 같다.

stack은 가장 기본적인 자료구조이다. 이 글에서는 C++의 template를 이용해 어떤 type의 변수던지 사용할 수 있는 STL의 stack을 그대로 구현해보겠다. 구현 방법은 이전 글인 vector만들기와 상당히 유사했다. 코드는 다음과 같다.

#include <iostream>
#include <stdlib.h>
#include <cstring>

using namespace std;

template <typename T>
class mystack {
private:
    int num;
    int len;
    T* tmp;
    T* arr;
public:
    mystack() { //생성자
        mystack::num = 0;
        mystack::arr = (T*)malloc(sizeof(T) * 10); //초기 stack 배열 크기 10으로 설정
        memset(arr, 0, sizeof(arr)); //배열 초기화
        len = 10; //초기 크기 10
        tmp = NULL;
    }

    ~mystack() { //소멸자
        if(arr) free(arr); //메모리 반환
    }

    T top() { //가장 위에 있는 원소 리턴
        return arr[num-1];
    }

    int size() { //stack에 있는 원소의 수 리턴
        return num;
    }

    bool empty() { //stack이 차있는 경우 false 빈 경우 true 리턴
        if(num) return false;
        else return true;
    }

    void pop() { //가장 위에 있는 원소 제거
        if(num == 0) return; //stack이 빈 경우 어떤 일도 일어나지 않음
        arr[num--] = 0; //가장 위에 있느 원소 0으로 설정하고 num 감수
        if(num < len/2) { //만약 배열의 절반도 안차있는 경우
            len /= 2; //배열 크기 절반으로 감소
            tmp = arr; //임시 배열 설정
            arr = (T*)malloc(sizeof(T) * len); //배열 절반 크기로 새로 생성
            for(int i = 0; i < num; i++) arr[i] = tmp[i]; //stack에 있는 원소 복사
            free(tmp); //임시 배열 메모리 반환
        }
    }

    void push(T input) { //원소 stack 맨 위에 추가
        if(num == len - 1) { //stack 배열이 모두 찬 경우
            len *= 2; //배열 크기 두배로 늘림
            tmp = arr; //임시 배열 설정
            arr = (T*)malloc(sizeof(T) * len); //배열 크기 두 배로 생성
            for(int i = 0; i < num; i++) arr[i] = tmp[i]; //stack에 있는 원소 복사
            free(tmp); //임시 배열 메모리 반환
        }
        arr[num++] = input; //원소 맨 위에 추가
    }
};

위의 코드를 이용하여 직접 stack을 실행시켜 보았다.

1부터 4096전까지 2씩  곱하며 stack에 넣었다. 이후 stack의 크기를 출력하였고 그 다음 7개의 원소 top을 출력하고 pop하였다. 그 결과 stack

의 크기를 또 한번 출력하였다. 결과는 다음과 같다.

다음과 같이 12개의 원소가 잘 들어갔고 7개의 원소가 잘 pop된 것을 알 수 있다. template를 사용하였기 때문에 int형 변수 말고도 mystack을 사용할 때 <>안에 다른 자료형을 사용할 수 있다. ADT인 class나 struct도 사용할 수 있기 때문에 굉장히 편리하게 사용할 수 있다. 다른 STL 구현 코드들도 아래 링크에서 확인할 수 있다.

https://github.com/Seo-sang/C-_Standard_Template_Library

https://programmers.co.kr/learn/courses/30/lessons/42583

이 문제는 문제 자체를 이해하는데도 굉장히 오래걸렸다. 다리의 길이와 다리에 올라갈 수 있는 트럭의 수를 같은 숫자를 쓰기 때문에도 헷갈렸고 다리를 트럭이 지나는데 다리의 길이만큼 시간이 필요하다는 것도 문제에 적혀져 있지 않아서 너무 아쉬운 문제였다. 이 문제는 쉽게 생각해 다리 길이만큼의 큐를 만들고 while문을 돌면서 트럭이 큐에 들어가게 만드는 것이 가장 쉬운 방법이었다. 코드는 다음과 같다.

#include <string>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
    int on_weight = 0;
    int i = 0;
    queue<int> q; //다리를 나타낼 큐
    for(int i = 0; i < bridge_length; i++) { //다리의 길이만큼 큐에 0을 채움
        q.push(0);
    }
    while(i < truck_weights.size()) { //다리에 트럭이 모두 올라갈 때까지
        if(q.front() != 0) { //다리를 빠져나가는 트럭의 무게를 뺌
            on_weight -= q.front();
        }
        q.pop(); //다리에서 트럭 pop
        answer++; //시간 경과
        if(on_weight + truck_weights[i] <= weight) { //다리에 다음 트럭을 올려도 무게가 넘지 않을 경우
            on_weight += truck_weights[i]; //무게 추가
            q.push(truck_weights[i]); //트럭 다리에 추가
            i++; //다음 트럭
        }
        else { //그렇지 않으면 트럭 추가하지 않고 0 추가
            q.push(0);
        }
    }
    return answer+bridge_length; //마지막 트럭이 다리를 지나는 시간인 다리 길이를 더하여 리턴
}

위의 코드를 보면 다리에 다음 트럭을 올리고자할 때 무게를 넘지 않는지 체크한다. 만약 무게가 넘어갈 경우 트럭을 올리지 않고 다리의 길이를 유지할 0을 큐에 push한다. 마지막에 리턴하기 전에 bridge_length를 더하는 이유는 마지막 트럭이 다리를 모두 지나는데 bridge_length 시간만큼 들기 때문에 더해야한다.

큐를 이용해 다리에서 트럭들이 while문을 돌면서 앞으로 하나씩 이동하는 것을 표현하는 것이 핵심이었고 while문을 돌 때마다 시간이 경과하여 시간초과가 날 것이라고 생각했는데 다행히 효용성을 테스트하는 케이스는 없어서 통과할 수 있었다. 실제 구현은 간단했지만 문제 난이도는 3단계로 느껴질정도로 문제를 이해하는 것도 어려웠다. 효용성 테스트가 없어서 2단계 문제인 것 같다.

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

이 문제는 BFS와 DFS모두 풀 수 있는 문제이다. 문제 알고리즘 분류는 깊이 우선 탐색이지만 글쓴이는 BFS를 이용하여 풀었다. 문제는 인접행렬이 주어졌을 때 2-친구의 수가 가장 많은 사람을 구하는 것이다. 2-친구는 두 사람이 친구이거나 한 사람을 건너서 친구인 친구를 말한다. 즉 깊이가 2 이하로 알고 있는 친구의 수이다. 코드는 다음과 같다.

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

const int MN = 51;

vector<int> g[MN]; //인접 리스트
bool vst[MN]; //방문배열

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    int rst = 0;
    int N; cin >> N;
    for(int i = 0; i < N; i++) {
        string s; cin >> s; //한 줄씩 string으로 입력 받음
        for(int j = 0; j < s.size(); j++) {
            if(s[j] == 'Y') { //친구인 경우 인접리스트에 추가
                g[i].push_back(j);
                g[j].push_back(i);
            }
        }
    }
    for(int i = 0; i < N; i++) { //0번부터 N-1번까지 2-친구의 수 구하기
        queue<int> q; //BFS에 이용할 큐
        memset(vst, 0, sizeof(vst)); //방문배열 초기화
        vst[i] = true; //자기 자신 방문 체크
        int cnt = 0;
        for(int e : g[i]) { //자기 자신의 친구 체크
            if(!vst[e]) {
                vst[e] = 1;
                cnt++;
                q.push(e);
            }
        }
        while(!q.empty()) { //자기 자신의 친구의 친구들만 확인
            int now = q.front(); q.pop();
            for(int e : g[now]) {
                if(!vst[e]) { //친구가 아닌 경우. 즉 친구의 친구인 경우
                    vst[e] = 1;
                    cnt++;
                }
            }
        }
        rst = max(rst, cnt); //2-친구가 가장 많은 사람의 2-친구 수 갱신
    }
    cout << rst;
}

이 문제는 깊이를 확인할 필요 없이 깊이가 2까지만 탐색하면 되므로 0번부터 N-1번까지의 친구를 큐에 넣고 수를 세고 큐가 빌 때까지 그 친구들의 친구의 수만 세주면 된다. 이때 친구의 친구를 발견할 경우 큐에 넣지 않으면 깊이가 2인 친구까지만 탐색할 수 있다. 그렇게 구한 2-친구의 수의 최대값을 출력하면 간단히 답을 구할 수 있다.

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

이 문제는 비 방향성 그래프의 간선이 주어졌을 때 V번 정점부터 시작하여 DFS로 탐색한 결과와 BFS로 탐색한 결과를 각각 출력하는 기본적인 그래프 탐색 문제이다. 입력은 정점의 개수 N, 간선의 개수 M, 탐색을 시작할 정점 번호 V와 M개의 간선들로 이루어진다. 코드는 아래와 같다.

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

const int MN = 1001;

vector<int> g[MN]; //인접 리스트
bool vst[MN]; //방문 여부
void dfs(int N) { //DFS
    vst[N] = true; //방문 체크
    cout << N << ' '; //방문한 노드 번호 출력
    for(int e : g[N]) { //방문한 노드로부터 인접 리스트를 확인
        if(!vst[e]) dfs(e); //방문하지 않은 노드 방문
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    int N, M, V; cin >> N >> M >> V;
    for(int i = 0; i < M; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v); //인접리스트 추가
        g[v].push_back(u);
    }
    for(int i = 1; i <= N; i++) { //정점 번호 오름차순으로 정렬
        sort(g[i].begin(), g[i].end());
    }
    dfs(V); //V번 정점부터 DFS
    cout << "\n" << V; //DFS출력 마지막을 나타내는 개행 후 BFS 시작정점 V출력
    queue<int> q; //BFS에 사용할 queue
    memset(vst, 0, sizeof(vst)); //방문 배열 초기화
    q.push(V); //시작 정점 queue에 추가
    vst[V] = true; //시작 정점 방문 체크
    while(!q.empty()) { //모든 정점을 방문할 때까지
        int now = q.front(); q.pop(); //queue의 첫 번째 pop
        for(int e : g[now]) { //인접리스트 확인
            if(!vst[e]) { //방문하지 않은 노드 발견할 경우
                cout << ' ' << e; //정점 출력
                vst[e] = 1; //방문 체크
                q.push(e); //queue에 추가
            }
        }
    }
}

방문하는 정점은 번호가 작은 것부터 우선적으로 방문해야하므로 우선 각 정점의 인접리스트를 오름차순으로 정렬한다.

    DFS를 우선적으로 출력하기 때문에 방문하지 않은 노드를 발견할 경우 곧바로 DFS로 탐색하여 정점을 출력하고 방문체크를 한다. 그 다음 그 노드로부터 인접리스트를 확인하여 더 탐색할 수 있는 정점이 있는지 확인한다. 있을 경우 재귀적으로 탐색한다.

    BFS는 queue를 이용한다. 방문한 노드를 체크하고 큐에 넣는다. 큐는 FIFO(First In First Out)이기 때문에 방문한 노드를 순서대로 확인할 수 있다. 시작정점 V를 큐에 넣고 방문 체크를 한다. 반복문은 큐가 빌때까지 반복한다. 큐의 첫 번째 원소를 pop한 후 그 원소의 인접 리스트를 확인한다. 방문하지 않은 노드를 발견할 경우 그 정점을 출력하고 방문체크를하고 큐에 push한다.

    백준에서는 개행이나 공백이 한 두개 더 출력되더라도 오답처리를 하지 않기 때문에 마지막일 경우 뒤에 공백이나 개행을 넣지 않기 위한 예외를 처리하지 않아도 된다.

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

이 문제는 BFS와 DFS 모두 풀 수 있는 문제이다. 글쓴이는 DFS를 이용하여 이 문제를 풀어보았다. 코드는 아래와 같다.

#include <iostream>
#include <string>
#include <algorithm>
#include <stdbool.h>
#include <vector>
#include <cstring>

using namespace std;

const int MN = 51;

int map[MN][MN]; //인접행렬
bool vst[MN][MN]; //방문 여부
int di[8] = {1, 0, 0, -1, 1, -1, 1, -1}; //8가지 방향으로 이동을 나타냄
int dj[8] = {0, 1, -1, 0, 1, 1, -1, -1};
int w, h;
void dfs(int i, int j) {
    vst[i][j] = true; //방문 체크
    for(int d = 0; d < 8; d++) { //8가지 방향을 탐색
        int ni = i + di[d]; //다음 i좌표
        int nj = j + dj[d]; //다음 j좌표
        if(0 <= ni && ni < h && 0 <= nj && nj < w) { //지도를 벗어나는지 확인
            if(!vst[ni][nj] && map[ni][nj]) { //방문 여부와 땅인지 여부 확인
                dfs(ni, nj); //재귀로 DFS 탐색
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    while(true) { //0을 입력받을 때까지 반복
        cin >> w >> h;
        if(w == 0 && h == 0) break; //0이 두 개 입력될 경우 종료
        memset(map, 0, sizeof(map)); //테스트케이스마다 초기화
        memset(vst, 0, sizeof(vst)); //테스트케이스마다 초기화
        for(int i = 0; i < h; i++) {
            for(int j = 0; j < w; j++) {
                cin >> map[i][j]; //지도 입력
            }
        }
        int cnt = 0;
        for(int i = 0; i < h; i++) {
            for(int j = 0; j < w; j++) {
                if(map[i][j] && !vst[i][j]) { //땅이고 방문하지 않은 경우 DFS 탐색
                    dfs(i, j);
                    cnt++;
                }
            }
        }
        cout << cnt << '\n';
    }
}

이 문제는 지도를 주어졌을 때 상하좌우 대각선으로 땅이 이어져 있다고 할 때 분리된 섬의 개수를 구하는 문제이다. 우리는 x, y좌표 형식으로 문제를 입력받기 때문에 위 코드의 di, dj 배열과 같이 8가지 방향을 나타낼 수 있다. 그림으로 나타내면 다음과 같이 나타낼 수 있다.

i, j에서 8가지 방향의 좌표를 더해 ni, nj 좌표를 구한다. 이때 지도를 벗어나는지를 확인해준다. 그렇지 않으면 Out of Bounds 에러가 발생할 수 있다.  그 다음 방문 여부와 땅인지의 여부를 확인하여 DFS 탐색을 계속한다. 이때 지도에서 땅인 부분의 DFS 횟수가 곧 섬의 개수인 것을 알 수 있다. 이전에 풀은 연결 요소의 개수와 구하는 방식이 비슷한 것을 알 수 있다. 차이점은 인접리스트 형식이 아니라 좌표형식으로 주어진 입력을 활용하여 좌표를 이동하며 DFS를 한다는 것이다.

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

이 문제는 방향이 없는 그래프를 주어졌을 때, 연결 요소의 개수를 구하는 문제이다. 즉 간선으로 연결되어 있는 집합의 개수가 총 몇 개인지를 출력하는 프로그램이다. bfs, dfs 모두 사용할 수 있는 문제지만 나는 dfs를 이용하였다. 코드는 다음과 같다.

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>

using namespace std;

bool visit[1001]; //방문 여부 판단
vector<int> g[1001]; //인접 리스트
void dfs(int n) { //DFS 함수
    visit[n] = 1;
    for(int nxt : g[n]) {
        if(!visit[nxt])
            dfs(nxt);
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); //시간 감소
    int N, M; cin >> N >> M;
    for(int i = 0; i < M; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v); //비방향성 그래프이므로 인접 리스트에 u->v, v->u 모두 추가
        g[v].push_back(u);
    }
    int cnt = 0;
    for(int i = 1; i <= N; i++) { //1부터 N까지 dfs를 하며 연결 요소의 개수 카운트
        if(!visit[i]) { //방문하지 않은 번호에서만 dfs
            dfs(i);
            cnt++;
        }
    }
    cout << cnt;
}

이 문제는 가장 간단한 DFS 문제중 하나이다. 1번 노드부터 N번 노드까지 DFS를 이용해 전부 방문하고 나면 visit 배열을 통해 방문한 노드인지 확인할 수 있다. 그러므로 이미 방문한 DFS의 횟수를 통해 연결 요소의 개수를 셀 수 있다.

인접 행렬은 인접 리스트에 비해 많은 메모리를 소모하기 때문에 vector를 지원하는 C++에서는 인접 리스트를 사용하는 것이 굉장히 좋다. DFS에서 재귀를 이용해 탐색할 때 방문 여부를 언제 체크하냐에 따라 재귀의 횟수를 많이 줄일 수 있다. 위와 같이 재귀를 하기 전에 방문 여부를 확인할 경우가 있고 재귀를 들어가서 첫 줄에 방문했을 경우 return하는 방식으로 프로그램을 구현할 수 있다. 후자의 경우 불필요한 방문이 될 수 있으므로 위의 코드와 같이 전자 방식으로 구현하는 것이 더 효율적이다.