[백준/1260] DFS와 BFS | 인접 리스트에 그래프 저장하기

알고리즘

 

아래와 같이 그래프의 연결 상태가 주어진다면, 인접 리스트와 인접 행렬 두 가지 방식으로 관계를 정의할 수 있다.

이 문제에서는 인접 리스트를 사용하여 그래프 관계를 정의하겠다.

1 2
1 3
1 4
2 4
3 4

 

[인접리스트를 활용한 그래프 표현]

1. 간선의 개수 만큼 정점의 관계들이 입력 되니까 간선의 수 만큼 for문을 반복.

2. 두 정점을 입력 받아서 연결관계를 표현하기 위해 서로의 리스트에 저장.

 

이때 정점의 정보는 1 ~ n까지의 숫자로 나타나므로, graph의 크기를 n+1만큼 해주어야 한다.

(range 함수는 n-1까지의 수를 반환하니까)

# 그래프 초기화
graph = [[] for _ in range(n+1)]
# 간선의 개수가 m일 때
for _ in range(m) : 
	x, y = map(int, input().split())
        graph[x].append(y)
        graph[y].append(x)

만약 입력이 다음과 같을 때 인접 리스트는 

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

[[], [2, 3], [5, 1], [4, 1], [5, 3], [4, 2]]

이 형태로 저장된다.

따라서 그래프를 정렬해주어야 한다. (문제 조건)

 

[정점을 입력 받아 인접리스트를 통해 그래프를 표현하는 방법]

# 그래프 초기화
graph = [[] for _ in range(n+1)]
# 간선의 개수가 m일 때
for _ in range(m) : 
	x, y = map(int, input().split())
        graph[x].append(y)
        graph[y].append(x)

for i in graph : 
	i.sort()

---

전체 코드

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

n,m,v = map(int, input().split())
# n : 정점, m : 간선
graph = [[] for _ in range(n+1)]

def dfs(v) : 
    visited[v] = True
    dfs_path.append(v)
    
    for i in sorted(graph[v]) : 
        if not visited[i] : 
            dfs(i)
        
def bfs(v) : 
    q = deque()
    q.append(v)
    visited[v] = True
    
    while q : 
        x = q.popleft()
        bfs_path.append(x)
        
        for i in sorted(graph[x]) : 
            if not visited[i] : 
                visited[i] = True
                q.append(i)
            

for _ in range(m) : 
   x, y = map(int, input().split()) 
   graph[x].append(y)
   graph[y].append(x)

# 탐색 루트를 저장해줄 변수
dfs_path = []
bfs_path = []

visited = [False] * (n+1)
dfs(v)
visited = [False] * (n+1)
bfs(v)

print(*dfs_path)
print(*bfs_path)

---

알게된 점

• 인접 리스트로 그래프 표현
• 정점을 방문할 리스트 저장