[Python] 1325번: 효율적인 해킹

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

1325번: 효율적인 해킹

시간 제한: 5초

메모리 제한:  256mb

<문제 풀이전 나의 생각>**************************************************

일단 그래프구만, 혹은 DFS가 의심이 된다. 시간 제한도 널널한데, 이거 좀 수상함

간단히 하자면 노드를 탐색하고 가장 많이 연결 되어 있는 노드를 찾으면 될것같

체인 라이트링을 날려서 가장 많이 죽일수 있는애를 찾는것 같음 (여러개인 경우에 오름차순으로 출력하라고 함)

 

 

<문제 푸는중 고민>**********************************************************

처음에는 방향성이 없는 그래프인줄 알았다. BUT 그려보니 방향성이 있다. A B 로 입력이 들어오면 B는 부모, A는 자식이라는 의미이다. 그래서 1,2가 선택이 되는거였구나, 역시 그려보면 답이 나온다.

그럼 방향성이 존재하는 그래프 형태로 구상을 해보자.

 

메모리 초과 발생, BFS 방식으로 노드 탐색 횟수를 체크 하였지만, 메모리 초과 문제가 발생한다.

시도는 좋았던것 같다.

메모리 초과 한 이유를 분석해보자--> 정수형 4byte, 노드개수 10^4....

왜 메모리 초과가 발생한거지?

문자열로 바꿔서 할까

 

3번 연속으로 메모리 초과가 발생한다. 딕셔너리 자료구조를 인접 리스트로 바꾸어도 보았지만 그런다.

눈물이난다 내일 물어봐야 겠다.

 

그리고 visited를 체크할 필요는 없다고 생각한다. 왜냐? 역류할 가능성이 있나...??

 

visited 체크는 맞다, 근데? 계속 시간초과가 발생한다. 일단 지금 새벽 3시 이니, 좀 자고 하자

아래는 틀린 코드이다.

 

내일 DFS로 바꿔서 풀어봐야 겠다. --> 메모리 문제는 해결완료

하지만 시간초과 발생함.... 심지어 다른 분들의 코드도 참고했는데 그것도 시간초과가 남

# 딕셔너리 사용해서 구현한 부분.

import sys#, collections

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

# '1':[] 형태로 들어가게 된다.
N_arr = {i+1:[] for i in range(N)}


# 이제 내용물을 추가해주자
for i in range(M):
    son, mom = map(int, sys.stdin.readline().split())
    N_arr[mom].append(son)


# 탐색연산 횟수를 반환해주는 함수 작성
def check(rootnode):
    # DFS 방식을 구현하면 된다. stack 사용하기
    #frontier=collections.deque([])
    frontier = []
    frontier.append(rootnode)
    cnt = 0
    visited = [False for _ in range(N+1)]    # 방문체크
    visited[rootnode] = True     # 시작노드 True로 바꿔주기
    while(frontier):
        a = frontier.pop()
        
        for n in N_arr[a]:
            if visited[n]:
                continue
            frontier.append(n)
            visited[n] = True
            cnt+=1
    
    return cnt


# 각 노드의 탐색 정보를 가지고 있게 함(탐색 횟수를 -1로 두고, 최곳값을 찾게 구현한다.)
ans_num = []
top = -1
for i in range(1,N+1):
    now = check(i)
    # 탐색횟수가 더 큰게 존재하면 왕을 교체한다.
    if top< now:
        top = now
        ans_num.clear()
        ans_num.append(i)
        
        
    # 동점자 발생시 후보로 넣는다
    elif top == now:
        ans_num.append(i)

# 우승자들 발표
print(*ans_num)

# 메모리 초과가 발생한다 계속....

 

 

<문제를 풀고난뒤 후기>*********************************************************

메모리 초과, 시간초과의 연속이다. --> pypy3로 하니깐 통과 됨...

허탈하다. 

메모리 초과는 내가 bfs,dfs 구현할때 visited 처리를 안해줘서 그런거엿다.

시간초과는 python으로는 안돌아 간다. pypy로 하면 잘 돌아간다.

 

알게된점: *리스트명 이라고 쓰면 안에 있는 요소들 깔끔하게 벗겨서 출력이 가능하다.