친구 (BOJ 1058) — 2-친구를 찾아라 C++

👤 친구 (BOJ 1058) — 2-친구를 찾아라

출처: 백준 1058번 문제 - 친구

✅ 문제

지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다.
가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다.
어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람이 친구이거나,
A와 친구이고, B와 친구인 C가 존재해야 된다.

여기서 가장 유명한 사람은 2-친구의 수가 가장 많은 사람이다.
가장 유명한 사람의 2-친구의 수를 출력하는 프로그램을 작성하시오.

A와 B가 친구면, B와 A도 친구이고, A와 A는 친구가 아니다.

입력

첫째 줄에 사람의 수 N이 주어진다.
N은 50보다 작거나 같은 자연수이다.
둘째 줄부터 N개의 줄에 각 사람이 친구이면 Y, 아니면 N이 주어진다.

출력

첫째 줄에 가장 유명한 사람의 2-친구의 수를 출력한다.

✅ 예제 입력과 출력

예제 입력 1

3
NYY
YNY
YYN

예제 출력 1

2

예제 입력 2

3
NNN
NNN
NNN

예제 출력 2

0

예제 입력 3

5
NYNNN
YNYNN
NYNYN
NNYNY
NNNYN

예제 출력 3

4

예제 입력 4

10
NNNNYNNNNN
NNNNYNYYNN
NNNYYYNNNN
NNYNNNNNNN
YYYNNNNNNY
NNYNNNNNYN
NYNNNNNYNN
NYNNNNYNNN
NNNNNYNNNN
NNNNYNNNNN

예제 출력 4

8

예제 입력 5

15
NNNNNNNNNNNNNNY
NNNNNNNNNNNNNNN
NNNNNNNYNNNNNNN
NNNNNNNYNNNNNNY
NNNNNNNNNNNNNNY
NNNNNNNNYNNNNNN
NNNNNNNNNNNNNNN
NNYYNNNNNNNNNNN
NNNNNYNNNNNYNNN
NNNNNNNNNNNNNNY
NNNNNNNNNNNNNNN
NNNNNNNNYNNNNNN
NNNNNNNNNNNNNNN
NNNNNNNNNNNNNNN
YNNYYNNNNYNNNNN

예제 출력 5

6

✅ 아이디어

💡 1. 문제 구조

• 입력은 N x N 크기의 문자 행렬 graph[i][j]
• graph[i][j] == 'Y'는 i번 사람이 j번 사람의 친구라는 뜻
  → 즉, "행이 열의 친구냐?"

💡 2. 2-친구의 조건

사람 i의 2-친구가 되기 위한 조건은 다음 중 하나입니다:

• graph[i][j] == 'Y' → 직접 친구
• graph[i][k] == 'Y' && graph[k][j] == 'Y' → 공통 친구 k가 존재 (i–k–j)

💡 3. 반복문 구조

for (int i = 0; i < N; i++) {      // 기준 사람 i
    for (int j = 0; j < N; j++) {  // i의 2-친구 후보 j
        if (graph[i][j] == 'Y') {
            // 직접 친구
        } else {
            for (int k = 0; k < N; k++) {  // 공통 친구 후보 k
                if (graph[i][k] == 'Y' && graph[k][j] == 'Y') {
                    // k는 공통 친구
                }
            }
        }
    }
}

💡 4. 시각적으로 반복문 흐름 보기

친구 관계 예시 (N = 4):

	0	1	2	3
0	N	Y	Y	N
1	Y	N	Y	N
2	Y	Y	N	N
3	N	N	N	N

예시: i = 0, j = 3일 때 공통 친구 검사

• 직접 친구 아님 (graph[0][3] == 'N')
• 공통 친구를 찾기 위해 k를 0~3까지 순회

🔹 k = 1 검사 중

	0	1	2	3
0	N	Y	Y	N
1	Y	N	Y	N
2	Y	Y	N	N
3	N	N	N	N

graph[0][1] == Y ✅
graph[1][3] == N ❌ → k=1은 공통 친구 아님

🔹 k = 2 검사 중

	0	1	2	3
0	N	Y	Y	N
1	Y	N	Y	N
2	Y	Y	N	N
3	N	N	N	N

graph[0][2] == Y ✅
graph[2][3] == N ❌ → k=2도 공통 친구 아님

💡 5. 핵심 개념 요약

변수	역할
i	2-친구를 세려는 사람
j	i의 2-친구 후보
k	i와 j의 공통 친구 후보
graph[i][j] == 'Y'	i가 j의 친구인가?
graph[i][k] == 'Y' && graph[k][j] == 'Y'	k가 i와 j의 공통 친구인가?

✅ 전체 코드 (C++)

#include <iostream>
using namespace std;

int main() {
    int N;
    char graph[50][51];
    cin >> N;

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

    int maxCount = 0;

    for (int i = 0; i < N; i++) {
        int count = 0;

        for (int j = 0; j < N; j++) {
            if (i == j) continue;

            if (graph[i][j] == 'Y') {
                count++;
                continue;
            }

            for (int k = 0; k < N; k++) {
                if (graph[i][k] == 'Y' && graph[k][j] == 'Y') {
                    count++;
                    break;
                }
            }
        }

        if (count > maxCount) maxCount = count;
    }

    cout << maxCount << '\n';
    return 0;
}

🔍 코드 상세 리뷰

🔸 입력 처리

char graph[50][51];
cin >> N;
for (int i = 0; i < N; i++) {
    cin >> graph[i];
}

• graph[i][j]: i번 사람이 j번 사람과 친구인지 여부 저장
• 각 줄은 문자열 그대로 받아 처리
• graph[i][i]는 항상 'N'이므로 자기 자신과는 친구가 아님

🔸 외부 루프 — 기준 사람 i를 순회

for (int i = 0; i < N; i++) {
    int count = 0;

• 현재 기준 사람 i의 2-친구 수를 세기 위한 반복문
• visited 없이, count만 직접 증가

🔸 내부 루프 — 2-친구 후보 j 검사

for (int j = 0; j < N; j++) {
    if (i == j) continue;

• j는 i와 같은 사람이 아니어야 하므로 continue
• i ≠ j인 모든 j에 대해 2-친구 조건을 검사

🔸 조건 1 — 직접 친구면 바로 2-친구

if (graph[i][j] == 'Y') {
    count++;
    continue;
}

• i와 j가 직접 친구라면 j는 2-친구
• 그리고 바로 continue → 공통 친구 검사는 생략됨
• 중복 방지 완벽히 처리됨

🔸 조건 2 — 공통 친구 탐색

for (int k = 0; k < N; k++) {
    if (graph[i][k] == 'Y' && graph[k][j] == 'Y') {
        count++;
        break;
    }
}

• k는 공통 친구 후보
• 공통 친구를 찾으면 break로 중복 방지 → j는 한 번만 카운트됨

🔸 최댓값 갱신

if (count > maxCount) maxCount = count;

• i번 사람의 2-친구 수를 전체 최대값과 비교해 갱신

🔸 출력

cout << maxCount << '\n';

• 가장 유명한 사람의 2-친구 수를 출력

✅ 보충 설명

구간	주의점
graph[i][j]	"i가 j의 친구인가?" → 행이 열의 친구냐
graph[i][k] && graph[k][j]	공통 친구 k를 통한 간접 연결
continue	직접 친구일 경우, 공통 친구 검사 생략
break	공통 친구는 한 명만 있어도 충분하므로 빠르게 탈출