문제 설명
각 사람마다 직접 친구와 친구의 친구(2-친구)를 구하고, 2-친구의 수가 가장 많은 사람의 값을 출력하는 문제
예제 입력/출력
•
입력1
5
NYNNN
YNYNN
NYNYN
NNYNY
NNNYN
Plain Text
복사
•
출력1
4
Plain Text
복사
제약 조건
•
문제 풀이
이 문제는 각 사람이 가진 2-친구의 수를 구하고, 가장 많은 사람의 값을 출력하는 그래프 문제이다.
여기서 2-친구란,
•
직접 친구이거나 (1다리 연결)
•
공통 친구를 통해 연결된 사람이다. (2다리 연결)
즉, 어떤 사람이 다른 사람과 직접 연결되어 있거나, 친구를 통해서 연결될 수 있는지 확인하는 문제이다.
접근1 플로이드-워셜 -
먼저, 입력으로 주어진 N × N 크기의 2차원 그래프를 friends 변수에 저장한다.
이때, friends[i][j] == 'Y'이면 직접 친구, 'N'이면 친구가 아님을 의미한다.
또한, 각 사람의 2-친구 관계를 저장할 connected 배열을 선언한다.
•
connected[i][j] == 1이면 i와 j가 2-친구
•
connected[i][j] == 0이면 i와 j가 연결되지 않음
이제 플로이드-워셜 알고리즘을 활용하여 2-친구 관계를 업데이트한다.
1.
i와 j가 직접 친구라면 connected[i][j] = 1로 설정한다.
2.
직접 친구가 아니라면, 어떤 사람 k를 거쳐서 i와 j가 연결될 수 있는지 확인한다.
•
즉, i → k 그리고 k → j가 둘 다 가능하면 i → j도 가능하다.
•
이 경우 connected[i][j] = 1로 갱신한다.
마지막으로, 각 사람의 2-친구 수는 connected 행의 합과 같다.
모든 행의 합 중 가장 큰 값을 출력하면 정답이 된다.
접근2 플로이드-워셜 개선 -
기존 플로이드-워셜 접근법은 모든 에 대해 삼중 반복문을 사용하여 의 시간 복잡도를 가진다.
하지만 이 문제에서는 최단 거리 계산이 아니라, 2-친구 관계만 찾으면 된다.
따라서 불필요한 반복문을 제거하여 로 최적화할 수 있다.
1.
각 사람 i에 대해 직접 친구를 찾는다.
2.
직접 친구 j의 친구 k를 찾아 2-친구를 확장한다.
•
이때 i == k가 아니면서 friends[j][k] == ‘Y’ 이면 i와 k는 2-친구가 된다.
•
단, i와 k가 이미 직접 친구라면 중복으로 세지 않도록 주의한다.
3.
모든 i에 대해 2-친구 개수를 세고, 최댓값을 출력한다.
풀이 코드
접근1 플로이드-워셜 -
# 입력 값 받기
N = int(input())
friends = [list(input()) for _ in range(N)]
# 플로이드-워셜 알고리즘
connected = [[0] * N for _ in range(N)]
for k in range(N):
for i in range(N):
for j in range(N):
if i != j:
if friends[i][j] == 'Y' or (friends[i][k] == 'Y' and friends[k][j] == 'Y'):
connected[i][j] = 1
answer = 0
for row in connected:
answer = max(answer, sum(row))
print(answer)
Python
복사
접근2 플로이드-워셜 개선 -
# 입력 값 받기
N = int(input())
friends = [list(input()) for _ in range(N)]
answer = 0
for i in range(N):
two_friends = set()
for j in range(N):
if friends[i][j] == 'Y': # i와 j가 직접 친구일 때
two_friends.add(j)
for k in range(N):
if friends[j][k] == 'Y' and k != i: # 친구의 친구도 찾기
two_friends.add(k)
answer = max(answer, len(two_friends))
print(answer)
Python
복사
