백준, 효율적인 해킹

백준, 효율적인 해킹

 

🪴 문제 

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

1325번: 효율적인 해킹

 

🪴분류

accepted

 

🪴 풀이

처음 접근 방법은 노드 관계도가 'B를 해킹하면, A도 해킹할 수 있다.'

이므로 종속 관계가 B → A 인 단방향 그래프를 그린다.

예제를 그래프 관계도로 표현하면 다음과 같다.

adj = {
	1: [3], 
    2: [3], 
    3: [4, 5]
    }

 

문제에서 원하는 답을 도출하기 위해서 최종적으로 원하는 그래프 관계도는 다음과 같다.

possible_Hacking = {
	1: [3, 4, 5], 
    2: [3, 4, 5], 
    3: [4, 5]
    }

 

그래서 그냥 바로 그래프 관계도를 탐색하면서 1번 노드 값이 그래프 관계도 key값으로 있으면, 그 길이를 더해주는 방식으로 코드를 짜 제출하니 바로 '틀렸습니다'...

아무래도 양방향으로 종속관계가 성립해 겹치는 노드가 같이 카운트 될 수도 있고 자기 자신이 카운트 될 수도 있는듯하다.

 

결국 중복없이 해킹할 수 있는 모든 노드의 갯수를 탐색하면서 알아내야 하는 문제였다.

 

global hackingCnt, visited

def bfs(node):
    global hackingCnt, visited, adj

    visited[node] = True
    queue = deque([node])

    while(queue):
        curNode = queue.popleft()

        for nextNode in adj[curNode]:
            if not visited[nextNode]:
                visited[nextNode] = True
                hackingCnt += 1
                queue.append(nextNode)

bfs로 방문처리해주며 방문할 수 있는 모든 노드를 방문해주면 해킹 가능한 노드 갯수를 세야 하는 문제!

 

hackingInfo = defaultdict(int)
for node in range(1, N+1):
    hackingCnt = 0
    visited = [False] * (N+1)
    bfs(node)
    hackingInfo[node] = hackingCnt

각 노드마다 해킹 가능한 정보를 담는 hackingInfo 딕셔너리를 생성했다.

 

📜 최종 제출 코드

from collections import deque, defaultdict

N, T = map(int, input().split())

global adj
adj = defaultdict(list)
for _ in range(T):
    a, b = map(int, input().split())
    adj[b].append(a)


# 더이상 해킹 가능한 컴퓨터가 없을 때 까지 탐색 bfs

global hackingCnt, visited

def bfs(node):
    global hackingCnt, visited, adj

    visited[node] = True
    queue = deque([node])

    while(queue):
        curNode = queue.popleft()

        if curNode in adj:
            for nextNode in adj[curNode]:
                if not visited[nextNode]:
                    visited[nextNode] = True
                    hackingCnt += 1
                    queue.append(nextNode)

hackingInfo = defaultdict(int)
for node in range(1, N+1):
    hackingCnt = 0
    visited = [False] * (N+1)
    bfs(node)
    hackingInfo[node] = hackingCnt

sorted_hackingInfo = sorted(hackingInfo.items(), key=lambda x:-x[1])
maxHackingCnt = sorted_hackingInfo[0][1]

result = []
for key, val in sorted_hackingInfo:
    if val == maxHackingCnt:
        result.append(key)
    else:
        break

print(*result, sep=' ')

 

 

🪴 시간복잡도

현재 노드가 이웃한 노드를 가질 때만, for문 돌게 하는 코드를 추가하니 시간이 꽤 줄어들었다.

 

 

🪴 참고한 블로그 글

https://velog.io/@hyuntall/%EB%B0%B1%EC%A4%80-1263%EB%B2%88-%EC%8B%9C%EA%B0%84-%EA%B4%80%EB%A6%AC-%EB%AC%B8%EC%A0%9C-%ED%92%80%EC%9D%B4-%ED%8C%8C%EC%9D%B4%EC%8D%AC

[백준] 1325번: 효율적인 해킹 문제 풀이 파이썬

메모리 초과 문제로 배열을 사용하셨다고 한다.

나는 딕셔너리를 사용했으나, 통과 되었다. 

메모리를 더 줄이고 싶으면 list를 사용하면 될 것 같다.