백준 1260 파이썬 python : DFS와 BFS @@황소처럼 우직하게@@ 탐색순서 주의안하면 시간초과납니다;; 최적화하기.

이 글에서는 dfs와 bfs의 개념을 설명하지 않습니다.

dfs bfs 공부하시구 이 글봐주시면 '최적화' 라는 위대함에 알게됩니다.

오랜만에 복습겸 이 문제를 접하게되었는데, 계속 시간초과가 나는겁니다..

n, m, v = list(map(int, input().split()))

adj = [[0 for i in range(n + 1)] for j in range(n + 1)]

for i in range(m):
    a, b = map(int, input().split())
    adj[a][b] = 1
    adj[b][a] = 1

def dfs(v, hist, adj):
    hist.append(v)
    for i in range(1, n + 1):
        if i not in hist and adj[v][i]:
            hist = dfs(i, hist, adj)
    return hist

def bfs(v, adj):
    q = [v]
    hist = [v]
    while q:
        now = q.pop(0)
        for i in range(1, n + 1):
            if i not in hist and adj[now][i]:
                q.append(i)
                hist.append(i)
    return hist

print(' '.join(map(str, dfs(v, [], adj))))
print(' '.join(map(str, bfs(v, adj))))

1시간 삽질했네요.. ㅠㅠ 해답은 아래 코드입니다.

n, m, v = map(int, input().split())

adj = [[0 for i in range(n + 1)] for j in range(n + 1)]

for i in range(m):
    a, b = map(int, input().split())
    adj[a][b] = 1
    adj[b][a] = 1

def dfs(v, hist, adj):
    hist.append(v)
    for i in range(1, n + 1):
        if adj[v][i] and i not in hist:
            hist = dfs(i, hist, adj)
    return hist

def bfs(v, adj):
    q = [v]
    hist = [v]
    while q:
        now = q.pop(0)
        for i in range(1, n + 1):
            if adj[now][i] and i not in hist:
                q.append(i)
                hist.append(i)
    return hist

print(' '.join(map(str, dfs(v, [], adj))))
print(' '.join(map(str, bfs(v, adj))))

차이가 뭔지 보이시나요? ㅋㅋㅋ

if adj[v][i] and i not in hist:

검색 순서입니다. 위 코드가 올바른 순서이고요. 

if i not in hist and adj[v][i]:

위 코드와 같이 쓰면 시간초과가 납니다.

이런 문제에서 세세하게 시간따질줄 몰랐는데;;

하여튼, and 문에 대해서 더 알아볼게요

가령 A and B 일 때, A 가 false 이면 B는 확인하지 않고 넘어갑니다.

바로 이 차이때문에 시간초과가납니다.

최적화할 때, 최대한 A에 false가 많이 발생하는걸로 위치시켜야하는 것이죠.

아 그리고 마지막 출력문은

print(*dfs(v, [], adj))
print(*bfs(v, adj))

이렇게 쓰는게 더 깔끔합니다.

이게 시간초과를 일으키는지 온갖 의심이 들어서 map 쓰고 난리였네요 

--

ps)

10일 뒤 더 깔끔해지고, 시간복잡도도 내려가고, 성장한 코드는 아래 글에 다시 포스팅했습니다.

백준 1260 파이썬 python : DFS와 BFS @@황소처럼 우직하게@@ 깔끔 숏코딩