글 읽기 - [c++] 놓친 부분이 있는지 확인해주시면 감사하겠습니다!

ymkwon3 3년 전 0

알고리즘을 풀면서 틀리거나 모르겠다 싶은 것은 질문을 참조하면서 모두 해결을 했었습니다.

이번 문제는 이해 자체도 어렵지 않아서 쉽게 풀겠다...라고 생각하였지만

생각보다 시간이 걸리게 되어 이렇게 질문게시판에 처음으로 글을 작성합니다.

아래의 코드 필요한 부분에 주석을 달아두었습니다.

혹시 놓친 부분이 있거나 반례가 있을 시 알려주시면 감사하겠습니다.ㅠㅠ

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

using namespace std;

vector<pair<int, int>> network;
vector<bool> infected(101, false);
int n, m; // 컴퓨터의 수, 쌍을 이루는 수
int a, b; // 쌍을 받기위한 임시 변수

void init()
{
    cin >> n;
    cin >> m;
    for (int i = 0; i < m; i++)
    {
        cin >> a >> b;
        network.push_back(make_pair(a, b));
    }
    sort(network.begin(), network.end()); // 정렬을 통한 바이러스 시작
}

void solve()
{
    int cnt = 0;
    infected[1] = true;
    for (int i = 0; i < m; i++)
    {
        if (infected[network[i].first] && !infected[network[i].second]) // 양방향 검사
        {
            infected[network[i].second] = true;
            cnt++;
        }
        else if (infected[network[i].second] && !infected[network[i].first])
        {
            infected[network[i].first] = true;
            cnt++;
        }
    }
    cout << cnt << "\n";
}

int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    init();
    solve();
    return 0;
}

akwk777 3년 전 1

예외:

1 3

1 4

2 5

3 2

질문자님 코드 : 3

정답 : 4

ymkwon3 3년 전 1

정렬을 함으로써 이 문제를 해결 했다고 생각하고 코드를 다시 짰었는데

문제가 해결된 것이 아니었네요 ㅠㅠㅠㅠㅠ 정말 감사합니다. 덕분에 해결했습니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[c++] 놓친 부분이 있는지 확인해주시면 감사하겠습니다!

ymkwon3 3년 전 0

akwk777 3년 전 1

ymkwon3 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말