[Baekjoon] 1058번: 친구 (DFS/BFS Silver2) - Python

1. 문제

1058번: 친구

2. 코드

from collections import deque

n = int(input())
friends = [[0 for _ in range(n)] for _ in range(n)]

for i in range(n):
    friend = input()
    for j in range(n):
        if friend[j] == 'Y':
            friends[i][j] = 1

def bfs(start):
    visited = [0] * n
    visited[start] = 1
    queue = deque([(start, 0)])  
    count = 0
    while queue:
        current, distance = queue.popleft()
        if distance >= 2:
            continue
            
        for next in range(n):
            if not visited[next] and friends[current][next]:
                count += 1
                visited[next] = 1
                queue.append((next, distance + 1))  
                
    return count

answer = 0
for start in range(n):
    answer = max(answer, bfs(start))
print(answer)

3. 로직

입력 받기 및 인접 행렬 생성

n = int(input())
friends = [[0 for _ in range(n)] for _ in range(n)]

for i in range(n):
    friend = input()
    for j in range(n):
        if friend[j] == 'Y':
            friends[i][j] = 1

1. friends 라는 2차원 리스트를 생성한다. 노드들 간의 친구 관계를 나타내는 인접 행렬을 저장할 것이다.
2. 노드들 간의 친구 관계를 나타내는 문자열을 입력받는다. 'Y'는 친구이고 'N'은 친구가 아님을 의미한다.
3. 입력받은 문자열을 순회하며 'Y'인 경우 해당 위치의 friends 리스트 값을 1로 설정한다.

모든 노드를 시작점으로 하여 최대 친구 수 구하기

answer = 0
for start in range(n):
    answer = max(answer, bfs(start))

모든 노드를 시작점으로 하여 BFS 탐색을 수행하고, 각 노드에서 얻은 최대 친구 수를 answer 변수에 저장한다.

BFS 수행

def bfs(start):
    visited = [0] * n
    visited[start] = 1
    queue = deque([(start, 0)])
    count = 0
    while queue:
        current, distance = queue.popleft()
        if distance >= 2:
            continue
            
        for next in range(n):
            if not visited[next] and friends[current][next]:
                count += 1
                visited[next] = 1
                queue.append((next, distance + 1))
                
    return count

1. visited 리스트 초기화:

• visited 리스트는 노드를 방문했는지를 체크하는 리스트이다. 처음에는 모든 노드가 방문되지 않은 상태를 나타내기 위해 visited 리스트를 0으로 초기화한다.
• start 노드는 시작 노드이므로 이미 방문한 것으로 처리하기 위해 1로 설정한다.

2. BFS 탐색을 위한 큐 생성:

• 큐에는 (start, 0) 형태의 튜플을 삽입한다. 이 튜플은 현재 노드와 해당 노드까지의 거리를 나타낸다. 처음에는 거리가 0이므로 distance에 0이 설정된다.

3. BFS 탐색 시작: ( 큐가 빌 때까지 반복한다. )

• 큐의 가장 왼쪽에 있는 노드를 꺼내서 현재 노드와 거리 정보를 변수 current, distance에 저장한다.
• 현재 노드와 시작 노드의 distance 가 2 이상인 경우 탐색을 진행하지 않고 다음 노드로 넘어간다. ( 거리가 2 이상인 노드는 더이상 2-친구가 될 수 없음. )

4. 현재 노드와 친구 관계인 노드 탐색:

• 해당 노드가 방문되지 않았고 현재 노드와 친구 관계인 경우에만 다음을 실행한다.
• 친구 수를 증가시킨다.
• 방문한 노드를 체크하기 위해 1로 설정한다.
• 다음 탐색 진행을 위해 다음 노드와 시작 노드까지의 거리가 1 늘어났음을 나타낸다.

  출력

return count

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