[BOJ] 1260. DFS와 BFS

문제

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

1260번: DFS와 BFS

 

---

 

주요 아이디어

기본적인 DFS, BFS 구현 문제

• 따로 저장하지 말고 방문할 때마다 방문 처리로 출력을 진행해주자
• 문제에 명시되어 있진 않으나 예시를 보고 노드가 오름차순 정렬임을 유추할 수 있음

---

 

코드 구현 (Python 3)

 

def dfs(graph, v, visited):
    visited.append(v)
    print(v, end=' ')

    # 인접 노드 방문
    for adj in graph[v]:
        if adj not in visited:
            dfs(graph, adj, visited)

    return None

 

from collections import deque

def bfs(graph, v):
    queue = deque()
    visited = [] # 방문처리
    queue.append(v)
    visited.append(v)

    while queue:
        now = queue.popleft()
        print(now, end=' ')

        # 인접노드 방문
        for adj in graph[now]:
            if adj not in visited:
                queue.append(adj)
                visited.append(adj)
    
    return None

 

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

# 그래프 먼저 인접 리스트 형태로 구축하기
graph = [[] for _ in range(n+1)]

# 양방향 간선 입력 받기 -> sort 필요함
for _ in range(m):
    s, e = map(int, input().split())
    graph[s].append(e)
    graph[e].append(s)

for i in range(1, n+1):
    graph[i].sort()

dfs(graph.copy(), v, [])
print('')
bfs(graph.copy(), v)

 

---

 

 

제출 결과

---

코드 개선 방안