[백준(Baekjoon)] 1260 DFS와 BFS

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

 

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

 

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

 

입력	출력
4 5 1 1 2 1 3 1 4 2 4 3 4	1 2 4 3 1 2 3 4
5 5 3 5 4 5 2 1 2 3 4 3 1	3 1 2 5 4 3 1 4 2 5
1000 1 1000 999 1000	1000 999 1000 999

---

나의 풀이

[Python(파이썬)]

def dfs(x, check):	
    check[x] = True     # x 노드 방문 표시
    print(x, end=' ')
    for k in glist[x]:  # x 노드와 연결된 아직 방문하지 않은 노드를 재귀호출
        if not check[k]:
            dfs(k, check)

def bfs(x, check):
    queue = deque([x])
    check[x] = True     # x 노드 방문 표시
    while queue:    # 큐가 빌 때까지
        k = queue.popleft()
        print(k, end=' ')
        for y in glist[k]:
            if not check[y]:    # x 노드와 연결된 방문하지 않은 원소들을 큐에 삽입
                queue.append(y)
                check[y] = True

import sys
from collections import deque
input = sys.stdin.readline
v, e, n = map(int, input().split())
glist = [[] for _ in range(v+1)]
vsort = []

for _ in range(e):  # 인접리스트 생성
    i, j = map(int, input().split())
    glist[i].append(j)
    glist[j].append(i)
    vsort.append(i)
    vsort.append(j)

set(vsort)
for i in vsort:     # 간선이 있는 노드만 정렬
    glist[i].sort()

check = [False]*(v+1)
dfs(n, check)
print()
check = [False]*(v+1)
bfs(n, check)

 

 

---

풀이과정

1. 인접리스트 생성
2. DFS 구현
3. BFS 구현

 

DFS와 BFS를 구현하는 방법은 인접행렬, 인접리스트 등 여러가지가 있지만 나는 그 중 인접 리스트를 이용해 DFS, BFS를 구현했다. 

 

1. 인접리스트 생성

입력으로 간선이 연결하는 두 정점의 번호가 주어지기 때문에 인접 리스트를 직접 생성해야 한다. 

※ 인접리스트 생성 시 주의할 점
첫 번째 : 입력으로 주어지는 간선은 양방향이다. 
두 번째 : 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다.

위의 두 가지가 인접리스트 생성할 때 중요하게 생각해야 할 점이다. 저 조건들을 생각하지 않고 구현해서 '틀렸습니다'를 보고 말았다.

위의 주의할 점을 생각하여 코드를 구현해보자.

 

glist = [[] for _ in range(v+1)]
vsort = []

for _ in range(e):  # 인접리스트 생성
    i, j = map(int, input().split())
    glist[i].append(j)
    glist[j].append(i)
    vsort.append(i)
    vsort.append(j)
    
set(vsort)
for i in vsort:     # 간선이 있는 노드만 정렬
    glist[i].sort()

 

1-1. 노드의 개수 + 1 만큼의 이차원 리스트 glist 초기화 ( 0은 비워두고 노드 개수만큼 리스트를 생성하기 위해 v+1)

1-2. 일차원 리스트 vsort 생성 (연결된 간선이 있는 노드 저장하는 리스트, 나중에 정렬하기 위함)

1-3. for문 e(간선의 개수) 만큼 1-[4~6] 반복

1-4. 간선이 연결하는 두 정점의 번호를 입력받아 i, j에 저장

1-5. 인접리스트에 간선 정보 저장

glist[i].append(j)	# 노드 i에 대한 리스트에 j 저장
glist[j].append(i)	# 노드 j에 대한 리스트에 i 저장

 

-> 입력으로 주어지는 간선은 양방향이기 때문에 각 각 저장을 해줘야한다. 

1-6. vsort에 i, j 저장

1-7. vsort를 집합으로 변환 -> 여러번 저장된 노드를 한 번만 저장하기 위함

1-8. 간선의 정보를 가지고 있는 노드에 대한 리스트 정렬 -> 방문할 수 있는 정점이 여러개인 경우 정점의 번호가 작은 것부터 먼저 방문하기 위해 정렬해야한다. 

for i in vsort:     # 간선이 있는 노드만 정렬
    glist[i].sort()

 

※ vsort를 구현한 이유

1부터 노드의 개수만큼 for문 돌려서 glist를 정렬할 수 있었지만 vsort를 구현한 이유는 시간을 줄이기 위함이다. 

정점이 전부 간선으로 연결 된 것은 아니기 때문에 vsort에 간선을 가진 정점을 저장해 두면 그 정점의 리스트만 정렬할 수 있다. 

ex) 1000 1 1000
999 1000이 입력일 때 
1 ~ 1000까지 정렬해야하지만 vsort를 이용하면 999, 1000번의 정점 리스트만 정렬하여 1000번을 2번으로 줄일 수 있다. 

 

 

---

[Algorithm] BFS, DFS (tistory.com)

[Algorithm] BFS, DFS

 

2. DFS 구현

 

DFS는 stack이나 재귀 함수하여 구현 할 수 있다. 

아래 코드는 재귀 함수를 이용하여 구현한 DFS 코드 이다. 

def dfs(x, check):	
    check[x] = True     # x 노드 방문 표시
    print(x, end=' ')
    for k in glist[x]:  # x 노드와 연결된 아직 방문하지 않은 노드를 재귀호출
        if not check[k]:
            dfs(k, check)

 

 

 

3. BFS 구현

 

BFS는 Queue를 이용하여 구현 할 수 있다. 

def bfs(x, check):
    queue = deque([x])
    check[x] = True     # x 노드 방문 표시
    while queue:    # 큐가 빌 때까지
        k = queue.popleft()
        print(k, end=' ')
        for y in glist[k]:
            if not check[y]:    # x 노드와 연결된 방문하지 않은 원소들을 큐에 삽입
                queue.append(y)
                check[y] = True

 

---

문제 출처

1260번: DFS와 BFS