greentea31's Note

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

풀이 과정

벽과 지나갈 수 있는 공간, 불과 지훈이의 위치가 주어지고 불은 상하좌우로 하루마다 한칸씩 번지며, 지훈이는 하루에 한칸씩 이동이 가능할 때, 지훈이가 미로에서 탈출할 수 있는지, 탈출이 가능하다면 걸리는 최소 날짜는 몇 일인지 구하는 문제이다.

flood fill bfs 문제이다. 지훈이를 불과 벽을 피해 bfs로 이동시키면서 미로의 밖에 도착이 가능한지, 가능하다면 도착하기까지의 날짜가 얼마나 걸리는지를 구해주면 된다.

풀고나서 다른 사람의 코드를 봤더니 불에 대한 BFS를 먼저 돌리고 각 칸에서 불이 번지는 시간을 먼저 계산후 지훈이의 BFS를 구하는 방법으로 푼 코드가 많았다. 그런데 사실 BFS를 2번 돌릴 필요가 없다. BFS의 시작 시점에 큐에 지훈이의 시작 위치를 넣은 후 불의 위치를 넣어서 지훈이의 진행과정이 불의 진행과정보다 먼저 이루어지게 한 후 BFS를 한번만 돌리면 된다.

# . F

# J #

# # #

같은 경우에 IMPOSSIBLE이 나와야 올바르게 짠 코드이다. 지훈이를 먼저 진행시키는 만큼 지훈이가 모서리에 도착하자마자 탈출 성공 처리를 해버리면 탈출이 가능한 잘못된 답이 나오게 된다.

소스 코드

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

char board[1001][1001];
int day[1001][1001];
int R, C;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int bfs() {
    queue<pair<int, int>> Q;

    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (board[i][j] == 'J') Q.push(make_pair(i, j));
        }
    }

    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (board[i][j] == 'F') Q.push(make_pair(i, j));
        }
    }

    while(!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        if (board[cur.first][cur.second] == 'J') {
            if (cur.first == 0 || cur.first == R-1 || cur.second == 0 || cur.second == C-1) {
                return day[cur.first][cur.second];
            }
        }

        for (int i = 0; i < 4; i++) {
            int ny = cur.first + dy[i];
            int nx = cur.second + dx[i];
            if (0 <= ny && ny < R && 0 <= nx && nx < C) {
                if (board[cur.first][cur.second] == 'J') {
                    if (board[ny][nx] != '.') continue;
                    board[ny][nx] = 'J';
                    day[ny][nx] = day[cur.first][cur.second] + 1;
                    Q.push(make_pair(ny, nx));
                } else if (board[cur.first][cur.second] == 'F') {
                    if (board[ny][nx] == 'F' || board[ny][nx] == '#') continue;
                    board[ny][nx] = 'F';
                    Q.push(make_pair(ny, nx));
                }
            }
        }
    }

    return -1;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> R >> C;

    for (int i = 0; i < R; i++) {
        for (int j = 0 ; j < C; j++) {
            cin >> board[i][j];
        }
    }

    int answer = bfs();
    if (answer == -1) cout << "IMPOSSIBLE";
    else cout << answer+1;

    return 0;
}

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

풀이 과정

하루가 지날 때마다 근처에 있는 토마토가 익을 때, 모든 토마토가 익는데 며칠이 걸리는지 구하는 문제이다.

https://ko.wikipedia.org/wiki/%ED%94%8C%EB%9F%AC%EB%93%9C_%ED%95%84

큐로 flood-fill을 구현하는 일종의 bfs 문제이다. board에 토마토가 익는데 걸리는 날짜가 저장되어 있다고 생각하고, flood-fill로 주변 토마토를 익혀가면서 주변 토마토의 board값을 기존 토마토의 board값 + 1을 시켜주면서 모든 토마토를 익힌다.

bfs 과정이 끝나면 board를 다 살펴보면서 0이 있으면 익지 않은 토마토가 존재하므로 -1, 0이 없으면 board의 최댓값의 -1을 답으로 출력해주면 된다. board값이 1로 주어진 토마토는 주어진 즉시, 0일째에 이미 익은 토마토이지만 1일째 익은 것으로 인식되므로 모든 토마토의 익은 날짜가 1씩 더해져 있기 때문 출력 전 -1을 해주는 것이다.

시작점이 여러 곳인 bfs는 그냥 bfs의 시작시에 큐에 여러 점을 넣어주고 돌리면 된다.

소스 코드

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

int board[1001][1001];
int M, N;

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

void bfs() {
    queue<pair<int, int>> Q;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (board[i][j] == 1) Q.push(make_pair(i, j));
        }
    }

    while(!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = cur.second + dx[i];
            int ny = cur.first + dy[i];
            if (0 <= nx && nx < M && 0 <= ny && ny < N) {
                if (board[ny][nx] == 0) {
                    board[ny][nx] = board[cur.first][cur.second] + 1;
                    Q.push(make_pair(ny, nx));
                }
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> M >> N;
    int num;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> num;
            board[i][j] = num;
        }
    }

    bfs();

    int answer = 0;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (board[i][j] == 0) {
                cout << -1;
                return 0;
            }

            if (board[i][j] > answer) {
                answer = board[i][j];
            }
        }
    }

    cout << answer-1;

    return 0;
}

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

풀이 과정

(, ), [, ]로 이루어진 문자열을 보고, 올바른 괄호 문자열인지 판단하고, 맞으면 문제의 조건에 맞게 괄호의 값을 출력하는 문제이다.

올바른 괄호 문자열 판단 자체는 )가 들어오면 스택탑이 (, ]가 들어오면 스택탑이 [인지 판단만 해주면 되는데 괄호의 값을 계산하기가 조금 까다롭다. 

(,나 [가 나오면 정답에 더해질 변수를 (초기값 1)을 문제의 조건에 맞게 2나 3을 곱해주고, )나 ]가 나오면 스택이 아닌 문자열에서 바로 앞에 있는 문자가 뭐였는지에 따라 변수를 정답에 더하고 변수를 나눌지, 아니면 그냥 변수를 나눌지 판단해주어야 한다.

예제로 주어진 문자열에서 정답에 더해질 변수 mul과 정답 변수 ans의 변화는 위의 그림과 같은데, 밑의 문제를 풀기 위한 아이디어와 동일한 아이디어를 사용해 괄호의 값을 구하게 된다.

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

올바른 괄호 문자열 판단의 아이디어, 쇠막대기 문제의 아이디어를 모두 활용해야 하는 문제였다.

소스 코드

#include <iostream>
#include <stack>
#include <string>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    stack<char> st;
    string s;
    cin >> s;

    int ans = 0;
    int mul = 1;

    for (int i = 0; i <= s.length(); i++) {
        if (s[i] == '(') {
            mul *= 2;
            st.push('(');
        } else if (s[i] == '[') {
            mul *= 3;
            st.push('[');
        } else if (s[i] == ']') {
            if (st.empty() || st.top() != '[') {
                cout << 0;
                return 0;
            }

            if (s[i-1] == '[') ans += mul;
            st.pop();
            mul /= 3;
        } else if (s[i] == ')') {
            if (st.empty() || st.top() != '(') {
                cout << 0;
                return 0;
            }

            if (s[i-1] == '(') ans += mul;
            st.pop();
            mul /= 2;
        }
    }

    if (st.empty()) cout << ans;
    else cout << 0;

    return 0;
}

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

풀이 과정

배열에 R(뒤집기), D(첫 번째 수 버리기) 연산을 합쳐서 10만 번 이하로 시행할 때, 배열의 최종 결과를 구하는 문제이다.

배열을 뒤집는 연산은 O(N)이고, 첫 번째 수를 버리는 연산도 O(N)이다. 배열이 아닌 큐를 사용하면 첫번째 수를 버리는 연산을 pop()으로 O(1)만에 수행할 수 있으니 큐로 문제를 풀면 좋을 것 같다는 생각이 든다.

그런데 R을 인식했을 때 실제로 배열을 뒤집으면 시간 초과가 발생한다. 배열에 들어있는 수가 문제에서 주어진 최대 값인 10만 개가 주어졌다고 가정하고, 수행할 함수 p가 길이가 10만이라고 해보자. p가 전부 다 R로 꽉 차있어도 실제로 10만 번 뒤집을 필요까지는 없다. R이 2번 연속으로 나오면 아무 연산을 안 해도 2번 뒤집은 것이랑 같은 결과를 내기 때문이다.

따라서 RDRDRDRDRDRD..... RDRDRDRD 이런 식으로 나와서 R이 50000번 나오는 경우가 가장 시간이 오래 걸리는 경우일 것이다. 10만 크기의 배열을 5만 번 뒤집을 때 연산 횟수를 어림잡아 계산하면 10만 * 5만 = 50억인데, 시간제한 1초 내에 50억 번의 연산을 할 수는 없다.

R이 짝수번 연속으로 나올 때 연산을 무시해서 연산 횟수를 줄여도 시간 내에 문제를 해결할 수 없으니 이 문제를 시간 내에 해결하려면 뒤집기 연산이 나왔을 때 배열을 실제로 뒤집으면 안 된다.

배열이 뒤집힌 상태에서 첫 번째 수 버리기 연산을 하는 것은 배열의 마지막 수를 버리는 연산과 같다. 또한 배열이 뒤집힌 상태이면 배열을 역순으로 출력하고, 뒤집히지 않은 상태일 때 그대로 출력한다면 배열을 뒤집지 않고도 첫 번째 수 버리기 연산과 배열의 출력이 이루어 질 것이다.

따라서 배열이 뒤집혔는지를 판단하는 변수 하나를 두고, 변수의 값에 따라 첫번째 수를 버릴지, 마지막 수를 버릴지, 똑바로 출력할지, 반대로 출력할지를 판단해서 문제를 해결할 수 있다. 첫번째 수, 마지막 수를 O(1)로 버릴 수 있는 자료구조는 덱이므로 덱을 사용해서 문제를 해결하였다.

소스 코드

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while(T--) {
        deque<int> DQ;
        int t = 0;
        bool errorFlag = false;

        string s;
        cin >> s;

        int num;
        cin >> num;

        string numbers;
        cin >> numbers;


        // 문자열 파싱후 덱에 삽입
        int parse_number = 0;
        for (char let : numbers) {
            if (isdigit(let)) {
                int parse = int(let) - 48;
                parse_number = parse_number * 10 + parse;
            } else {
                if (parse_number == 0) continue;
                DQ.push_back(parse_number);
                parse_number = 0;
            }
        }


        for (char let : s) {
            if (let == 'R') {
                t = (t+1) & 1;
            } else if (let == 'D') {
                if (DQ.empty()) {
                    cout << "error\n";
                    errorFlag = true;
                    break;
                }

                if (t == 0) {
                    DQ.pop_front();
                } else {
                    DQ.pop_back();
                }
            }
        }

        if (errorFlag) continue;

        cout << '[';
        int save_size = DQ.size();

        for (int i = 1; i <= save_size; i++) {
            if (t == 0) {
                cout << DQ.front();
                DQ.pop_front();
            } else {
                cout << DQ.back();
                DQ.pop_back();
            }
            if (i == save_size) break;
            cout << ',';
        }

        cout << "]\n";
    }

    return 0;
}

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

풀이 과정

양방향 순환 큐를 회전시키면서 원하는 수를 모두 뽑아내려면 필요한 최소 회전 횟수를 구하는 문제이다.

덱을 회전시키면서 원하는 숫자를 모두 뽑아가면서 회전을 몇번 시켰는지 구하면 된다. 근데 원하는 수가 큐의 앞에 있는 수를 뒤로 넘겨가면서 찾아야 빠른지, 뒤에 있는 수를 앞으로 넘겨가면서 빠른지 어떻게 구분이 가능할까?

판단하려면 일단 찾고자 하는 수가 덱의 몇번째 index에 있는지 알아야 한다. find(DQ.begin(), DQ.end(), num)으로 num이 존재하는 위치의 주소값을 받아오고 거기서 DQ.begin()을 빼서 index를 구해주자.

여기서 구한 index의 2배가 덱의 사이즈보다 작으면 앞에 있는 수를 뒤로 넘기는게 빠르고, 크면 뒤에 있는 수를 앞으로 넘기는게 빠를 것이다. 예시를 들면 0 1 2 3 4 5 6 7 8 9에서 라는 덱에서 4는 4번째 index에 있으므로 4*2 < 10 이므로 앞에서 찾는게 빠를 것이라고 생각할 수 있다.

5는 5번째 index에 있는데, 5*2 < 10이다. index의 2배가 덱의 사이즈랑 같은 경우에는 앞에서 찾던 뒤에서 찾던 횟수의 차이가 없으나, 뒤에서 찾도록 구현하였다.

소스 코드

#include <iostream>
#include <algorithm>
#include <deque>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    deque<int> DQ;

    int N;
    cin >> N;

    for (int i = 1 ; i <= N; i++) {
        DQ.push_back(i);
    }

    int M;
    cin >> M;

    int answer = 0;

    while(M--) {
        int num;
        cin >> num;
        int idx = find(DQ.begin(), DQ.end(), num) - DQ.begin(); // num의 index값
        while (DQ.front() != num) {
            if (2*idx < DQ.size()) {
                DQ.push_back(DQ.front());
                DQ.pop_front();
            } else {
                DQ.push_front(DQ.back());
                DQ.pop_back();
            }
            answer++;
        }
        DQ.pop_front();
    }

    cout << answer;

    return 0;
}

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

풀이 과정

탑이 왼쪽으로 레이저를 쏠 때, 먼저 만나는 높이가 쏜 탑보다 크거나 같은 탑에 레이저가 도달하는데, 각 탑에서 쏜 레이저는 어떤 탑에서 수신하는지 출력하는 문제이다.

스택에 탑의 높이와 인덱스를 넣는다. 다음 건물이 들어왔을 때, 건물의 높이보다 크거나 같은 높이가 나올때 까지 스택 탑의 원소를 비운 후, 스택 탑의 index를 출력하면 그 index의 탑 높이는 입력받은 건물의 높이보다 같거나 클 것이므로 레이저가 도달할 것임을 알 수 있다.

소스 코드

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    stack<pair<int, int>> st;
    st.push(make_pair(100000001, 0));

    int N;
    cin >> N;

    for (int i = 1; i <= N; i++) {
        int num;
        cin >> num;

        while (st.top().first < num) {
            st.pop();
        }

        cout << st.top().second << ' ';

        st.push(make_pair(num, i));
    }

    return 0;
}

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

풀이 과정

알파벳 대문자, 소문자, 숫자, 백스페이스, 화살표를 인식해서 사용자가 입력한 단어가 무엇인지 출력하는 문제이다.

현재 커서의 위치에 따라 알파벳이 추가되는 위치, 삭제되는 위치가 결정된다. 배열로 문자열을 다룬다면 커서의 위치가 문장의 중간일 때 문자의 생성, 삭제 연산이 O(N)이 되어 비효율적인 코드가 된다. 생성, 삭제 연산을 O(1)로 만들어 줘야 한다.

1. 현재 커서의 위치를 2개의 스택으로 표현하기

커서 왼쪽에 있는 문자들을 1번 스택, 커서 오른쪽에 있는 문자들을 2번 스택에 저장한다고 하자. 그렇다면 문자의 삽입은 1번 스택에 push 연산을 해주는 것과 같으므로 O(1), 문자의 삭제는 1번 스택에 pop 연산을 해주는 것과 같으므로 O(1)이다. 화살표 입력시 1번 스택과 2번 스택의 top 요소들을 바꿔가면서 커서 왼쪽 문자, 커서 오른쪽 문자들을 유지해주면 된다.

모든 입력을 받았으면, 2번 스택의 요소들을 1번 스택에 전부 옮기면 모든 문자가 s1에 저장되게 된다. 이를 출력하면 되는데, s1에 있는 것을 그대로 출력시 문자열이 거꾸로 출력되므로 s2에 다시 옮겨담은 후 출력해주어야 원하는 문자열을 얻을 수 있다.

2. 링크드 리스트로 문자열을 표현하기

링크드 리스트에서는 삽입, 삭제 연산이 O(1)에 이루어지므로 효율적으로 커서의 위치에서의 삽입, 삭제 연산을 수행할 수 있다.

소스 코드

스택

#include <iostream>
#include <stack>
#include <string>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while(T--) {
        stack<char> s1;
        stack<char> s2;
        string L;
        cin >> L;
        for (char letter : L) {
            if (letter == '<') {
                if (s1.empty()) continue;
                s2.push(s1.top());
                s1.pop();
            } else if (letter == '>') {
                if (s2.empty()) continue;
                s1.push(s2.top());
                s2.pop();
            } else if (letter == '-') {
                if (s1.empty()) continue;
                s1.pop();
            } else {
                s1.push(letter);
            }
        }

        while(!s2.empty()) {
            s1.push(s2.top());
            s2.pop();
        }

        while(!s1.empty()) {
            s2.push(s1.top());
            s1.pop();
        }

        while(!s2.empty()) {
            cout << s2.top();
            s2.pop();
        }

        cout << '\n';
    }

    return 0;
}

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

풀이 과정

배열에서 두 요소의 합이 x가 되는 경우의 수를 구하는 문제이다.

O(N^2)인 완전 탐색방법으로 풀 수는 있겠지만 배열의 길이가 10만까지 들어오므로 O(N^2)로 처리하면 1초내로 연산이 다 불가능하고 시간 초과가 발생한다.

해결 방법은 크게 2가지가 있다.

1. 투 포인터

배열을 정렬한 뒤, left, right 포인터를 배열의 시작지점, 끝부분에 위치시킨다. 그 후 배열의 left번째 index의 원소 + right번째 index의 원소를 x와 비교한 후, x보다 작으면 left를 전진, 0보다 크면 right를 후진, x와 같으면 left, right를 전진, 후진 시킨 뒤 정답을 1 늘려주면 된다.

2. 배열로 자연수 존재 여부 판단

(x - 배열의 원소) 라는 수가 나온 적이 있는지를 체크하는 배열을 두고, 등장한 적이 있으면 합해서 x가 되므로 답의 개수를 하나씩 늘리면 된다.

소스 코드

#include <iostream>
#include <algorithm>
using namespace std;
int a[100005];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int x;
    cin >> x;

    sort(a, a+n);

    int left = 0;
    int right = n-1;
    int answer = 0;

    while (left < right) {
        int temp = a[left] + a[right];
        if (temp < x) {
            left++;
        } else if (temp > x) {
            right--;
        } else {
            left++; right--;
            answer++;
        }
    }

    cout << answer;

    return 0;
}

배열

#include <iostream>
#include <algorithm>
using namespace std;
int a[100005];
bool exist[2000005];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int x;
    cin >> x;

    int answer = 0;

    for (int i = 0; i < n; i++) {
        if (x-a[i] > 0 && exist[x-a[i]]) answer++; // 나온 적 있으면 정답 증가
        exist[a[i]] = true; // 나왔다고 처리
    }

    cout << answer;

    return 0;
}

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

풀이 과정

도시와 도시 사이를 오가는 버스의 비용이 주어질 때, 모든 도시의 쌍 (A, B)에 대해 A에서 B로 가는 최소 비용을 구하는 문제이다.

도시는 정점, 버스의 비용은 가중치를 갖는 간선으로 생각하면 하나의 그래프로 모델링할 수 있고, 그래프의 모든 정점의 쌍에 대한 최소 비용을 구하는 문제로 생각할 수 있다.

그래프의 최소 비용 문제에서는 BFS, 다익스트라, 벨만-포드, 플로이드-와샬 알고리즘을 생각해 볼 수 있으며 그중에서 모든 정점의 쌍에 대한 최소 비용은 플로이드-와샬 알고리즘을 사용해서 구할 수 있음이 알려져 있다.

플로이드-와샬 알고리즘을 사용하여 문제를 해결하였다.

소스 코드

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

const int INF = 987654321;
int d[105][105];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    for (int i = 1 ; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            d[i][j] = INF;
        }
    }

    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        d[a][b] = min(d[a][b], c);
    }

    for (int i = 1; i <= n; i++) {
        d[i][i] = 0;
    }

    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (d[i][j] == INF) cout << "0 ";
            else cout << d[i][j] << ' ';
        }
        cout << '\n';
    }

    return 0;
}

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

풀이 과정

컴퓨터와 연결된 네트워크가 주어질 때, 1번 컴퓨터와 네트워크로 연결되어서 웜 바이러스에 걸리게 되는 컴퓨터의 수를 구하는 문제이다.

컴퓨터와 네트워크는 그래프의 정점과 간선으로 모델링 할 수 있고, 1번 정점과 연결된 연결 요소에 포함된 정점의 개수 - 1이 정답이 될 것이다. 연결 요소의 정점의 개수는 DFS 혹은 BFS로 정점들을 탐색하면서 구할 수 있다.

소스 코드

DFS

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

vector<int> E[101];
bool visited[101];
int answer = -1;

void dfs(int x) {
    answer++;
    visited[x] = true;

    for (auto next : E[x]) {
        if (visited[next]) continue;
        dfs(next);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int computer, edge, u, v;
    cin >> computer;
    cin >> edge;

    for (int i = 0; i < edge; i++) {
        cin >> u >> v;
        E[u].push_back(v);
        E[v].push_back(u);
    }

    dfs(1);
    cout << answer << '\n';

    return 0;
}

BFS

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

vector<int> E[101];
bool visit[101];
int answer;

void bfs(int start_x) {
    queue<int> Q;
    Q.push(start_x);
    visit[start_x] = true;

    while(!Q.empty()) {
        int cur = Q.front(); Q.pop();
        for (auto next : E[cur]) {
            if (visit[next]) continue;
            Q.push(next);
            answer++;
            visit[next] = true;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int computer, e, a, b;
    cin >> computer;
    cin >> e;

    for (int i = 0; i < e; i++) {
        cin >> a >> b;
        E[a].push_back(b);
        E[b].push_back(a);
    }

    bfs(1);

    cout << answer << '\n';

    return 0;
}