[Baekjoon] 1260_DFS와 BFS

Silver II

문제(출처: https://www.acmicpc.net/problem/1260)

---

<DFS와 BFS>

문제 

 

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

 

 

입력

 

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

 

출력 

 

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

 

 

문제 풀이

   - 시간 초과 코드

#시간초과
import sys

if __name__=='__main__':
    N,M,V=map(int,sys.stdin.readline().split())

    arr={}
    check=[False]*N # 다 방문했는지 확인
    for i in range(M):
        a,b=map(int,sys.stdin.readline().split())
        if a in arr:
            temp=arr.get(a)
            temp.append(b)
            arr[a]=temp
        else:
            arr[a]=[b]
        if b in arr:
            temp = arr.get(b)
            temp.append(a)
            arr[b]=temp
        else:
            arr[b]=[a]

    for key,value in arr.items():
        value=sorted(value)
        arr[key]=value


    # DFS - 깊이 우선 탐색
    X=V
    result=[X]
    check[X-1]=True
    while False in check:
        for i in arr.get(X):
            if check[i-1]==False:
                result.append(i)
                X=i
                check[i-1]=True
                break

    print(' '.join(map(str,result)))

    # BFS - 너비 우선 탐색
    check=[False]*N
    result=[V]
    check[V-1] = True
    temp=[V]
    while False in check:
        V=temp.pop(0) # 너비 우선 탐색이므로
        for i in arr.get(V):
            if check[i-1]==False:
                temp.append(i)
                result.append(i)
                check[i-1]=True

    print(' '.join(map(str,result)))

 

• DFS와 BFS를 구하는데 while문 for문을 다 사용한 Magic

풀면서도 DFS, BFS 구하는데 코드가 이렇게 긴가 하면서 눈물 났던 문제이다.

내가 DFS, BFS도 모르는가? 그럴지도.. 이번 기회를 통해 이해한 것 같다!

이 문제는 개념 문제라 DFS, BFS 개념부터 찾아봤다. 사실 개념 코드를 본 것이 이 문제의 전부라고 생각한다..

 

 

- 통과한 코드

import sys

def dfs(arr, start): # 깊이 우선 탐색
    visit=[]
    temp=[start]

    while temp:
        x=temp.pop(0)
        if x not in visit: # 아직 방문하지 않았다면
            visit.append(x)
            temp=arr.get(x)+temp
    return visit

def bfs(arr, start): # 너비 우선 탐색
    visit=[]
    temp=[start]

    while temp:
        x=temp.pop(0)
        if x not in visit: # 아직 방문하지 않았다면
            visit.append(x)
            temp+=arr.get(x)
    return visit

if __name__=='__main__':
    N,M,V=map(int,sys.stdin.readline().split())

    arr={}
    for i in range(N): #init
        arr[i+1]=[]

    for i in range(M): # 양방향 간선
        a,b=map(int,sys.stdin.readline().split())
        arr[a].append(b)
        arr[b].append(a)

    for key,value in arr.items(): #작은 것 먼저 방문하기 위해 정렬
        value=sorted(value)
        arr[key]=value

    print(' '.join(map(str, dfs(arr,V))))
    print(' '.join(map(str, bfs(arr, V))))

 

• dfs
  - visit list 선언, temp list에 시작할 정점 번호 넣어서 선언
  - temp list가 빌 때까지 반복: temp에서 맨 앞 값을 뽑아와 아직 방문한 정점이 아니라면 visit에 추가하고 temp list 앞에 그 정점과 연결된 정점들을 추가
• bfs
  - visit list 선언, temp list에 시작할 정점 번호 넣어서 선언
  - temp list가 빌 때까지 반복: temp에서 맨 앞 값을 뽑아와 아직 방문한 정점이 아니라면 visit에 추가하고 temp list에 그 정점과 연결된 정점들을 추가
• main
  - 정점 수, 간선 수, 시작 정점 입력
  - 정점과 연결된 정점을 dict로 표현 -> key 값들 다 선언
  - 양방향 간선 이므로 양쪽 key에 value 추가
  - 정점 번호가 작은 것 먼저 방문하기 위해 정렬
  - dfs, bfs 호출

---

생각🤔

 

dfs와 bfs를 이해하고 나니 문제를 쉽게 해결할 수 있었던 것 같다. 아.. 아닌가 dfs 코드가 잘못된 거 같기도 하고 아닌 거 같기도 하고 모르겠다 ㅜ_ㅜ

이제 겁먹지 말고 dfs와 bfs 관련된 문제를 도전해봐야겠다 😉

 

---