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

DFS와 BFS 성공

1260번: DFS와 BFS

문제

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

입력

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

출력

 

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

 

내 코드

from collections import deque

N,M,V=map(int,input().split())

edge=[] #edge[점1][점2]로 간선 표현할거임

for _ in range(N+1): #점 개수보다 1개 많게해야 인덱스 그대로 접근가능
    edge.append([False]*(N+1))
    
for _ in range(M): #존재하는 간선을 True로 표현(양방향이라 두번)
    a,b=map(int, input().split())
    edge[a][b]=True
    edge[b][a]=True
    
#DFS, BFS별로 각 점을 방문했는지 여부 체크(T/F).
#인덱스 그대로 접근하기위해 여기서도 점을 N+1개 생성.
dfs_node=[False]*(N+1)
bfs_node=[False]*(N+1)

def dfs(V):
    dfs_node[V]=True
    print(V, end=' ')
    for i in range(1, N+1): #인접한 애를 우선적으로 방문
        if not dfs_node[i] and edge[V][i]:
            dfs(i)
        
def bfs(V):
    deq=deque([V]) #시작점으로 deque 생성.
    bfs_node[V]=True #시작점은 바로 방문처리.
    
    while deq: #deque가 빌 때까지 반복
        V=deq.popleft() #먼저 넣은놈부터 빼야한다
        print(V, end=' ') #빼는 순간 방문처리.
        for i in range(1, N+1): #일단 인접한 애들 넣고보기.
            if not bfs_node[i] and edge[V][i]:
                bfs_node[i]=True #인접한 애들 방문처리
                deq.append(i)
                           
dfs(V)
print()
bfs(V)

 

풀이 및 접근)

- DFS는 재귀를 통해, BFS는 deque(덱)을 이용한 반복문을 통해 구현한다.

- 간선을 edge[한 점][다른 한 점] 꼴로 표현하기 위해 [N+1 * N+1] 개의 리스트를 생성한다. 왜 N+1이냐면 노드의 총 개수가 5개이고 노드번호 5를 표현하려면, 5+1개를 확보해야 edge[5][?] 혹은 edge[?][5]에 접근할 수 있다.

- 문제에서 주어진 간선들을 True 처리해서 그 간선들이 있음을 표현한다.

- DFS, BFS별로 점 리스트를 생성. 여기에서도 위와 같은 이유로 N+1개씩 생성.

- DFS는 시작점으로부터 그냥 무작정 인접한 놈들을 계속 방문한다. 이 때 재귀를 사용한다.

- BFS는 시작점에서 인접한놈들 먼저 다 방문했으면, 그놈들중에 제일 첫놈부터 또 인접한 놈들을 먼저 방문한다.