(알고리즘 공부점검) [백준 1260번] DFS와 BFS - 파이썬

문제 링크:

 

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

1260번: DFS와 BFS

 

---

풀이 과정:

이 문제는 DFS(깊이 우선 탐색 알고리즘)과 BFS(너비 우선 탐색 알고리즘)의 가장 기초가 되는 문제이다.

DFS에서는 인접 행렬(이웃해 있는 행렬의 값이 모두 일치)을 이용하여, BFS에서는 데크(deque)를 호출해 큐(queue)를 이용하여 문제를 풀었다.

DFS는 스택의 자료 구조와 같다고 말할 수 있는 재귀 함수(자기 자신을 호출하는 함수)를 이용해 문제를 푼다.

BFS는 큐의 자료 구조를 이용해 최단 이동거리 같은 문제에서 자주 쓰인다.

다음 풀이 코드에 있는 함수들은 DFS와 BFS의 기본 메서드 정의 함수인만큼 가장 기초가 되는 함수이다.

이 함수들의 정의를 보면서 DFS와 BFS의 개념에 대해 명확히 알고, 복습해 나가는 것이 이번 나 자신과의 숙제이다.

 

풀이 코드:

 

# 1260번 DFS와 BFS 
from sys import stdin 
from collections import deque 

# 입력받기 
n, m, v = map(int, stdin.readline().split()) 
matrix = [[0] * (n+1) for _ in range(n+1)] 

# 간선이 연결하는 두 정점의 번호를 인접행렬로 변환 
for _ in range(m): 
	data = list(map(int, stdin.readline().split())) 
    matrix[data[0]][data[1]] = 1 
    matrix[data[1]][data[0]] = 1 
    

# dfs 함수 
def dfs(start, visited): 
	visited += [start] 
    for i in range(len(matrix[start])): 
    	if matrix[start][i] == 1 and i not in visited: 
        	dfs(i, visited) 
    return visited 
    
    
# bfs 함수 
def bfs(start): 
	visited = [start] 
	queue = deque([start]) 
    while queue: 
    	n = queue.popleft() 
        for i in range(len(matrix[start])): 
        	if matrix[n][i] == 1 and i not in visited: 
            	visited.append(i) queue.append(i) 
    return visited 
    
# dfs, bfs 출력 
print(*dfs(v, []))
print(*bfs(v))

 

1260번 DFS와 BFS

 

알고리즘 공부 1달 점검

알고리즘을 시작한지 1달이 지났다.

지난 1달 동안 그리디와 구현 문제를 집중적으로 공부하였고, 이제 막 그래프 알고리즘인 DFS와 BFS에 대해 배우기 시작했다.

처음 백준에 입문했던 시기에 나는 하루에 1문제도 혼자서 풀 수 없었고, 답안을 보면서 배우는 등 코린이였다.

현재는 하루에 2문제 이상씩 푸는 것을 목표로 전진해 나가고 있다.

목표를 높게 설정하면 나도 그만큼 크게 성장할 수 있는 것 같다.

지금은 그리디와 간단한 구현 정도는 스스로의 힘으로 해결할 수 있고, 더 많은 알고리즘을 공부하기 위해 시간을 쪼개며 최선을 다하고 있다.

내가 거의 매일 블로그에 올리는 백준 문제들은 2회 이상 반복해서 문제를 푼 것이며, 최소 1회는 혼자 힘으로 처음부터 끝까지 코드를 작성해 내 문제로 만들고 있다.

 

내가 블로그에 백준 문제들을 정리하는 이유는 공부한 것을 복습하며 정리함과 동시에, 많은 사람들에게 코드를 공유해 같이 성장해나가고자 하는 내 바람이 있기 때문이다.

앞으로도 이 마음, 이 다짐 잊지 않고 내 닉네임인 Industriousness(부지런함) 닉값하기 위해 최선을 다해 볼 것이다.

 

항상 찾아와 주시는 구독자분들과 제 코드를 봐주시는 모든 분들께 감사의 말씀을 드립니다.