[BOJ] 1058 친구

# 1058 친구

def dfs(idx):
    global N
    visited = [True]*N
    visited[idx] = False
    stack = [(idx,0)]
    cnt = -1

    while stack:
        cu_x,both_person = stack.pop()
        for x in range(N):
            if arr[cu_x][x] == 'Y':
                if visited[x] and both_person <= 1:
                    visited[x] = False
                    stack.append((x,both_person+1))
        cnt += 1
    return cnt
N = int(input())

arr = [list(input()) for _ in range(N)]
max_number = 0
for i in range(N):
    temp = dfs(i)
    max_number = max(max_number,temp)

print(max_number)

이 문제는 DFS를 이용해서 풀었다.

 

이 문제에서 2-친구가 되는 경우는 2종류이다.

1. 직접적인 친구인 경우

2. 한 다리를 건너서 친구가 되는 경우

 

총 2가지이다.

 

이것을 구분해주기 위해 both_person이라는 변수로 징검다리 친구가 되는 경우를 찾아줬따.

 

이 변수 없이 진행 시, 연결된 모든 친구들이 출력되기 때문에, 최대 거리가 2이하인 경우만 구분해줄려고 썼다.

 

이 문제를 풀고 난뒤에 대부분의 사람들이 플로이드 와샬로 풀었다는 경우가 많지만,

 

아직 플로이드 와샬 알고리즘에 대해 잘 모르기 때문에 그 방법은 나중에 알고리즘을 배우면 시도 해봐야겠다.