[C++] SWEA 1238 - Contact

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15B1cKAKwCFAYD

SW Expert Academy

<풀이>

1. 입력으로 주어지는 데이터를 배열로 만든다.

2. 배열을 탐색하며 방문 배열에 연락을 몇 번 거쳤는지를 저장한다.

3. 가장 많은 연락을 거친 사람 중 숫자가 가장 큰 사람을 출력한다.

​

<해법>

1. 입력으로 주어지는 데이터를 배열로 만드는 방법.

=> 연락하는 사람, 연락받는 사람을 기준으로 나눕니다.

​

2. 방문 배열에 연락이 몇 번 거쳤는지 저장하는 방법.

=> ( 연락 받는 사람의 거친 연락 수 = 연락 하는 사람의 거친 연락 수 + 1 ) 을 저장하는 배열을 만듭니다.

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
 
const int MAX = 101;
 
bool map[MAX][MAX];
int visited[MAX];
 
void bfs(int st) {
    queue<int> q;
    q.push(st);
    visited[st] = 0;
 
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
 
        for (int i = 1; i < MAX; i++) {
            int nxt = i;
            if (map[cur][nxt] && visited[nxt] < 0) {
                q.push(nxt);
                visited[nxt] = visited[cur] + 1;
            }
        }
    }
    return;
}
 
int main() {
 
    int test_case;
    int T;
 
    T = 10;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //사용할 전역변수 초기화
        memset(map, false, sizeof(map));
        memset(visited, -1, sizeof(visited));
 
        int data_cnt, START;
        cin >> data_cnt >> START;
 
        //a->b로 연락 가능
        for (int i = 0; i < data_cnt / 2; i++) {
            int a, b;
            cin >> a >> b;
            map[a][b] = true;
        }
 
        //당번부터 탐색 시작
        bfs(START);
 
        //연락된 사람들 중 숫자가 가장 큰 사람 저장
        int cnt = -1;
        int res = 0;
        for (int i = 0; i < MAX; i++) {
            if (visited[i] >= cnt) {
                cnt = visited[i];
                res = i;
            }
        }
 
        //출력
        cout << "#" << test_case << " " << res << "\n";
    }
}

 

BFS에 대해 알아볼 수 있는 문제였습니다.