백준 [1058] "친구"

Kimbab1004·2024년 2월 6일
0

Algorithm

목록 보기
3/102

링크텍스트

A와 B가 친구인 경우는 'Y'값의 갯수만 생각하면 됐지만 A와 B의 친구인 C에서 조금 애를 먹었다. 그래서 친구관계가 'N'인 C의 경우에 A와 B의 경우의 수를 찾는 방식으로 아래와 같이 구현했다.

else if (friends_each[i][j] == 'N') {
				for (int k = 0; k < n; k++) {
					if ((friends_each[i][k]=='Y') && (friends_each[j][k] == 'Y')) {
						two_friend_cnt[i] += 1;
						break;

만약 현재 위치가 'N'일때 i와 j를 연결지어주는 인싸 'K'를 새롭게 만들어 i와 j가 다리건너 친구가 가능한지 검사하였고 만약 가능하다면 i의 인싸력을 1 높여주였다.

#include <iostream>
#include <deque>
#include <string>
#include <sstream>
#include <algorithm>

using namespace std;
#define MAX_N 50

int main(void) {
	
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	string friends_each[MAX_N];
	int two_friend_cnt[MAX_N] = { 0 };

	int n;
	cin >> n;

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

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (i == j) {
				continue;
			}
			else if (friends_each[i][j] == 'Y') {
				two_friend_cnt[i] += 1;
			}
			else if (friends_each[i][j] == 'N') {
				for (int k = 0; k < n; k++) {
					if ((friends_each[i][k]=='Y') && (friends_each[j][k] == 'Y')) {
						two_friend_cnt[i] += 1;
						break;
					}
				}
			}
		}
	}

	int result = *max_element(two_friend_cnt, two_friend_cnt+n);
	cout << result;
		

	return 0;
	}

0개의 댓글