«   2022/09   »
        1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30  
Archives
Today
2
Total
95,993
관리 메뉴

차근차근

[백준 1325] 효율적인 해킹 본문

대학교/Algorithm

[백준 1325] 효율적인 해킹

SWKo 2020. 9. 9. 22:55

0. 제목

  • 백준 1325 효율적인 해킹
  • BOJ 1325 효율적인 해킹
  • 파이썬 1325 효율적인 해킹
  • Python 1325 효율적인 해킹

1. 문제

www.acmicpc.net/problem/1325

 

1325번: 효율적인 해킹

첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한�

www.acmicpc.net


2. 풀이

  • 각 점의 연결 상태를 adj 배열에 나타낸다.
  • bfs 알고리즘을 통해 해킹할 수 있는 컴퓨터의 수를 구한다.
  • 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 출력해야 하므로 max_value의 초기값을 -1로 설정하고 각 점마다 오름차순으로 bfs를 수행한다.
  • max_value보다 bfs 결과 값이 크면 갱신해주고 result 배열에 넣어준다. 만약 bfs 결과 값이 max_value와 같으면 result 배열에 값을 추가해준다.
  • 결과적으로 result가 구해지면 이미 오름차순으로 값들이 담겨 있기 때문에 그대로 출력해주면 된다.

3. 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
from collections import deque
 
n, m = map(int, input().split())
adj = [[] for _ in range(n+1)]
 
for _ in range(m):
    x, y = map(int, input().split())
    adj[y].append(x)
 
 
def bfs(v):
    q = deque([v])
    visited = [False* (n + 1)
    visited[v] = True
    count = 1
    while q:
        v = q.popleft()
        for e in adj[v]:
            if not visited[e]:
                q.append(e)
                visited[e] = True
                count += 1
    return count
 
result = []
max_value = -1
 
for i in range(1, n + 1):
    c = bfs(i)
    if c > max_value:
        result = [i]
        max_value = c
    elif c == max_value:
        result.append(i)
        max_value = c
 
for e in result:
    print(e, end=" ")

 

'대학교 > Algorithm' 카테고리의 다른 글

[백준 12865] 평범한 배낭  (0) 2020.09.11
[백준 1904] 01타일  (0) 2020.09.10
[백준 1325] 효율적인 해킹  (0) 2020.09.09
[백준 1012] 유기농 배추  (0) 2020.09.08
[백준 2606] 바이러스  (0) 2020.09.08
[백준 1697] 숨바꼭질  (0) 2020.09.06
0 Comments
댓글쓰기 폼