[BOJ][python] DOM

최대한 not in 안쓰고 해결하기

 

 

문제

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

 

나의 풀이

처음에는 set을 사용해서 좋아하는 채널에서 싫어하는 채널을 뺐을 때 남아있는 채널이 없으면 -1을 출력하도록 했습니다.
그러나 set의 차집합 연산량이 많아서 주어진 시간안에 해결되지 않았습니다.

그래서 visited를 사용, 이미 방문한 곳을 다시 한번 방문하면 싸이클을 돈다 판단하고 -1을 출력하도록 했습니다.
배열의 접근은 O(1)이므로 연산시간이 그렇게 크지 않습니다.

최대한 not in 방식을 사용하지 않게 하기 위해서 try except 문을 사용한 것이 특징입니다.

import sys

read = lambda: sys.stdin.readline().strip()


if __name__ == "__main__":
    n, m, p = map(int, read().split())
    ch_dict = {}
    visited = [0] * 100001
    for _ in range(n):
        pos, neg = map(int, read().split())
        try:
            ch_dict[neg]
        except:
            ch_dict[neg] = pos

    count = 0
    while True:
        if visited[p] == 1:
            print(-1)
            break
        try:
            visited[p] = 1
            p = ch_dict[p]
        except:
            print(count)
            break
        count += 1

 

다른 분의 풀이

사실 제 풀이는 dfs를 명시 안해줬을 뿐, 구조는 완전히 동일했습니다.
dfs를 명시하고 사용한 코드는 다음과 같습니다.

#dfs 함수
def dfs(start):
    cnt = 0
    visited =set()
    visited.add(start)
    stack = [start]
    while stack:
        v = stack.pop()
        for next_v in adj_graph[v]:
            #순회 하면 -1
            if next_v in visited:
                cnt = -1
                break
            else:
                stack.append(next_v)
                visited.add(next_v)
                cnt +=1
    return cnt 
            
if __name__ == "__main__":
    import sys
    input = sys.stdin.readline

	n, m, p = map(int,input().split())
    #채널 인접
    adj_graph ={i:[] for i in range(1,m+1)}
    for _ in range(n):
        fav, hated = map(int,input().split())
        #어린사람 우선순위 
        if adj_graph[hated]:
            continue
        adj_graph[hated].append(fav)
    print(dfs(p))