[백준] 1325번 : 효율적인 해킹 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

1325번: 효율적인 해킹

 

1. 문제 설명

2. 풀이과정

주어진 제한 시간에 비해 N과 M의 크기가 작은 편이므로 시간 복잡도와 관련된 제약은 크지 않은 편이다.

하지만 해당 문제에서 잘 확인해야 할 부분은 신뢰 관계 A, B는 A가 B를 신뢰한다는 것이다.

또한 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터는 신뢰를 가장 많이 받는 컴퓨터이다.

그래프의 노드와 에지를 기준으로 이해하면 A라는 노드에서 탐색 알고리즘으로 방문하는 노드가 B, C라고 하면 B, C는 A에게 신뢰받는 노드가 된다.

해당 부분을 고려해 문제를 해결하면 된다.

 

인접 리스트로 컴퓨터와 신뢰 관계 데이터를 그래프로 표현한다.

신뢰 관계 A, B는 A가 B를 신뢰한다는 것이고 이는 B를 해킹하면 A도 해킹할 수 있다는 것이므로 B 컴퓨터에 같이 해킹 가능한 A 컴퓨터를 노드로 저장한다.

모든 노드를 시작 위치로 하여 각각 BFS 탐색을 진행해 탐색되는 노드의 개수(해킹할 수 있는 컴퓨터 개수)를 저장한다.

탐색 종료 후 각 노드별 해킹 가능한 컴퓨터의 개수 중 최댓값을 구하고 최댓값을 가지는 컴퓨터를 오름차순으로 출력한다.

 

슈도코드

1. N(노드 개수), M(에지 개수) 입력받기
2. graph(그래프 데이터 저장 인접 리스트)
3. for M만큼 반복: graph 인접 리스트에 그래프 데이터 저장
4. BFS 구현하기 BFS(v):
   1. visited 리스트에 현재 노드 방문 기록
   2. queue(큐 자료구조 생성)
   3. queue 자료구조에 시작 노드 삽입
   4. while (큐가 비어 있을 때까지):
      1.  queue에서 현재 노드 데이터 가져오기
      2. for 현재 노드의 연결 노드:
         1. if (연결 노드 중 미 방문 노드):
            1. queue에 연결 노드 삽입
            2. visited 리스트에 노드 방문 기록
   5. visited 리스트에서 방문한 노드의 개수 반환
5. result(정답 리스트, 각 노드별 해킹 가능한 컴퓨터 개수 저장)
6. for i 1 ~ N까지 반복:
   1. visited(방문 여부 저장) 리스트 초기화
   2. BFS(i) 실행 (모든 노드로 BFS 실행)
7. MAX(각 노드별 해킹 가능한 컴퓨터의 개수 중 최댓값)
8. for i 1 ~ N까지 반복:
   1. if (해당 노드의 해킹 가능한 컴퓨터의 개수가 최댓값과 같으면): 해당 노드 번호 출력

반응형

3. 소스코드

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())

graph = [[] for _ in range(N + 1)]
for _ in range(M):
    A, B = map(int, sys.stdin.readline().split())
    graph[B].append(A)

def BFS(v):
    visited[v] = False
    queue = deque()
    queue.append(v)

    while (queue):
        now = queue.popleft()
        for i in graph[now]:
            if (visited[i]):
                queue.append(i)
                visited[i] = False

    return visited.count(False)

result = [0] * (N + 1)
for i in range(1, N + 1):
    visited = [True] * (N + 1)
    result[i] = BFS(i)

MAX = max(result)
for i in range(1, N + 1):
    if (result[i] == MAX):
        print(i, end=' ')