알고리즘 분류 : 그래프 이론, 그래프 탐색, 플로이드-워셜
문제
지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람이 친구이거나, A와 친구이고, B와 친구인 C가 존재해야 된다. 여기서 가장 유명한 사람은 2-친구의 수가 가장 많은 사람이다. 가장 유명한 사람의 2-친구의 수를 출력하는 프로그램을 작성하시오.
A와 B가 친구면, B와 A도 친구이고, A와 A는 친구가 아니다.
입력
첫째 줄에 사람의 수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 각 사람이 친구이면 Y, 아니면 N이 주어진다.
출력
첫째 줄에 가장 유명한 사람의 2-친구의 수를 출력한다.
예제입출력
접근
각 사람을 노드로 생각하고 친구의 관계를 간선으로 생각하면 그래프로 볼 수가 있다.
위 문제에서 A가 B의 2-친구가 되려면 A와 B가 친구이거나 A와 친구이고 B와 친구인 C가 필요하다고 되어있다.
이를 그래프로 생각하면 A와 B는 그래프상에서 바로 인접해있거나 하나의 노드를 거쳐서 도달할수 있는 노드이면 2-친구가 되는 것이다.
즉 A-B 이거나 A-C-B 이런 모양의 그래프일때 B와 C는 A의 2-친구가 되는것이다.
접근방식은 이러하다.
- 주어진 입력에 따라서 그래프를 만든다.
- 반복문을 이용해서 각 노드들이 시작노드일때 bfs탐색을 한다.
- bfs 탐색시에는 간선의 가중치를 1로 생각해서 인접한 노드로 가면 +1 한다.
- 시작노드는 가중치가 0이고 인접한 노드는 1이된다.
- 2-친구는 인접하거나 하나의 노드를 거쳐서 도달할수 있는 노드 즉 인접한 노드의 인접노드이다.
- 시작노드에 인접한 노드들을 2-친구로 생각하여 수를 세고, 해당 인접노드에 연결된 노드들도 2-친구로 생각해서 수를 센다.
- 저장한 수를 반환한다.
- 이 과정을 각각의 노드들을 시작점으로 하여 반복해서 이중에 가장큰수를 출력한다.
이 문제조건대로라면 bfs에서 노드를 다 볼 필요도 없다.
시작노드의 가중치를 0으로 하여 queue에 넣어 탐색을 하고, 인접한 노드는 +1을 해서 저장한다.
이 가중치가 2가 되면 2-친구가 아니기 때문에(가중치가 1일때 인접노드의 수를 카운트 하기 때문에 가중치가 2인 노드는 볼필요가 없다)탐색 queue에 넣지 말고 continue를 이용하면 다 탐색할 필요가 없어진다.
아래는 이를 구현한 코드이다.
import sys
from collections import deque
'''입력'''
n = int(sys.stdin.readline())
#그래프 만들기(인덱스가 노드 - 0,1,2....)
graph = [list(map(str,sys.stdin.readline().strip())) for _ in range(n)]
def bfs(start_node,graph):
visited = [False] * len(graph)
need_visited = deque(list())
need_visited.append([start_node,0])
visited[start_node] = True
#간선의 가중치를 1로 생각하고 1,2이면 숫자를 세서 저장할 변수
friend_count = 0
while need_visited:
current_node,current_count = need_visited.pop()
#가중치가 2보다 크면 2-친구가 아님
if current_count >= 2:
continue
#연결된 노드의 갯수가 같기 때문에 반복문을 돌려가면서 처리함
#반복문을 돌면서 탐색을 한 노드가 아니고, Y(친구)이면 count값을 증가시키고 다음 탐색을 위해서 need_visited에 넣음
for i in range(n):
if visited[i] == False and graph[current_node][i] == "Y":
friend_count += 1
visited[i] = True
need_visited.append([i,current_count+1])
return friend_count
#가장 많은 친구수 출력
max = 0
#반복문을 돌면서 각 사람의 2-친구 수를 bfs탐색을 통해서 알아내고, 그중에 최대값을 저장해서 출력함
for i in range(n):
#bfs탐색을 해서 2-친구 수를 찾음
friend = bfs(i,graph)
if max < friend:
max = friend
print(max)결과
처음에 노드의 가중치가 2가 되면 셀 필요가 없는데 >=여기서 =를 빼먹는 바람에 틀렸다.
좀 더 꼼꼼히 확인후에 낼 필요가 있는 것 같다.
