풀이_1260.md

🤓 백준 1260 - DFS와 BFS

• Date : 2020.11.7(토)
• Time : 10분

문제

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

코드 풀이

def dfs(v):
    visited.append(v)
    for i in adj[v]:
        if i not in visited:
            dfs(i)

: 먼저 처음 시작 노드를 visited 배열에 넣어준다. 그리고 그 번호와 연결된 정점들을 보면서 방문하지 않았다면 재귀함수를 이용해서 구현했다.

def bfs(v):
    need_visit = deque()
    need_visit.append(v)
    while need_visit:
        node = need_visit.popleft()
        if node not in visited:
            visited.append(node)
            for j in adj[node]:
                if j not in visited:
                    need_visit.append(j)

: 먼저 방문해야하는 정점을 넣어주는 리스트를 큐로 구현했다. 그리고 처음에는 역시 시작 노드를 넣어줬다. 그리고 그 배열에 정점이 있는 동안 while문을 계속 돌아줬다. 방문해야하는 노드를 need_visit의 제일 왼쪽 데이터로 빼고, 만약 방문하지 않은 노드라면 방문했다는 표시를 해준 다음 그와 연결된 노드를 본다. 역시 그 노드들도 방문하지 않았다면 need_visit에 넣어서 방문해야 한다는 것을 표시한다.