[백준] 1260 DFS와 BFS (Python 파이썬)

www.acmicpc.net/problem/1260

1260번: DFS와 BFS

문제 설명

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 문제이다.

---

풀이 과정

풀이 ① - 그래프를 인접리스트로 구현

 

graph[a].append(b)의 의미는 a번에 b번을 연결시키는 뜻이다.

즉 1번에 2, 3, 4 가 연결되어 있으면 graph의 1번째 행에 2,3,4를 추가하게 된다.

그리고 문제에서, 번호가 작은것 부터 탐색하라고 했으므로 정렬을 해주어야 한다.

from collections import deque

n, m, v = map(int, input().split())
graph = [[]*(n+1) for _ in range(n+1)]
visited = [False]*(n+1)

for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    graph[a].sort()
    graph[b].sort()

def dfs(graph, visited, v):
    visited[v] = True
    print(v, end=' ')

    for i in range(len(graph[v])):
        if not visited[graph[v][i]]:
            dfs(graph, visited, graph[v][i])

def bfs(graph, visited, v):
    queue = deque()
    queue.append(v)
    visited[v] = False

    while queue:
        cur = queue.popleft()
        print(cur, end=' ')
        for i in range(len(graph[cur])):
            if visited[graph[cur][i]]:
                queue.append(graph[cur][i])
                visited[graph[cur][i]] = False


dfs(graph, visited, v)
print()
bfs(graph, visited, v)

 

풀이 ② - 그래프를 인접행렬로 구현

인접행렬은 알아서 앞에서 부터 탐색하기 때문에 정렬을 할 필요는 없다.

인접리스트에서 graph[a].append(b) 로 구현한 부분을 graph[a][b] = graph[b][a]로 구현하면 된다.

from collections import deque

n,m,v = map(int,input().split())
graph = [[0]*n for _ in range(n)]
visited = [False]*n

for i in range(m):
    a, b = map(int,input().split())
    graph[a-1][b-1] = graph[b-1][a-1] = 1

def DFS(v):
    visited[v] = True
    print(v+1, end=' ')

    for i in range(n):
        if graph[v][i]==1 and not visited[i]:
            DFS(i)

def BFS(start):
    visited[start] = False
    queue = deque()
    queue.append(start)

    while queue:
        v = queue.popleft()
        print(v+1, end=' ')

        for i in range(n):
            if graph[v][i]==1 and visited[i]:
                queue.append(i)
                visited[i]=False

DFS(v-1)
print()
BFS(v-1)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !