[백준] 1058 - 친구

문제

백준 1058번 친구

 

 

알고리즘

1. 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)

플로이드-워셜 알고리즘이란 가중 그래프에서 최단 경로를 찾는 알고리즘이다. 다익스트라 알고리즘 또한 가중 그래프에서 최단 경로를 찾는 알고리즘이지만, 특정한 두 점 사이의 최단경로를 구하는 반면 플로이드 워셜 알고리즘은 모든 점에서 다른 모든 점까지의 최단 경로를 구하는 알고리즘이다. 

알고리즘의 순서를 간단히 설명하면 다음과 같다.

1. 초기 가중 그래프를 테이블화(graph) 하였을 때, 인접하지 않아 가중치가 없을 경우는 무한대로 표시한다.
2. 한 노드에서 다른 노드까지의 거리는 반복문을 통해 갱신된다. 반복 변수는 노드이며,
   1번 노드를 거쳐갈 경우 모든 거리 테이블의 갱신,
   2번 노드를 거쳐갈 경우 모든 거리 테이블의 갱신..
   의 반복으로 총 n 개의 노드를 중간노드로 거쳐가는 것을 반복하여 최종적으로 모든 노드에 대한 최단 거리 테이블을 완성할 수 있다.
   코드로 작성할 경우, 3번의 반복문에서 행의 index를 나타내는 i, 열의 index를 나타내는 j, 중간 노드를 나타내는 k, 총 3개의 변수를 사용한다. 이때, graph [i][j]와 graph [i][k]+graph [k][j] 중 작은 수를 graph [i][k]의 값으로 할당하게 된다.

점화식을 통해 큰 문제를 작은 문제로 나누어 반복문을 통해 최적 값을 지속적으로 갱신한다는 점에서 DP의 일종이라고 볼 수 있다.

 

2. 너비 우선 탐색(Breadth-First Search, BFS)

너비 우선 탐색은 시작 정점을 방문한 후, 시작 정점에 인접한 모든 정점들을 우선 방문하는 탐색 알고리즘이다. DFS와 다른 점은,  다음번 탐색 노드를 결정하는 방식이다.

알고리즘은 한 노드의 주변 노드를 큐(Queue)에 넣고, 다음 탐색 노드를 큐에서 꺼내어 현 노드의 주변을 모두 탐색 후 다음 깊이로 넘어가는 과정을 거친다.

 

문제 풀이

1. 이 문제는 각 사람의 친구 여부에 대한 2차원 배열이 주어졌을 때, 각 사람에 대해 친구이거나 한 사람 건넜을 때 친구인 사람(2-친구)의 수를 찾고, 2-친구가 가장 많은 사람의 2-친구 수를 찾는 것이 목적이다. 반복문을 통해, 다른 사람이 나의 친구의 친구인지 확인하여 2-친구의 수를 찾을 수 있으며, 구현 시 플로이드-워셜 알고리즘을 사용하게 된다. 다만, 이 문제는 최단 경로의 가중치를 찾는 대신 연결 여부를 표시하므로, 점화식을 변형하여 관계가 형성될 경우 다른 방식으로 표기하였다.

사람 i 와 사람 j가 같지 않고, 친구가 아닌 경우, 다른 사람 k를 통해 i와 k가 친구이고, j와 k가 친구임이 확인된다면 i와 j는 2 친구로 새롭게 표시('2')한다. 이때, '2'가 아닌 'Y'(초기 친구)로 표시할 경우, i와 j가 한 사람이 아닌 두 사람을 건너 친구인 경우도 구분할 수 없으므로 '2'로 따로 표시하였다. 이후 각 사람에 대해 'Y' 혹은 '2'인 경우의 수를 계산하여 가장 큰 값을 출력하였다.

 

2. 문제 해결 이후 다른 사람들의 풀이를 보던 중, BFS로 해결한 방법을 보고 이와 같은 방식으로 다시 풀어보았다.

출처 : https://alpyrithm.tistory.com/102

[알고리즘][Python] 백준(BOJ) 1058 친구_파이썬

 

해당 글에서 푼 방식은, 사람 index와 깊이를 큐에 넣어 깊이가 2 미만, 즉 초기에 주어진 친구이거나 한 사람을 건너 친구인 경우만 친구의 index를 큐에 넣고 친구의 친구를 찾는 것이다. 첫 While문이 실행되었을 때 초기 친구인 모든 사람이 큐에 포함되고, 친구의 친구들을 확인하게 되면서 2-친구의 수를 셀 수 있다. 

해당 풀이에서 깊이는 이런 식으로 표현된다.

• 나 자신 : 0
• 친구 : 1
• 친구의 친구 : 2

이 문제는 친구의 친구를 찾는다는 점에서 플로이드-워셜 알고리즘을 사용할 수도 있다. 그러나 한 친구를 건넌 친구라는 '깊이'의 조건이 존재하고, 친구의 수를 찾는 문제이다. 따라서 BFS를 사용하여 큐에 (index, depth)를 넣고 깊이의 제한을 더 명확히 하면서도, '2차원 배열의 갱신'에 초점을 두는 것이 아니라 '친구의 친구를 찾는 것'의 의미를 직관적으로 표현할 수 있다.

또한 시간적인 측면에서도 플로이드-워셜 알고리즘은 O(n^3)의 시간 복잡도를 가지고, BFS는 O(n^2)의 시간 복잡도를 가지므로, BFS를 사용하는 것이 효율적일 것이다. 

* BFS는 그래프에서 노드의 수 V와 간선의 수 E에 대해 O(V+E) 이다. 하지만 이 문제는 모든 친구와의 관계가 결정되었으므로, 밀집 그래프이다. 따라서 간선의 수가 V(V-1) 이므로, O(n^2)라고 볼 수 있다.

 

첫 번째와 두 번째는 BFS, 세 번째는 플로이드 워셜

시간 복잡도는 BFS 알고리즘이 훨씬 작지만, 구현된 코드에서 중복 탐색되는 관계가 존재하며 n이 50 이하의 값을 가지기 때문에 실제 백준 사이트에서 테스트했을 때는 플로이드 워셜 알고리즘을 사용한 코드가 더 짧은 시간 안에 해결되었다.

 

코드

## 플로이드 워셜 알고리즘

import sys

input = sys.stdin.readline

n = int(input())
board=[list(map(str,input().rstrip())) for _ in range(n)]
for i in range(n):
  for j in range(i, n):
    if i!=j and board[i][j]=='N':
      for k in range(n):
        if board[i][k]==board[k][j]=='Y':
          board[i][j]=board[j][i]='2'

maxv=0
for i in range(n):
  maxv=max(n-board[i].count('N'),maxv)

print(maxv)

 

## BFS 알고리즘

import sys
from collections import deque

input = sys.stdin.readline

n = int(input())
board=[list(map(str,input().rstrip())) for _ in range(n)]

def bfs(i):
  q=deque([(i,0)])
  visited=[False] * n
  visited[i]=True
  counts=0

  while q:
    idx, depth=q.popleft()
    
    if depth>=2:
      continue
    
    for j in range(n):
      if not visited[j] and board[idx][j]=='Y':
        counts+=1
        visited[j]=True
        q.append((j, depth+1))
  return counts
    

maxv=0
for i in range(n):
  maxv=max(bfs(i),maxv)

print(maxv)