[BAEKJOON] 1260 DFS와 BFS

문제

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

입력

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

출력

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

예제 입력 1 복사

4 5 1
1 2
1 3
1 4
2 4
3 4

예제 출력 1 복사

1 2 4 3
1 2 3 4

예제 입력 2 복사

5 5 3
5 4
5 2
1 2
3 4
3 1

예제 출력 2 복사

3 1 2 5 4
3 1 4 2 5

예제 입력 3 복사

1000 1 1000
999 1000

예제 출력 3 복사

1000 999
1000 999

 

---

 

이 문제는 dfs, bfs 기본 문제.

dfs와 bfs를 이해하기 좋은 문제이다.

 

이걸 제일 먼저 풀걸,,,

거저 주는 문제였네...

 

def dfs(mr, v, vi):

    vi[v] = True

    print(v, end=' ')

    for i in mr[v]:

        if not vi[i]:

            dfs(mr, i, vi)

   

def bfs(mr, v, vi):

    que = deque([v])

    vi[v] = True

    while(que):

        _v = que.popleft()

        print(_v, end=' ')

        for i in mr[_v]:

            if not vi[i]:

                que.append(i)

                vi[i] = True

 

dfs와 bfs의 차이는 말 그대로 재귀 + 스택이냐 

큐 사용이냐 차이이다.

 

많이 안풀어봐서 장담은 못하겠지만 아마도.

 

그래서 문제가 요구하는 것처럼 탐색 정점 출력하게 구현하였다.

  

n,m,v = map(int, sys.stdin.readline().split())

# mr = []

# for i in range(n+1):

#     mr.append([])

mr = [[] for i in range(n+1)]

그리고 입력 받은 그래프를 넣을 배열 생성

 

주석한 것과 안한 것은 똑같이 동작하는 코드인데

개인적으로 주석한게 나는 직관적이여서 편하긴 한데

최대한 1줄로 쓸 수 있게 밑에 코드를 익숙해지려고 작성하는 중...

 

for i in range(m):

    t,f = map(int, sys.stdin.readline().split())

    mr[t].append(f)

vi_d = [False] * (n+1)

dfs(mr, v, vi_d)

print()

vi_b = [False] * (n+1)

bfs(mr, v, vi_b)

그리고 이 문제 같은 경우 처음에 작성된 코드는 위와 같았다.

 

근데 알고보니 실수를 2개나 해버린 것...

 

첫번째는 이 문제는 정점 값이 작은 곳부터 방문한다는 것.

* 문제를 잘 읽자...

 

그리고 두번 째는 입력으로 주어지는 간선은 양방향이라는 것...

* 문제를 잘 읽자... 2222

 

for i in range(m):

    t,f = map(int, sys.stdin.readline().split())

    mr[t].append(f)

    mr[f].append(t)

for i in range(len(mr)):

    mr[i].sort()

vi_d = [False] * (n+1)

dfs(mr, v, vi_d)

print()

vi_b = [False] * (n+1)

bfs(mr, v, vi_b)

 

그래서 양방향으로 추가를 하였고 작은 정점부터 접근해야되기 때문에

정렬을 해주었다

 

import sys

from collections import deque

def dfs(mr, v, vi):

    vi[v] = True

    print(v, end=' ')

    for i in mr[v]:

        if not vi[i]:

            dfs(mr, i, vi)

   

def bfs(mr, v, vi):

    que = deque([v])

    vi[v] = True

    while(que):

        _v = que.popleft()

        print(_v, end=' ')

        for i in mr[_v]:

            if not vi[i]:

                que.append(i)

                vi[i] = True

n,m,v = map(int, sys.stdin.readline().split())

# mr = []

# for i in range(n+1):

#     mr.append([])

mr = [[] for i in range(n+1)]

for i in range(m):

    t,f = map(int, sys.stdin.readline().split())

    mr[t].append(f)

    mr[f].append(t)

for i in range(len(mr)):

    mr[i].sort()

vi_d = [False] * (n+1)

dfs(mr, v, vi_d)

print()

vi_b = [False] * (n+1)

bfs(mr, v, vi_b)

.