[#1325] 효율적인 해킹

백준 1325번 효율적인해킹 (silver 1)

대충이해하고 구현해서 메모리초과 되기

---

처음 문제를 보고

• DFS/BFS로 영역구분 문제처럼 풀면 되겠구나!

문제에 대한 오해

• "A가 B를 신뢰하는경우 = B를 해킹하면 A도 해킹할 수 있다" 의 말 의 뜻
  • 내가 오해한 바 : A-B연결된 경우- A를 해킹하면 B 해킹가능(O) & B해킹하면 A 해킹가능 (O)
  • 문제가 뜻한 바 : A-B연결된 경우- A를 해킹하면 B 해킹가능(X) & B해킹하면 A 해킹가능 (O)
• 방향이 있는 그래프인데, 무방향 그래프로 착각한거나 마찬가지다 ㅎㅎ
• 미리 예제를 손으로 시물레이션 돌려보고, 정확히 이해했는지 확인하자

 

첫 풀이

from collections import deque

# 데이터 입력받기
n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m) :
    a, b = map(int, input().split())
    #graph[a].append(b) # 양방향 그래프인 경우
    graph[b].append(a)


total_info = []
def bfs(start) : 
    q = deque([start])
    visited = [False] * (n+1)
    visited[start] = True
    visited_info = [start]
    while(q) : 
        v = q.popleft()
        for _v in graph[v] : 
            if visited[_v] == False :
                q.append(_v)
                visited[_v] = True
                visited_info.append(_v)
    return visited_info

# 모든 노드에 대하여 bfs 실행
for i in range(1, n+1) : 
    total_info.append(bfs(i))

# 가장 길이가 긴 노드들 출력
max_len = -1
max_idx_arr = []
for i, arr in enumerate(total_info) :
    if len(arr) >= max_len :
        max_len = len(arr)
        max_idx_arr.append(i+1)
for v in max_idx_arr :
    print(v, end=' ')

첫풀이 결과

메모리 초과...

메모리 초과는 흔하지 않은데ㅎㅎ

해결에만 중점을 두고 너무 메모리를 남발하면서 짜긴 했다. 

굳이 어떤 노드가 어떤 노드랑 부모관계를 맺는지 기록하지 않고, 수만 count 해도 됐었다. (다짜고나서 깨닫;ㅅ;)

 

 

메모리를 더 효율적으로 사용하게 더 깔끔하게 짜봤다. 

 

 

두번째 풀이 

from collections import deque

# 데이터 입력받기
n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m) :
    a, b = map(int, input().split())
    #graph[a].append(b) # 양방향 그래프인 경우
    graph[b].append(a)


total_info = []
def bfs(start) : 
    q = deque([start])
    visited = [False] * (n+1)
    visited[start] = True
    cnt = 0
    while(q) : 
        v = q.popleft()
        cnt += 1
        for _v in graph[v] : 
            if visited[_v] == False :
                q.append(_v)
                visited[_v] = True
    return cnt


ans = [0 for _ in range(n+1)]
for i in range(1, n+1) :
    ans[i] = bfs(i)

for i in range(1, n+1) :
    if ans[i] == max(ans) :
        print(i, end=' ')

 

통과~!

 

 

느낀점

- 단방향그래프/양방향 그래프 헷갈림 -> 문제를 잘 이해해야지 

- 결과가 뭘 원하는지에 맞춰서 최대한 메모리를 효율적으로