[백준] [실버2] 1260. DFS와 BFS

1260. DFS와 BFS

1260번: DFS와 BFS

 

• 내 풀이
  • 문제 잘 읽기!! 
  • 방문할 수 있는 정점 여러개인경우 작은것부터 -> sorted () 해주기

from collections import deque
from collections import defaultdict
#N: 정점개수
#M: 간선 개수
#V: 탐색 시작정점
N,M,V= map(int,input().split())
stack=deque()
queue=deque()
lst=defaultdict(list)

for i in range(M):
    x,y=map(int, input().split())
    lst[x].append(y)
    lst[y].append(x)


def dfs(stack, V, visited):
    stack.append(V)
    while stack:
        x=stack.pop()

        if x not in visited:
            print(x, end=" ")
            visited.append(x)
            for ls in sorted(lst[x]): #정점 작은것부터 방문
                dfs(stack, ls, visited)
            

def bfs(queue, V, visited):
    queue.append(V)
    while queue:
        y= queue.popleft()

        if y not in visited:
            print(y, end=" ")
            visited.append(y)
            for ls in sorted(lst[y]):
                queue.append(ls)
            
visited=[]
dfs(stack, V, visited)
print()
visited=[]
bfs(queue,V, visited)

 

• 다른 사람 풀이

from collections import deque


def dfs(start):
    visited[start] = True
    print(start, end=" ")

    for i in graph[start]:
        if not visited[i]:
            dfs(i)


def bfs(start):
    queue = deque([start])
    visited[start] = True
    while queue:

        v = queue.popleft()
        print(v, end=" ")
        for i in graph[v]:
            if not visited[i]:
                visited[i] = True
                queue.append(i)


N, M, V = map(int, input().split())
graph = [[] for _ in range(N + 1)]

for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

# 정렬
for i in graph:
    i.sort()

# dfs
visited = [False] * (N + 1)
dfs(V)
print()

# bfs
visited = [False] * (N + 1)
bfs(V)

• 인접행렬방식 - True, False 값으로

from collections import deque

N, M, V = map(int, input().split())

graph = [[False] * (N + 1) for _ in range(N + 1)]

for _ in range(M):
    a, b = map(int, input().split())
    graph[a][b] = True
    graph[b][a] = True

visited1 = [False] * (N + 1)  # dfs의 방문기록
visited2 = [False] * (N + 1)  # bfs의 방문기록


def bfs(V):
    q = deque([V])  # pop메서드의 시간복잡도가 낮은 덱 내장 메서드를 이용한다
    visited2[V] = True  # 해당 V 값을 방문처리
    while q:  # q가 빌때까지 돈다.
        V = q.popleft()  # 큐에 있는 첫번째 값 꺼낸다.
        print(V, end=" ")  # 해당 값 출력
        for i in range(1, N + 1):  # 1부터 N까지 돈다
            if not visited2[i] and graph[V][i]:  # 만약 해당 i값을 방문하지 않았고 V와 연결이 되어 있다면
                q.append(i)  # 그 i 값을 추가
                visited2[i] = True  # i 값을 방문처리


def dfs(V):
    visited1[V] = True  # 해당 V값 방문처리
    print(V, end=" ")
    for i in range(1, N + 1):
        if not visited1[i] and graph[V][i]:  # 만약 i값을 방문하지 않았고 V와 연결이 되어 있다면
            dfs(i)  # 해당 i 값으로 dfs를 돈다.(더 깊이 탐색)


dfs(V)
print()
bfs(V)