백준 BFS/DFS 문제입니다. 알고리즘 숙달을 위한 문제 반복풀이입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.

문제

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

[나의 풀이1]

⌛ 시간 초과

양방향 그래프 구현이 어려워 해답을 참고하여 구현하였습니다.

def dfs(v):
	
    # 순회한 정점 print
    print(v,end=" ")
    for i in graph[v]:
        if not visitied[i]:
            visitied[i] = True
            # DFS 구현을 위한 재귀함수
            dfs(i)

def bfs(v):

	# queue 활용 bfs 구현
    from collections import deque
    queue = deque([v])

    while queue:
        v = queue.pop()
        print(v,end=" ")
        
        for i in graph[v]:
            if not visitied[i]:
                visitied[i] = True
                queue.appendleft(i)

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

# 그래프 구현
graph = [[] for _ in range(N+1)]
visitied = [False]*(N+1)

# 양방향이기 때문에 연결된 양쪽 정점 모두 append
for _ in range(M):
    a, b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

# 작은 값을 우선으로 돌기 때문에 sort()
for i in range(N+1):
    graph[i].sort()

# 첫 순회 위치 = True
visitied[V] = True
dfs(V)
print()

# visitied list 초기화
for i in range(N+1):
    visitied[i] = False

visitied[V] = True
bfs(V)

양방향 그래프 탐색 구현을 위해 연결된 양쪽 정점 모두 서로의 값을 추가해주는 것이 포인트였습니다. 재귀함수를 통한 DFS 구현과 queue 구조를 활용하여 BFS를 구현하였습니다.

[나의 풀이2]

⌛ 이전 풀이

from collections import deque

def getData():
    
    N, M, V = list(map(int,input().split()))
    graph = [set()for i in range(N+1)]
    for _ in range(1,M+1): # i= 1~5
        connect = list(map(int,input().split()))
        graph[connect[0]].add(connect[1])
        graph[connect[1]].add(connect[0])

    return graph,V
graph,V = getData()
print(graph)

def DFS(graph,V):
    
    DFS_visited = []
    stack = [V]
    
    while stack:
        n = stack.pop()
        if n not in DFS_visited:
            DFS_visited.append(n)
            stack += sorted(list(graph[n] - set(DFS_visited)),reverse=True) 
    return DFS_visited                                                      
                                                                            
DFS_visited = DFS(graph,V)                                                  

def BFS(graph,V):
    
    BFS_visited = []
    queue = deque([V])
    
    while queue:
        n = queue.popleft()
        if n not in BFS_visited:
            BFS_visited.append(n)
            queue += sorted(graph[n] - set(BFS_visited)) 
    return BFS_visited                           
                                                
BFS_visited = BFS(graph,V)

print(*DFS_visited)
print(*BFS_visited)

DFS, BFS 구현 구조는 유사하지만 다음에 방문할 정점들(graph[n])에 set()형태로 바꾸어준 방문한 정점들(visited)를 빼주는 방식으로 방문하지 않은 정점들만 stack(DFS) or queue(BFS) 구조에 더해주는 방식입니다.

감사합니다.