[백준] 1260번 - DFS와 BFS

1. 문제

 

2. 코드

n, m, v = map(int, input().split())
l_v = [0 for i in range(n+1)]
l = [[0] * (n+1) for i in range(n+1)]

for i in range(m):
    a, b = map(int, input().split())
    l[a][b] = l[b][a] = 1

#print(l)

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

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

dfs(v)
print()
bfs(v)

 

3. 풀이

양방향이기 때문에 matrix를 만들어주었다.

n*n (0 때문에 편의를 위해 (n+1)*(n+1) 로 만듦) 크기의 matrix를 만들어서 이어져 있는 간선은 1로 표시한다.

위의 코드에서 matrix는 l이고, 방문한 정점을 표시하기 위한 list는 l_v이다.

 

dfs와 bfs는 각각 재귀와 큐를 통해 구현할 수 있다.

 

 

[dfs]

dfs의 경우, 재귀를 통해 구현할 수 있다.

우선 현재 방문한 곳은 1로 표시해주고, 해당 방문 정점을 출력해준다.

다음으로 반복문 안에 재귀 함수를 선언함으로 해당 방문 정점(v)와 인접한 곳들을 찾아 재귀함수를 실행해준다.

l_v[i]가 0이고(즉, 방문하지 않았고), l[v][i]가 1이면(즉, 현재 방문 정점인 v와 인접해있으면) i에 대한 재귀함수(dfs)를 수행!

 

[bfs]

bfs의 경우, 큐를 통해 구현할 수 있다.

우선 방문해야 할 정점을 넣을 queue를 선언해주고, v로 초기화를 해준다.

현재 방문한 곳은 0으로 표시해준다(dfs 때문에 다 1로 되어있기 때문에 반대로 0으로 표시. dfs 실행 후, l_v를 다시 0으로 다 초기화 해줬다면 1로 표시해도 된다.)

queue 안에 데이터가 있는 동안 반복한다. 

1) queue에서 pop해서 v에 넣고, 출력한다.

2) 반복문을 실행하여 v와 인접한 정점을 찾아 queue에 append 해준다.

--> l_v[i] 가 1이고(즉, 방문하지 않았고), l[v][i]가 1이면(즉, 현재 방문 정점인 v와 인접해있으면) queue에 넣어주고(다음 방문해야 할 곳으로 넣어주고), 해당 정점은 l_v[i]를 0으로 바꾸어준다. 방문한 것으로 처리하는 것이다.

 

 

 

요약 : 

n에 대한 반복문을 실행하면서 방문하지 않았고, 현재 방문 정점과 인접해있으면

해당 정점에 대한 재귀함수를 수행하는 게 dfs,

해당 정점을 queue에 넣어주는 게 bfs이다.