[실버 2] 백준 1058 - 친구 (파이썬)

https://www.acmicpc.net/problem/1058

풀이

• 사람 수 N명
• 각 사람이 다른 사람과 친구인지 여부가 Y 또는 N으로 주어짐
• 직접 친구이거나 친구의 친구(2-친구)까지를 포함해 가장 많은 친구 수를 가지는 사람을 찾아 그 수를 출력

접근 방법

• 각 사람을 기준으로 BFS 수행
• 거리가 1 또는 2인 사람 수를 세면 된다 (자기 자신은 제외)
• 각 사람마다 세서 그 중 최대값을 구함

조금 생각해야하는 부분

• dist[j] <= 2이면 2-친구까지 포함
• visit 배열과 dist 배열을 통해 BFS 방문 여부 및 거리 체크

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

N은 사람수 F[i]는 i번째 사람의 친구 관계 문자열을 나타낸다.

visit = [False] * N
dist = [-1] * N
queue = deque()

queue.append(i)
visit[i] = True
dist[i] = 0

BFS 초기화는 visit, 중복 방문 방지를 위해 사용하고, dist는 i번 사람으로부터 각 사람까지의 거리를 나타낸다.

while len(queue) != 0:
    u = queue.popleft()

    for v in range(N):
        if F[u][v] == 'Y' and not visit[v]:
            queue.append(v)
            visit[v] = True
            dist[v] = dist[u] + 1

BFS를 실행하며 u → v로 갈 수 있다면 v를 큐에 추가하고 거리를 갱신한다.

count = 0
for j in range(N):
    if j != i and dist[j] != -1 and dist[j] <= 2:
        count += 1

자기 자신을 제외하고, i로 부터의 거리가 1 또는 2인 사람만 카운트 한다.

코드

# 백준 1058 - 친구
# 분류 : BFS

from collections import deque

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

max_count = 0

for i in range(N) :
    visit = [False] * N
    dist = [-1] * N
    queue = deque()

    queue.append(i)
    visit[i] = True
    dist[i] = 0

    while len(queue) != 0 :
        u = queue.popleft()

        for v in range(N) :
            if F[u][v] == 'Y' and not visit[v] :
                queue.append(v)
                visit[v] = True
                dist[v] = dist[u] + 1

    count = 0
    for j in range(N) :
        if j != i and dist[j] != -1 and dist[j] <= 2 :
            count += 1

    max_count = max(max_count, count)

print(max_count)

다른 접근 방법

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

max_count = 0
for i in range(N) :
    f2 = set()

    for j in range(N) :
        if F[i][j] == 'Y' :
            f2.add(j)

            for k in range(N) :
                if F[j][k] == 'Y' and k != i :
                    f2.add(k)
    
    max_count = max(max_count, len(f2))

print(max_count)