1260번: DFS와 BFS

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

1260번: DFS와 BFS

 

 

 

 

기본적인 DFS와 BFS를 구현하는 문제

재귀를 사용하지 않고 반복문으로만 풀어봤다.

 

* 한 노드에 간선이 여러 개일 경우 값이 낮은 노드부터 오름차순으로 방문한다.

 

 

 

 

1) Input Parsing

first = input().split(' ')

N = int(first[0])	# node의 갯수
M = int(first[1])	# 간선의 갯수
V = int(first[-1])	# 시작 node

lines = {}	# node간 간선을 dictionary로 만든다. (양방향 간선)

for i in range(0, M):	
    l = input().split(' ')	# 간선 input
    node1 = int(l[0])
    node2 = int(l[-1])

    if not node1 in lines:
        lines[node1] = []

    lines[node1].append(node2)

    if not node2 in lines:
        lines[node2] = []

    lines[node2].append(node1)

 

 

 

 

 

2) DFS - 깊이 우선 탐색

 

깊이 우선 탐색은 현재 노드에서 갈 수 있는 방향으로 최대한 깊게 들어간다.

stack을 사용해 구현해야하며, 아래 순서로 이루어진다.

stack

 

1) 시작노드를 stack에 넣는다.

2) stack의 마지막 노드를 방문한다. (방문하지 않았을 경우)

3) 간선이 닿아있는 노드를 모두 stack에 넣는다. (오름차순으로 방문하기 위해 내림차순으로 집어넣는다)

4) 노드에 더이상 방문할 이웃 노드가 없을 경우 pop

5) stack에 남아있는 노드가 없을 때까지 2~4)를 반복한다.

 

 

def DFS():
    visited = []	# 방문 기록을 남겨 재방문하지 않도록 한다
    nodeStack = [V]	# stack을 이용해 방문 순서를 정한다. 최초 시작 node를 넣는다.
    
    for i in lines:
        lines[i].sort(reverse=True)	# DFS에서는 낮은 값 node의 탐색을 먼저 끝내야 한다.

    while nodeStack:	# 방문할 node가 없을 때까지 반복
        current = nodeStack.pop()	
        if not current in visited:	# 방문하지 않았으면 방문
            visited.append(current)
            if not current in lines:	# current에 간선이 없으면 stack에 넣지 않는다.
                continue
            
            nodeStack += lines[current]	# reverse된 node를 stack에 집어 넣는다.
    
    return ' '.join(str(x) for x in visited)	# 출력 형식에 맞춰 반환

 

 

 

 

 

3) BFS - 너비 우선 탐색

같은 depth에 있는 노드를 먼저 방문한다.

queue를 써서 구현한다.

queue

 

 

def BFS():
    visited = [V]
    nodeQueue = deque([V]);	# queue를 이용한다. 
    
    while nodeQueue:	# 방문할 node가 없을 때까지
        current = nodeQueue.popleft()
        if not current in lines:	# node에 간선이 없으면 아무것도 하지 않는다.
            continue
        lines[current].sort()	# 오름차순 방문을 위해 정렬
        for node in lines[current]:
            if not node in visited:	# 방문하지 않았으면 방문
                visited.append(node)
                nodeQueue.append(node)

    return ' '.join(str(x) for x in visited)	# 출력 형식에 맞춰 반환

 

 

 

결과

 

 

 

주의)

1. 간선이 없는 경우를 고려해야 한다. 'if not current in lines'을 체크하지 않을 경우 lines 딕셔너리에 없는 키값으로 접근하기 때문에 런타임 오류가 발생한다.

2. Python 알고리즘 문제에서 Queue를 쓸 때 list를 사용하면 안된다. list의 pop은 인덱스를 하나씩 앞으로 당기는 작업이 들어가기 때문에 효율이 매우 좋지 않다.

from collections import deque를 사용해야한다.