[백준] 1325. 효율적인 해킹 (Python)

yuuforest·2023년 9월 3일

python 그래프 탐색 백준 알고리즘

그래프 탐색

목록 보기

5/14

백준 문제 풀이 - 그래프 탐색

📰 문제

문제 확인 🏃

💡 입출력 예제

💬 풀이

🎵 첫번째 풀이

from collections import deque
import sys


input = sys.stdin.readline

N, M = map(int, input().split())        # 컴퓨터의 개수 N, 신뢰 관계 개수 M
computers = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())    # a가 b를 신뢰한다 > b를 해킹하면 a도 해킹할 수 있다.
    computers[b].append(a)


def solution():
    answers = []

    for idx in range(1, N+1):
        answers.append((bfs(idx), idx))

    answers.sort(key=lambda x : (-x[0], x[1]))
    max_ans = answers[0][0]

    for ans in answers:
        if max_ans == ans[0]:
            print(ans[1], end=" ")
        else:
            break


def bfs(start):

    visited = [False] * (N+1)

    queue = deque()
    queue.append(start)
    visited[start] = True

    count = 0

    while queue:
        now = queue.popleft()
        count += 1
        for com in computers[now]:
            if not visited[com]:
                queue.append(com)
                visited[com] = True

    return count


solution()

🎵 두번째 풀이

"다른 분들의 풀이 참고" 위의 코드 보다는 더 적은 for문 사용

from collections import deque
import sys


input = sys.stdin.readline

N, M = map(int, input().split())        # 컴퓨터의 개수 N, 신뢰 관계 개수 M
computers = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())    # a가 b를 신뢰한다 > b를 해킹하면 a도 해킹할 수 있다.
    computers[b].append(a)


def solution():
    answers = []
    max_ans = -1

    for idx in range(1, N+1):
        ans = bfs(idx)
        if max_ans < ans:
            max_ans = ans
            answers.clear()
            answers.append(idx)
        elif max_ans == ans:
            answers.append(idx)

    for a in answers:
        print(a, end = " ")


def bfs(start):

    visited = [False] * (N+1)

    queue = deque()
    queue.append(start)
    visited[start] = True

    count = 0

    while queue:
        now = queue.popleft()
        count += 1
        for com in computers[now]:
            if not visited[com]:
                queue.append(com)
                visited[com] = True

    return count


solution()