백준-1260 DFS와BFS

타마타마·2024년 8월 26일

정리/오답

문제정리노트

목록 보기

4/5

💡문제 분석 요약

DFS, BFS 개념 요약
노드갯수, 간선 수, 시작 노드 를 입력 받은 후 DFS값 출력, BFS 값 출력 하는 문제
정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V
M개의 줄에는 간선이 연결하는 두 정점의 번호

💡알고리즘 설계

DFS 함수와 BFS 함수를 작성
그래프의 처음은 빈 값으로 설정 > 그래프는 0번이 아닌 1번부터 사용한다고 조건에 되어있기 때문
그래프 입력 및 구현
1. 입력 받은 두 수는 서로 연관이 되어 있기 때문에 인접리스트로 구현해줘야 한다.
1. 예를 들어 1 4를 입력 받은 경우, 1번 노드에 4번 노드가 연결되어 있음을 구현하고, 4번 노드에 1번 노드가 연결되어 있음을 구현한다.
  2-1. 이중 리스트의 1번 인덱스에 4를 넣고, 4번 인덱스에 1을 넣는다.
  EX) graph[a].append(b) graph[b].append(a) graph[a].sort() graph[b].sort()
2. DFS BFS 호출

💡코드

# 1. 그래프 생성
# 2. dfs 생성
# 3. bfs 생성
#. dfs 출력 후 bfs 출력

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

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

from collections import deque
def bfs(g, start, visited):

  queue = deque([start])
  visited[start] = True

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

    for i in graph[v]:
      if not visited[i]:
        queue.append(i)
        visited[i] = True



n,m,v = map(int, input().split())
graph = [[] for _ in range(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()



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

print("")

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