[Python | 백준] 1260번: DFS와 BFS

1. n, m, v 입력 받기 (띄어쓰기 입력)

n, m, v = map(int, input().split())

N(정점수), M(간선수), V(탐색 시작할 정점 번호)

 

2. 그래프 입력 받기 (노드 연결 정보) - 인접 행렬

graph = [[0] * (n+1) for _ in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    graph[a][b] = graph[b][a] = 1

 

정점 번호와 인덱스 일치시키기 위해 n+1로 초기화

무방향 그래프이므로 graph[a][b] = graph[b][a] = 1

 

** 그래프 출력하기

def print_graph(graph):
    for row in graph[1:]:  # 0번째 행과 열은 사용하지 않음
        print(' '.join(map(str, row[1:])))  # 0번째 열도 사용하지 않음

print_graph(graph)

 

 

참고. 인접 행렬 방식 vs 인접 리스트 방식

https://yesolz.tistory.com/entry/DFSBFS#%EA%B7%B8%EB%9E%98%ED%94%84%EC%9D%98%20%EA%B8%B0%EB%B3%B8%20%EA%B5%AC%EC%A1%B0-1

DFS/BFS | 관련 자료구조, 개념, 구현예제

 

 

3. 방문 정보 저장할 배열

visited1 = [False] * (n+1)
visited2 = visited1.copy()

참고로 copy()는 shallow copy (얕은 복사)

 

4. DFS

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

노드 먼저 방문처리 해주고 바로 프린트,

1부터 n 인덱스 i

v와 i 연결되어있고 & 방문하지 않았다면 - 재귀호출로 DFS (스택 구조)

 

5. BFS

def bfs(v):
    queue = [v]
    visited2[v] = True
    while queue:
        v = queue.pop(0)
        print(v, end=' ')
        for i in range(1, n+1):
            if graph[v][i] == 1 and visited2[i] == False:
                queue.append(i)
                visited2[i] = True

queue에 v 삽입하고 방문처리

큐가 비어있지 않을 때동안 계속 while문 실행

v를 queue에서 빼주고 프린트

1부터 n까지 인덱스 i 에서 

v와 i 연결되어있고 & i 방문하지 않았다면 queue에 i 삽입하고 i도 방문 처리

 

 

전체 풀이

n, m, v = map(int, input().split())

# 그래프 - 노드 연결 정보 (2차원 리스트)
graph = [[0] * (n+1) for _ in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    graph[a][b] = graph[b][a] = 1

# 방문 정보
visited1 = [False] * (n+1)
visited2 = visited1.copy()

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

def bfs(v):
    queue = [v]
    visited2[v] = True
    while queue:
        v = queue.pop(0)
        print(v, end=' ')
        for i in range(1, n+1):
            if graph[v][i] == 1 and visited2[i] == False:
                queue.append(i)
                visited2[i] = True

dfs(v)
print()
bfs(v)

 

 

ref.

https://velog.io/@falling_star3/%EB%B0%B1%EC%A4%80Python-1260%EB%B2%88-DFS%EC%99%80BFS

[백준][Python] 1260번 DFS와 BFS(DFS/BFS 기본 구현 자세히)