[백준(BOJ)] 1325번 : 효율적인 해킹 - PYTHON[파이썬]

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

1325번: 효율적인 해킹

 

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

 

---

 

⊙ 문제 접근 과정

 

일차원 배열이면 충분하다.

 

일차원 배열로 bfs를 돌려서 가장 많이 돌아가는 것을 찾아내면 된다.

방문 여부는 지역변수인 bfs() 함수 안에 넣는다.

별도의 초기화 작업을 피하기 위해서이다.

 

 

---

 

⊙ 문제 풀이

 

import sys
from collections import deque

input = sys.stdin.readline

N, M = map(int, input().split())
arr = [[] for _ in range(N+1)]
result = []
q = deque()
maxCnt = 0

for i in range(M):
    a, b = map(int, input().split())
    arr[b].append(a)

def bfs(x):
    visited = [0 for _ in range(N+1)]
    q.appendleft(x)
    visited[x]=1
    cnt = 1
    while q:
        x=q.popleft()
        for i in arr[x]:
            if visited[i] == 0:
                visited[i] = 1
                cnt +=1
                q.append(i)
    return cnt

for i in range(1,N+1):
    temp = bfs(i)
    if maxCnt == temp:
        result.append(i)
    elif maxCnt < temp:
        maxCnt=temp
        result=[]
        result.append(i)

print(*result)

---

⊙ 결과

 

---

⊙ 마무리

 

 

NONE

 

 

좋아요는 로그인하지 않아도 누를 수 있습니다!