[알고리즘] 스택&dfs / 큐&bfs

장현수·2023년 5월 16일
0

알고리즘

목록 보기
7/9

스택 구현 : append, pop

무방향 그래프의 인접행렬의 모양은?
-> 대칭적이다. = 전치가 의미가 없음

dfs 깊이우선탐색

  • 전체 점을 다 거쳐야 하는 경로
    visited 사용
    1) 리스트 방식 : 방문 한 점의 값을 True
    2) set 방식 : 방문 한 점을 visited set에 추가(공간복잡도 더 소요)
stack = [1]  # 맨처음 시작점은 1번 포도알
visited = [] 
-----------------------------------------준비상태
while stack:  # 스택이 빌때까지 돌아라!
    current = stack.pop()  # 우선 스택에서 현재 위치 하나 뽑고
    if current not in visited:  # 방문하지 않은 곳이라면,
        visited.append(current)  # 방문했다고 체크해줌
---------------------------------------------로직1		
		# 위의 if문 안으로 넣으면 더 좋습니다.
    for destination in range(V+1):  # current 입장에서 어디로 갈 수 있는지 모조리 체크
        if adj_matrix[current][destination] and destination not in visited:  # 갈수있고 + 방문 안했으면!
            stack.append(destination)  # 다음 갈 곳으로 Stack에 저장
---------------------------------------------로직2

<dfs 깊이우선탐색 준비>

  • visited 개념 사용
  • 컴퓨터는 인접행렬을 가지고 있다. = 나는 그래프를 볼 수 있다.
  • cur(현재 내 위치)변수
  • 1부터 탐색 -> stack에 1을 넣고 시작

stack이 빌 때까지 회차 반복

<1회차>
로직 1)
stack.pop() => 1
-> cur = 1 (현재 위치 = 1)
-> 현재 cur가 visited에 없으면 방문체크 하기. visited.append(1)

로직 2)
아직 가지 않은 곳이면서(not in visited) and 현재 cur와 이어져있는 곳(길이 있음) 탐색
-> 그것을 stack에 넣음
-> 회차 종료

1), 2) 로직을 노드만 바꿔가며 계속 반복 -> 재귀함수로도 가능

파이썬이기 때문에 스택에 중복값 쌓여도 상관 없음.
-> 스택에 기존 노드보다 많은 수가 쌓일 수 있음.

루프를 다 돌아도 스택이 빌 때까지 돌아야 함.

visited가 찍힌 후 스택들은 다 pop됨

bfs 너비우선탐색

<준비>

  • visited
  • cur
  • 시작 위치를 queue에 넣어두고 시작(1)

<1회차>

  • queue pop(0) : 선입선출이기 때문에 첫번째 요소 pop
    -> cur = 1
    -> if cur not in visited : visited.append(1)
    이어져있으면서 방문하지 않는 것들 queue에 쌓음

인접행렬 구조화

7 8  # Vertex = 7개, Edge = 8개인 그래프가 있을 때, (무조건 트리 아님)
1 2  # 다음 8개의 줄에 연결 정보를 제공
1 3  # 누구랑 누구가 연결되어있는지임.
2 4
2 5
4 6
5 6
6 7
3 7
a = [[0]*3]*3
a[0][0] = 9
a
[[9, 0, 0], [9, 0, 0], [9, 0, 0]]
  • id값 분리가 안됨 -> 사용하면 안되는 방식
b = [[0]*3 for _ in range(3)]
b[0][0] = 5
b
[[5, 0, 0], [0, 0, 0], [0, 0, 0]]
  • id값 분리. 이 방식으로 바둑판 만들어야 함
  • 인접 행렬 : 공간은 더 잡아먹지만 탐색이 빠름, 전치 등 확장성이 좋다
  • 인접 리스트 : 공간은 덜 잡아먹지만 시간은 더 걸림, 유의미한 결과값에선 평균적으로 더 빠르다

인접 행렬로 자료 정리하기

V, E = map(int, input().split())  # Vertex(포도알), Edge(선) 갯수

adj_matrix = [[0] * (V + 1) for _ in range(V + 1)]  # 인접행렬 기본틀 + 0번 포도알은 안씀

for _ in range(E):  # 간선 갯수만큼 돌면서 연결 정보를 받음
    start, end = map(int, input().split())  # 시작점과 끝점
    adj_matrix[start][end] = 1
    adj_matrix[end][start] = 1  # 양방향 그래프니까!!

# adj_matrix print 결과

# [[0, 0, 0, 0, 0, 0, 0, 0],  => 0번 포도알은 존재하지 않음
#  [0, 0, 1, 1, 0, 0, 0, 0],  => 1번 포도알은 2, 3번으로 갈 수 있음
#  [0, 1, 0, 0, 1, 1, 0, 0],  => 2번 포도알은 1, 4, 5번 가능
#  [0, 1, 0, 0, 0, 0, 0, 1],  => 3번 포도알은 1, 7번 가능
#  [0, 0, 1, 0, 0, 0, 1, 0],  => 4번 포도알은 2, 6번 가능
#  [0, 0, 1, 0, 0, 0, 1, 0],  => 5번 포도알은 2, 6번 가능
#  [0, 0, 0, 0, 1, 1, 0, 1],  => 6번 포도알은 4, 5, 7번 가능
#  [0, 0, 0, 1, 0, 0, 1, 0]]  => 7번 포도알은 3, 6번 가능

양방향 그래프

  • = 무방향 그래프
  • 방향이 정해져 있지 않음. 연결된 노드 간 서로 이동 가능

무방향 그래프의 표현

  • 자기 자신을 기준으로 대칭을 이룸
    -> 전치가 의미 없음.

인접리스트로 자료 정리하기

V, E = map(int, input().split())

adj_list = [[] for _ in range(V + 1)]

for _ in range(E):
    start, end = map(int, input().split())
    adj_list[start].append(end)
    adj_list[end].append(start)  # 양방향

# adj_list = [[], [2, 3], [1, 4, 5], [1, 7], [2, 6], [2, 6], [4, 5, 7], [6, 3]]
  • 각 노드가 갈 수 있는 (연결된) 노드를 리스트로 append
    0 번노드는 없음 : []
    1번 노드 : [2, 3]
    2번 노드 : [1, 4, 5]
    3번 노드 : [1, 7]
    4번 노드 : [2, 6]
    5번 노드 : [2, 6]
    6번 노드 : [4, 5, 7]
    7번 노드 : [3, 6]
profile
개같이 발전하자 개발

0개의 댓글