[Python] 백준 알고리즘 1260번 : DFS와 BFS

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

1260번: DFS와 BFS

 

 

👩‍💻문제 이해

DFS와 BFS의 결과를 각각 반환하는 것이다.

두 접점의 번호가 주어졌을 때, graph가 어떻게 생겼는지 파악을 하는 것이 문제 풀이의 핵심이다.

 

 

 

👩‍💻 스택과 큐를 이용한 DFS, BFS 알고리즘 구현 : 성공🌈

 

🎯전체 코드

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

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

visit_list1 = [0]*(n+1)
visit_list2 = [0]*(n+1)

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

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

dfs(v)
print()
bfs(v)

 

 

🎯graph 행렬 만들기

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

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 = 4 일때, 초기 graph는 다음과 같다.

 

다음으로 예제 입력이 주어졌을 때의 graph를 살펴보자

(1,2) (1,3) (1,4) (2,4) (3,4) 접점이 주어졌을 때 인접한 노드를 행과 열로 갖는 위치는 1로 표현된 것을 볼 수 있다.

 

 

 

🎯방문 리스트 만들기

BFS 와 DFS는 각각 스택과 큐를 사용해 구현된다.

이 때, 스택 / 큐에 한 번 들어갔던 노드는 다시 들어갈 수 없으므로 방문 리스트를 만들어 해당 노드가 스택 / 큐에 들어갔던 적이 있는지를 확인할 필요가 있다. 

 

visit_list1 = [0]*(n+1)
visit_list2 = [0]*(n+1)

 

예를 들어 n = 4 일 때,

visit_list = [0,0,0,0,0] 의 형태가 되고,

이 때 노드 1이 스택 / 큐에 들어갔던 적이 있다면 

visit_list = [0,1,0,0,0] 이 된다.

 

 

 

🎯DFS함수 구현

# 재귀함수를 사용해 dfs 구현

def dfs(v):
    visit_list1[v] = 1
    # 시작노드를 방문 처리
    
    print(v, end=' ')
    # 방문한 노드 출력
    
    # ex) 반복문을 이용해 v=1 일때, 
    # graph[1][1], graph[1][2], graph[1][3]을 확인해준다.
    # 즉, 1과 연결된 노드를 찾는다.
    
    for i in range(1, n+1):
    	# 아래의 조건식은 1과 인접한 노드 중 방문한 적이 없는 노드를 찾는 것이다.
        if graph[v][i] == 1 and visit_list1[i] == 0:
        	# 만약 1과 인접한 노드 중 방문한 적이 없는 노드가 있다면 재귀함수를 사용해
            # 시작 노드로 만들어줌으로써 방문 처리를 한다.
            dfs(i)

 

 

 

🎯BFS함수 구현

def bfs(v):
	# queue를 사용해 bfs를 구현
    queue = [v]
    visit_list2[v] = 1 
    # 여기까지는 dfs와 같다(방문처리).
    
    # bfs는 큐가 빌 때까지 반복
    while queue:
        v = queue.pop(0) 
        # queue는 선입선출 구조이므로 가장 먼저들어온 0번째 요소부터 뺀다.
		# 삭제한 요소를 v변수로 돌려받음
        
        print(v, end = ' ')
        # queue에서 빠진 수 v를 출력
        
        for i in range(1, n+1):
        	# 예를 들어 v가 1일 때, 
            # 노드 1과 인접한 노드들 중 큐에 방문한 적이 없는 노드가 있다면
            if(visit_list2[i] == 0 and graph[v][i] == 1):
            
            	# 큐에 추가되고, 방문처리를 해준다.
                queue.append(i)
                visit_list2[i] = 1
                
                # 이 때, queue에 값이 들어있다면, while문을 빠져나가지 못하고, 반복문을 실행