백준 1260-DFS와 BFS (파이썬)

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

예제 입력 1

4 5 1
1 2
1 3
1 4
2 4
3 4

예제 출력 1

1 2 4 3
1 2 3 4

예제 입력 2

5 5 3
5 4
5 2
1 2
3 4
3 1

예제 출력 2

3 1 2 5 4
3 1 4 2 5

예제 입력 3

1000 1 1000
999 1000

예제 출력 3

1000 999
1000 999

---

시나리오

정점과 양방향 간선이 주어졌고 이를 DFS와 BFS로 탐색한 결과를 출력하라고 했으므로 인접행렬 또는 인접리스트를 먼저 생성한다. 이후 체크리스트를 생성하되 DFS, BFS함수 모두에서 사용해야 하기 때문에 두개를 만들어준다. 이후 탐색을 시작할 정점의 번호 v를 매개변수로 받는 DFS함수와 BFS함수를 정석대로 구현해주면 되겠다.

코드

from collections import deque

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

adj = [[0] * (n + 1) for _ in range(n + 1)]

for _ in range(m):
    v1, v2 = map(int, input().split())
    adj[v1][v2] = adj[v2][v1] = 1

chk_dfs = [0] * (n + 1)
chk_bfs = [0] * (n + 1)


def dfs(now):
    chk_dfs[now] = 1
    print(now, end=' ')
    for nxt in range(1, n + 1):
        if adj[now][nxt] and not chk_dfs[nxt]:
            dfs(nxt)


def bfs(now):
    dq = deque()
    dq.append(now)
    chk_bfs[now] = 1
    while dq:
        poped = dq.popleft()
        print(poped, end=' ')
        now = poped
        for nxt in range(1, n + 1):
            if adj[now][nxt] and not chk_bfs[nxt]:
                dq.append(nxt)
                chk_bfs[nxt] = 1


dfs(v)
print()
bfs(v)

 

피드백

1.체크리스트를 생성하는 코드에서의 실수

#(1)실수한 코드
chk_dfs = chk_bfs = [0] * (n + 1)

#(2)바로잡은 코드
chk_dfs = [0] * (n + 1)
chk_bfs = [0] * (n + 1)

좀더 pythonic하게 짜고싶은 욕심에 (1)처럼 작성했다. 하지만 문제가 있다. int, str등 immutable한 객체는 위처럼 작성해도 무방하나 mutable한 list와 같은 객체는 얕은 복사가 되기 때문에 두 리스트 중 하나의 리스트의 값이 변경되면 나머지 리스트의 값도 변경된다.  

참고

https://brotherstone.tistory.com/33

Python mutable객체와 immutable객체

(+추후 작성할 깊은 복사 관련 포스트 링크)

a = b = c 연산을 했을 때 a,b가 같은 메모리 주소를 가리킬 거라는 생각을 못해 실수했다. 다음부터 주의하도록 하자.

 

2. BFS함수를 구현할 때의 실수

#(1)수정 전
def bfs(now):
    dq = deque()
    dq.append(now)
    while dq:
        poped = dq.popleft()
        if not chk_bfs[poped]:
            print(poped, end=' ')
        chk_bfs[poped] = 1
        now = poped
        for nxt in range(1, n + 1):
            if adj[now][nxt] and not chk_bfs[nxt]:
                dq.append(nxt)
                
#(2)수정 후
def bfs(now):
    dq = deque()
    dq.append(now)
    chk_bfs[now] = 1
    while dq:
        poped = dq.popleft()
        print(poped, end=' ')
        now = poped
        for nxt in range(1, n + 1):
            if adj[now][nxt] and not chk_bfs[nxt]:
                dq.append(nxt)
                chk_bfs[nxt] = 1

지난 번 미로탐색 문제를 풀었을 때 했던 실수와 같은 실수이다.

문제점은 큐를 이용하는 BFS구현할 때 방문표시를 하기 위해 체크리스트의 값을 바꾸는 코드를 큐에 append하는 시점에 삽입하는 것과 큐를 pop하는 시점에 삽입하는 것의 결과를 동일하게 생각한 것이다.

 

결론부터 말하면 append할 때 체크리스트를 갱신하는게 맞다. 그래야 이미 큐에 append된 정점을 재방문해서 다시 append하는 일이 발생하지 않는다.

다르게 설명하자면 큐는 선입선출 구조를 갖기 때문에 가장 최근에 삽입된 요소는 가장 늦게 빠져나간다. 따라서 특정 정점A를 방문하여 그 정보를 큐에 append하면 큐의 가장 뒤에 자리잡게 되고 반복문을 계속 돌면서 앞에 위치한 요소들이 모두 pop될 때까지 큐에 남아있게 된다. 하지만 A의 방문을 여부를 A가 pop이 될 때 True로 바꿔주게 되면 그 전까지는 A가 방문되지 않은 걸로 여겨지기 때문에 A는 다른 정점에 의해 계속해서 방문되고 큐에 삽입될 수 있다. 즉, 이미 방문한 정점의 중복삽입이 기하급수적으로 일어날 수 있다는 말이다. 그렇게 되면 프로그램이 매우 비효율적으로 동작하게 되어 제출했을 때 오답이 발생하거나 실행시간이 쓸데없이 길어질 수 있다.

 

 

실제로 수정 전과 후 코드를 제출했을 때의 시간 차이이다. 둘다 정답처리 되었지만 시간은 3배정도 차이난다.

 

참고

https://www.acmicpc.net/board/view/97218#comment-154789