[백준][1058] 친구

suhan0304·2023년 11월 5일

백준 최단경로 플로이드워셜

백준

목록 보기

21/53

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

문제

각각 N명의 사람들이 누구와 친구인지 주어진다.
N명의 사람 중 2-친구 수의 최댓값을 찾는 문제
2-친구란? 내 친구의 친구, 즉 거리가 2인 친구(그래프)이다.

입력

첫째 줄, 사람 수 N이 주어진다.
둘째 줄, 사람이 친구이면 Y, 아니면 N이 주어진다.

출력

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

풀이에 앞서

이 문제를 원래는 DFS 방식으로 시작 노드를 기준으로 깊이가 2가 될 때까지 노드를 방문할 수 있는 만큼 방문한 다음 자신을 제외하고 방문한 노드들의 수를 세는 방식으로 구현하려고 했으나, 노드 간 최단 경로를 구하는 경우에는 플로이드-워셜 알고리즘을 이용해 문제를 해결할 수 있을것 같아 해당 방법으로 구현했다.

플루이드-워셜(Floyd-Warshall) 알고리즘

플로이드-워셜 알고리즘이란?

그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘이다. 흔히 최단경로를 구하는 알고리즘으로 알려진 다익스트라 알고리즘은 하나의 정점에서 모든 정점까지의 최단 거리를 구하는 알고리즘이었다면, 플로이드-워셜 알고리즘은 한 번 실행하여 모든 노드 간 최단 경로를 구할 수 있다.

다익스트라 알고리즘을 이용해 푸는 문제도 있으므로 다익스트라 알고리즘에 대해 궁금하다면 해당 문제를 풀어보자.

플로이드-워셜 특징

시간복잡도는 O( $n^3$ )으로 큰 편이지만 입력 값이 어느 정도 제한되어있다면 충분히 사용 가능하다.
다익스트라 알고리즘과는 달리 모든 노드 쌍에 대해 최단 거리를 구하고, 음의 가중치를 가지는 그래프에서도 쓸 수 있다는 것이 특징이다.

플로이드-워셜 과정

모든 노드 간의 최단거리를 구해야 하므로 2차원 인접 행렬을 구성한다. 알고리즘은 다중 반복문으로 구성된다. 라운드마다 각 경로에서 새로운 중간 노드로 사용할 수 있는 노드를 선택하고, 더 짧은 길이를 선택하여 줄이는 과정을 반복한다.

임의의 노드 s부터 e까지 가는데 걸리는 최단거리를 d[s][e]라고 하자.

처음에 d[s][e]의 값은 노드 s와 노드 e가 직접적으로 연결되어 있다면 그 노드의 가중치만큼, 그렇지 않다면 무한(INF)로 초기화한다.
d[s][e]를 구하기 위해서, s와 e 사이의 모든 노드 m에 대해, 현재 d[s][e]에 저장되어 있는 값과, d[s][m]+d[m][e]의 값을 비교한다.
d[s][m]+d[m][e]의 값이 현재의 d[s][e] 값보다 작으면, d[s][e]를 d[s][m]+d[m][e] 의 값으로 업데이트한다.

쉽게 말해 모든 노드를 중간 노드로 사용하여 경로 값을 비교한다

실제 값의 변화를 보고 싶으면 다음 문서를 참고하자.

구현 방법

구현 방법은 3중 for문으로 굉장히 간단하게 구현할 수 있다.

def Floyd_Warshall(d, m, s, e) :
  for(m=1; m<=N; m++)
    for(s=1; s<=N; s++)
      for(e=1; e<=N; e++)
        if (d[s][e] > d[s][m] + d[m][e])
			d[s][e] = d[s][m] + d[m][e];

풀이

따라서 이 문제는 d가 1이거나 2인 경우를 확인하면 된다. 따라서 삼중 for 문을 다음과 같이 구현했다.

for k in range(n):
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            if graph[i][j] == "Y" or (graph[i][k] == "Y" and graph[k][j] == "Y"):
                f[i][j] = 1

여기서 graph가 바로 Y인 경우, 즉 직접 내 친구인 경우이거나 graph[i][k],graph[k][j]가 둘 다 Y인 경우인지를 확인해서 f를 1로 바꿔준다.
해당 반복문을 모두 실행하고 나면 각각의 사람마다 2-친구에 대해 1로 나타낸 리스트가 완성된다.

코드

import sys

n = int(sys.stdin.readline())
graph = [list(sys.stdin.readline().strip()) for _ in range(n)]
f = [[0] * n for _ in range(n)]

for k in range(n):
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            if graph[i][j] == "Y" or (graph[i][k] == "Y" and graph[k][j] == "Y"):
                f[i][j] = 1

ans = 0

for row in f:
    ans = max(ans, sum(row))
print(res)