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

👤 친구 (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 크기의 문자 행렬 arr[i][j]
• arr[i][j] == 'Y'는 i번 사람이 j번 사람의 친구라는 뜻
  → 즉, "행이 열의 친구냐?"

💡 2. 2-친구의 조건

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

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

💡 3. 반복문 구조

for i in range(N):        # 기준 사람 i
    for j in range(N):    # i의 2-친구 후보 j
        if i == j:
            continue
        if arr[i][j] == 'Y':       # 직접 친구
            ...
        else:
            for k in range(N):     # 공통 친구 후보 k
                if arr[i][k] == 'Y' and arr[k][j] == 'Y':
                    ...

💡 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일 때 공통 친구 검사

• 직접 친구 아님 (arr[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

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

🔹 k = 2 검사 중

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

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

✅ 전체 코드 (Python 구현)

N = int(input())
arr = []
for i in range(N):
    a = list(input())
    arr.append(a)

max_cnt = 0
for i in range(N):
    cnt = 0

    for j in range(N):
        if i == j:
            continue

        if arr[i][j] == 'Y':
            cnt += 1
            continue

        for k in range(N):
            if arr[i][k] == 'Y' and arr[k][j] == 'Y':
                cnt += 1
                break

    if cnt > max_cnt:
        max_cnt = cnt

print(max_cnt)

🔍 코드 상세 리뷰

🔸 입력 처리

N = int(input())
arr = [list(input()) for _ in range(N)]

• arr[i][j]: i번 사람이 j번 사람과 친구인지 여부 저장
• list(input())으로 문자열을 문자 리스트로 변환하여 저장

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

for i in range(N):
    cnt = 0

• 현재 기준 사람 i의 2-친구 수를 세기 위한 반복문

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

for j in range(N):
    if i == j:
        continue

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

🔸 조건 1 — 직접 친구면 바로 카운트

if arr[i][j] == 'Y':
    cnt += 1
    continue

• i와 j가 직접 친구라면 j는 2-친구로 카운트
• 그리고 바로 continue → 공통 친구 검사 생략

🔸 조건 2 — 공통 친구가 존재하면 2-친구로 간주

for k in range(N):
    if arr[i][k] == 'Y' and arr[k][j] == 'Y':
        cnt += 1
        break

• 공통 친구 k를 찾아 연결되면 1번만 카운트 후 break

🔸 최대값 갱신

if cnt > max_cnt:
    max_cnt = cnt

🔸 최종 출력

print(max_cnt)

✅ 보충 설명

구간	주의점
arr[i][j]	i가 j의 친구인가? (직접 친구)
arr[i][k] and arr[k][j]	공통 친구 k를 통한 간접 연결
continue	직접 친구이면 공통 친구 검사 생략
break	공통 친구는 한 명만 있어도 충분함