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

문제 )

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

1260번: DFS와 BFS

 

[ 풀이 ]

BFS 와 DFS에 대한 문제이다. DFS와 BFS는 이진트리로 밖에 안해봤었는데 이 문제는 조금 달랐다 .
DFS의 경우 , 만약 Node사이에 연결선이 존재한다면 연결된 Node부터 이어주게 된다.
그러나 BFS의 경우에는 level이 같은 Node들 부터 출력하게 된다. 

- DFS 설명 

https://luz0911.tistory.com/97?category=765468

DFS ( Depth First Search, 깊이 우선 탐색 ) python으로 구현하기

 

- BFS 설명 

https://luz0911.tistory.com/100?category=765468

BFS ( Breath First Search, 너비 우선 탐색 ) python으로 구현하기

 

 

예를 들어 예제 2번의 경우,  그래프는 이런 모양으로 그려질 것이다 

이 문제의 경우 DFS는 깊은 부분부터, 연결선을 이용하여 접근 할것이므로 그림과 같은 경로가 될것이다.

 

또한, bfs는 밑 그림과 같은 경로가 될것 이다. 

DFS는 재귀함수를 이용하고 , BFS는 queue를 이용하여 구해주었다. 

 

 

- python code 

# 재귀함수 이용해서 해결
def DFS(v):
    print(v,end=' ')
    visit[v]=1
    for i in range(1,N+1):
        if visit[i]==0 and road[v][i]==1: # 경로가 연결되어있고, 방문 하지X node이면 
            DFS(i)


# Queue 이용해서 해결
def BFS(v):
    visited=[v] # 방문한 node
    queue=[v] 
    while queue:
        p=queue.pop(0)
        print(p,end=' ')
        for i in range(1,N+1):
            if i not in visited and road[p][i]==1:
                queue.append(i)
                visited.append(i)



N,M,V=map(int,input().split())
visit=[0]*(N+1)     #DFS - 방문한 node인지 알려주는 list ( 방문-1, 방문X-0)

# 경로를 행렬로 만들어 줘야함 N*N 행렬 - 인접행렬 통해 접근 
road=[[0]*(N+1)for i in range(N+1)]
for i in range(M):
    x,y=map(int,input().split())
    road[x][y]=1
    road[y][x]=1

DFS(V)
print()
BFS(V)