1058-친구

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

1058번: 친구

그래프 탐색 문제이다. 처음에는 아무 생각 없이 DFS 방식으로 접근했는데, 문제의 조건을 보니 BFS로 푸는게 가장 옳은 방법인것 같다. 자신의 기준으로 최대 2단계 레벨에 해당하는 친구들의 수를 세서 비교하는 문제라 한쪽으로 끝까지 파고 들어가는 DFS보단 레벨별로 훑어나가는 BFS의 방식이 딱 알맞다.

 

코드 구성은 BFS에서 최대 2번째 레벨까지만 탐색을 진행하고 카운트를 비교하는 방식. bfs = queue 사용의 공식에 따라 큐를 놓고(코드에선 deque) 탐색을 진행한다.

초기에 주어지는 인접행렬을 받을때 문자열의 형태로 받게 되는데 sys.stdin.readline의 경우 개행문자(\n)까지 받게 되어 이를 제거해 주어야 한다. 입력함수 뒤에 .strip()을 추가하면 된다.

import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
adj = []
for _ in range(N):
    adj.append(list(input().strip()))	# 개행문자 제거

def bfs(start, line):		# 시작위치와 현재 레벨을 입력받는다.
    dq = deque()
    dq.append((start,line))
    chk[start] = 1
    while dq:
        now, nowline = dq.popleft()        
        if nowline == 2:		# 깊이가 2이면 멈춘다.
            continue
        for nxt in range(N):
            if adj[now][nxt] == 'Y' and chk[nxt] == 0:
                chk[nxt] = 1
                dq.append((nxt,nowline+1))

ans = 0
for i in range(N):
    chk = [0] * N
    bfs(i,0)
    ans = max(ans, sum(chk)-1)

print(ans)