[내가 볼 유용한 모음] 코딩 테스트

 

 

 

 

💚 주어진 임의의 노드 관계를 이용하여 인접 리스트 만들기

• (가장 큰 노드 번호가 5, 노드는 총 5개, 간선 개수 5) 

graph=[[] for _ in range(6)]

for _ in range(5):
    A,B=map(int,input().split())
    graph[A].append(B)
    graph[B].append(A)

print(graph)

https://lbdiaryl.tistory.com/219

 

 

💚 깊이 우선 탐색(Depth First Search)

: DFS는 한 루트로 계속 들어가 탐색한 뒤 탐색을 마치면 다시 돌아가 방문하지 않은 루트로 들어가 탐색

: 모든 경우의 수를 찾기 위한 백 트래킹 시 자주 사용되는 탐색 알고리즘

def dfs(v):
    visited[v] = True
    print(v, end=' ')
    for i in graph[v]:
        if not visited[i]:
            dfs(i)


graph=[[] for _ in range(6)]
visited=[False]*6 #방문 여부

for _ in range(5):
    A,B=map(int,input().split())
    graph[A].append(B)
    graph[B].append(A)

for i in graph: #노드번호에 따라 정렬
    i.sort()

dfs(1)
print()
print(visited)
print(graph)

 

 

 

 

 

 

 

💚 넓이 우선 탐색(Breadth First Search)

: BFS는 시작 노드로부터 가까운 노드를 순차적으로 탐색하는 알고리즘

: 연결되어 있는 노드를 큐에 넣고 순차적으로 추출해나가는 과정을 통해 구현

from collections import deque

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]:
                queue.append(i)
                visited[i] = True

graph=[[] for _ in range(6)]
visited=[False]*6

for _ in range(5):
    A,B=map(int,input().split())
    graph[A].append(B)
    graph[B].append(A)

for i in graph: 
    i.sort()

bfs(1)
print()
print(visited)