https://www.acmicpc.net/problem/1325
1325번: 효율적인 해킹
첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한
www.acmicpc.net
혼자 힘으로 풀었는가? x
알고리즘 분류
- DFS
- BFS
문제
해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.
이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.
이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한다"를 의미한다. 컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있다.
출력
첫째 줄에, 김지민이 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 출력한다.
BFS/DFS로 풀면되겠네 쉽네
하고 풀러 들어가면 '시간초과' 를 보게 된다.
시간초과 코드
import sys input = sys.stdin.readline n, m = map(int, input().split()) data = [ [0]for _ in range(n+1)] for _ in range(m): a, b = map(int, input().split()) data[b].append(a) cnt = [0] * (n+1) from collections import deque def bfs(n): q = deque() q.append(n) visited[n] = 1 cnt = 0 while q: now = q.popleft() size = len(data[now]) if size != 0: cnt += size-1 for i in range(1, size): if visited[data[now][i]] == 0: q.append(data[now][i]) visited[now] = 1 return cnt for i in range(1, n+1): visited = [0] * (n+1) cnt[i] = bfs(i) k = max(cnt) for i in range(1, n+1): if k == cnt[i]: print(i, end=' ')
정답 코드 (PyPy3 제출)
import sys input = sys.stdin.readline n, m = map(int, input().split()) data = [ [] for _ in range(n+1)] cnt = [0] * (n+1) for _ in range(m): a, b = map(int, input().split()) data[b].append(a) from collections import deque def bfs(n): q = deque() q.append(n) visited[n] = 1 while q: now = q.popleft() cnt[n] += 1 for i in data[now]: if visited[i] == 0: visited[i] = 1 q.append(i) result = -1 resultList = [] for i in range(1, n+1): visited = [0] * (n+1) bfs(i) if cnt[i] > result: resultList = [] result = cnt[i] resultList.append(i) elif cnt[i] == result: resultList.append(i) for i in resultList: print(i, end=' ')
솔직히.. 큰 차이는 없어 보이는데...
최대 값을 찾는 과정에서 배열에 계속 쌓아서 다시 찾는 것과 초기화하며 최대 값만 넣는 것의 차이라고 볼 수 있다.
'Algorithm > 백준' 카테고리의 다른 글
[Python] 백준 1080번 - 행렬 (실버 1) (0) | 2023.09.22 |
---|---|
[Python] 백준 2529번 - 부등호 (실버 1) (0) | 2023.09.21 |
[Python] 백준 12852번 - 1로 만들기 2 (실버 1) (0) | 2023.09.21 |
[Python] 백준 6588번 - 골드바흐의 추측 (실버 1) (0) | 2023.09.18 |
[Python] 백준 1926번 - 그림 (실버 1) (0) | 2023.09.18 |
댓글