[백준] 1260번 - DFS와 BFS (파이썬)

 문제링크

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

1260번: DFS와 BFS

 

나의 풀이

dfs/bfs를 활용한 코드를 풀어보지 않아서 참고자료를 활용해 문제를 훑어보는 시간을 가졌다. 지금은 단순히 그래프를 탐색하는 문제를 풀었지만, 앞으로는 응용문제를 계속 풀어보면서 LG CNS 코테 전까지 bfs, dfs를 정복하는게 목표다. 꼭 dfs/bfs문제는 풀고 나오리라!

bfs, dfs의 정말 간단한 개념) https://didu-story.tistory.com/98?category=902867
내가 참고한 자료 ) https://itholic.github.io/python-bfs-dfs/

[알고리즘] 탐색 알고리즘 DFS, BFS

 

from collections import deque

N,M,V=map(int,input().split())
matrix=[[0]*(N+1) for i in range(N+1)]

for i in range(M):
    a, b = map(int, input().split())
    matrix[a][b] = matrix[b][a] = 1
    
visited = [0] * (N+1)
############입력 형식 외우기############

def dfs(v):
		#시작노드는 방문처리 부터 하고 시작
    visited[v] = 1
    print(v, end=' ')
    for i in range(1, N+1):
				# matrix[v][i] 를 쓰는 이유는 인접행렬 중, visited=0인거 찾는거임
				# 만약 인접행렬이 방문하지 않은 노드라면, 방문해서 dfs재귀로 돌려주기
        if (visited[i]==0 and matrix[v][i]==1):
            dfs(i)

def bfs(v):
    queue = deque([v])
    #문제가 dfs먼저 돌리고 bfs돌리는 것
		#따라서 dfs돌아가면서 방문노드를 1로 바꾸었으니까 여기선 0으로 바꿔주면서 방문
    visited[v] = 0
    
		#방문할 노드를 queue에 넣어주고 이동할건데 여기 queue에 아무것도 없을떄까지 진행
		#시작노드v를 queue에 넣고 시작
    while queue:
        v = queue.popleft()
        print(v, end=' ')
        for i in range(1, N+1):
						#visited가 아직 1이고, 인접행렬이 있다면 방문해줘야하니까 queue에 넣고 방문처리해줌
            if (visited[i]==1 and matrix[v][i]==1):
                queue.append(i)
                visited[i] = 0
                
dfs(V)
print()
bfs(V)