[BOJ_1260] DFS와 BFS

틀린 부분이 있을 경우, 지적해 주시면 감사하겠습니다.

노드, 간선, 시작점을 첫째 줄에 입력 받고

둘째 줄 부터는 간선의 개수만큼 두 정점의 번호를 입력 받습니다.

두 개의 리스트를 생성합니다.

• 연결 정보를 나타낸 2차원 리스트
• 방문 여부를 기록한 1차원 리스트

이 정점을 연결 정보를 인접 행렬(adjacent matrix)로 다음과 같이 나타낼 수 있습니다. 

0	1	2	3	4
1		1	1	1
2	1			1
3	1			1
4	1	1

연결이 되어 있다면 1을 넣어주었습니다.

가장 핵심이 되는 부분은 방문하지 않은 노드면서 연결이 되어있는 노드를 방문해 나가는 것인데

• dfs의 경우 재귀함수를 호출하고
• bfs일 때는 큐에다가 넣어줍니다

from collections import deque

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

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

def dfs(cur):
	visited[cur] = True
	print(cur, end=' ')
	for i in range(1, n+1):
		if not visited[i] and adj[cur][i] == 1:
			dfs(i)

def bfs(start):
	queue = deque([start])
	visited[start] = True
	while queue:
		cur = queue.popleft()
		print(cur, end=' ')
		for i in range(1, n+1):
			if not visited[i] and adj[cur][i] == 1:
				queue.append(i)
				visited[i] = True

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

 

DFS & BFS 중 가장 기본이 되는 문제인데

 

저에게는 쉽지않군요;

 

www.acmicpc.net/problem/1260

1260번: DFS와 BFS