[백준/Python] 1260 DFS 와 BFS

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

 

 

사용 알고리즘: DFS, BFS

 

 

문제 제목대로 DFS, BFS 를 구현하면 되는 문제 

 

그래프 표현 방법에는 2가지가 있기 때문에 2가지 방법으로 풀어보았다. 

• 인접행렬(adjacency matrix): 인접성을 행렬(2차원배열/리스트)로 표현
• 인접리스트(adjacency list): 정점에 인접한 에지만을 연결리스트로 표현

 

1. 인접행렬(adjacency matrix) 

 

- 입력

N, M, V = map(int, input().split())
graph = [[0] * (N+1) for _ in range(N+1)]

for _ in range(M):
    a, b = map(int, input().split())
    graph[a][b] = 1
    graph[b][a] = 1

 

 

- dfs

 

visited1 배열은 방문을 표시하는 배열

 

방문 노드와 연결된 노드이고 -> graph[v][i] == 1

방문하지 않았던 노드를 -> visited[i] == 0

방문 -> dfs 호출

visited1 = [0] * (N+1)

def dfs(v):
    visited1[v] = 1
    print(v, end=' ')
    for i in range(1, N+1):
        if graph[v][i] == 1 and visited1[i] == 0:
            dfs(i)

 

 

- bfs

 

큐를 사용 (큐는 FIFO)

 

같은 층에 있는 노드들을 방문하고 큐에 넣음

큐에 넣은 노드를 pop 시키고 그 다음층 노드를 방문하고 큐에 넣음 (이 과정을 반복)

visited2 = [0] * (N+1)

def bfs(v):
    queue = deque()
    queue.append(v)
    visited2[v] = 1

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

        for j in range(1, N+1):
            if graph[x][j] == 1 and visited2[j] == 0:
                visited2[j] = 1
                queue.append(j)

 

 

 

인접행렬을 사용한 전체 코드

from collections import deque
import sys
input = sys.stdin.readline

def dfs(v):
    visited1[v] = 1
    print(v, end=' ')
    for i in range(1, N+1):
        if graph[v][i] == 1 and visited1[i] == 0:
            dfs(i)

def bfs(v):
    queue = deque()
    queue.append(v)
    visited2[v] = 1

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

        for j in range(1, N+1):
            if graph[x][j] == 1 and visited2[j] == 0:
                visited2[j] = 1
                queue.append(j)

# 입력
N, M, V = map(int, input().split())
graph = [[0] * (N+1) for _ in range(N+1)]

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

visited1 = [0] * (N+1)
visited2 = [0] * (N+1)

dfs(V)
print()
bfs(V)

 

 

 

2. 인접리스트(adjacency list)

 

인접리스트로 풀 때는 83% 에서 통과되지 않아 좀 헤맸다. (사실 많이..)

keyerror 가 났는데, keyerror 는 보통 딕셔너리에 없는 값에 접근할 때 나는 에러다.

bfs 함수에서 에러가 났는데, print 해서 확인해보면 graph 에 값이 잘 넣어졌고 테케도 잘 돌아가는데 왜 keyerorr 가 날까 고민을 하다가 해답을 찾았다. 

 

반례1: 노드가 한 개인 경우

 

입력/출력

# 입력
1 0 1

# 출력
1
1

 

반례2: 모든 노드가 연결되어 있지 않은 경우

 

입력/출력

# 입력
4 0 1

# 출력
1
1

 

 

※ 틀렸던 코드 

 

for 문을 돌면서 간선을 보고 graph 에 값을 넣어줌

반례 1, 2 처럼 노드에 연결된 다른 노드가 없는 경우 graph 에 값이 아예 들어가지 않음!!!!

 

bfs 함수는 시작노드로 들어온 노드로 가서 for 문을 돌면서 연결된 노드를 방문하는데,

아래의 테케일 때 graph 에 key 값 자체가 존재하지 않는데 접근했기 때문에 keyerror 가 나게 됨 

• 노드가 한 개인 경우
• 모든 노드가 연결되지 않은 경우

- 입력

N, M, V = map(int, input().split())
graph = {}
for i in range(M):
    a, b = map(int, input().split())
    if a not in graph: # 그래프에 a 라는 key 값이 없을 때
        graph[a] = [b]
    else: # 이미 a 라는 key 값이 존재할 때
        graph[a].append(b)
    if b not in graph: # 그래프에 b 라는 key 값이 없을 때
        graph[b] = [a]
    else: # 이미 b 라는 key 값이 존재할 때
        graph[b].append(a)

# 정렬
for y in graph:
    graph[y].sort()

 

- bfs

def bfs(n):
    queue = deque()
    queue.append(n)

    while queue:
        x = queue.popleft()
        visited2[x] = 1
        print(x, end=' ')

        for v in graph[x]:
            if visited2[v] == 0:
                visited2[v] = 1
                queue.append(v)

 

 

 

올바른 코드

 

graph 에 미리 key 값을 넣어 초기화 시켜줬기 때문에 노드가 한 개이거나 모든 노드가 연결되어 있지 않아도 에러가 나지 않음!!

 

그리고 각 key 의 value 리스트는 꼭 정렬시켜줘야 하는데, 정렬시켜주지 않으면 틀린 답이 나온다.

dfs 나 bfs 는 한 노드에 연결된 노드가 여러 개인 경우 별다른 기준이 없다면 숫자가 가장 빠른(작은) 노드부터 먼저 방문하는게 원칙인데,

정렬시켜주지 않으면 value 리스트에 들어온 순서대로 방문하게 된다. 

 

무슨 말이냐 하면.. 아래의 테케의 경우 정렬시켜 주지 않으면 이렇게 되기 때문에 작은 숫자부터 방문할 수 없다.

graph = {1: [2, 3], 2: [5, 1], 3: [4, 1], 4: [5, 3], 5: [4, 2]} 

5 5 3
5 4
5 2
1 2
3 4
3 1

 

- 입력

graph = {i: [] for i in range(1, N+1)} # 이거 중요!!

for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

# 정렬
for y in graph:
    graph[y].sort()

 

- dfs

def dfs(n):
    visited1[n] = 1
    print(n, end=' ')
    for v in graph[n]:
        if visited1[v] == 0:
            dfs(v)

 

- bfs

def bfs(n):
    queue = deque()
    queue.append(n)
    visited2[n] = 1  

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

        for v in graph[x]:
            if visited2[v] == 0:
                visited2[v] = 1
                queue.append(v)

 

 

인접리스트를 사용한 전체 코드

import sys
from collections import deque

input = sys.stdin.readline

def dfs(n):
    visited1[n] = 1
    print(n, end=' ')
    for v in graph[n]:
        if visited1[v] == 0:
            dfs(v)

def bfs(n):
    queue = deque()
    queue.append(n)
    visited2[n] = 1

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

        for v in graph[x]:
            if visited2[v] == 0:
                visited2[v] = 1
                queue.append(v)

# 입력
N, M, V = map(int, input().split())
graph = {i: [] for i in range(1, N+1)}

for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

# 정렬
for y in graph:
    graph[y].sort()

visited1 = [0] * (N+1) # dfs 가 사용
visited2 = [0] * (N+1) # bfs 가 사용

print(graph)
dfs(V)
print()
bfs(V)