낼름낼름 동동이

[ASAC 6일차] 그래프 탐색(DFS,BFS), Class, Stack, Queue 본문

데이터분석/파이썬

[ASAC 6일차] 그래프 탐색(DFS,BFS), Class, Stack, Queue

인죠인간 2024. 3. 28. 18:52

3월 28일의 기록

 

회사를 그만두고 헬스를 하게 된지, 3개월 정도 지났다.

처음에는 매일 가는게 힘들었지만 꾸준하게 하다보니 이제는 헬스장에서 운동하는게 즐겁다.

 

그런데, ASAC 과정을 시작하게 되면서 그날 배운건 그날 최대한 익히려고 하다보니 예전처럼 매일 헬스장에는 가지 못하고 있다.

갈수록 과정이 어려워지면 점점 더 못갈수도 있겠다는 생각이 들었다. 그래도 이제 막 습관이 들었는데... 이대로 또 운동을 안하고 살수는 없으니 평일에는 3회정도로 타협을 보고 주말에는 운동을 해야겠다.

0. 목차

  1. word count
  2. Class
  3. 소수문제, 재귀함수, while, 탐색
  4. Stack, Queue

1. word count

  • 가장 기본적인 Dict를 가지고 활용하는 예 : 워드카운트
  • 어떤 단어가 몇 번 나타났는지 계산
  • 단어 & 출현빈도(연결 / 쌍)
  • 쌍/연결 구조 : Dict(key : 단어, value : 출현빈도)
  • 단! 내가 수집한/처리할 긴 텍스트들 중에서 쭉~~ 스캔하면서 해당 단어가 나올 때 마다 카운팅!

간단 예제)

songs = '''The snow glows white on the mountain tonight 
Not a footprint to be seen A kingdom of isolation And it looks like I'm the queen"
songs'''

방법

  1. To Do : 위 단어 리스트를 돌아가면서 for문 돌리고
  2. 각, 단어별로 몇번 나타나는지 카운팅을 한다

Case 1) 신규 등록된 단어 : 단어 키, 값 1

Case 2) 이미 나왔던 단어 : 단어로 키 조회 → 값 + 1갱신

작성 코드

words = songs.split(" ")
# 1) 내가 words 입력에 대해서 처리할 양식을 결정하기

counts = {} # dic으로 왜? 1개 단어가 몇번 빈도로 나오는지 알기 위해
# 키 : 단어, 값 : 빈도
# 수집된 단어를 돌아가면서 for 문돌리기

for word in words: #복합어 처리......
# 1) 대소문자에 대한 처리 : 소문자로 통일
	word = word.lower() # The --> the
	# 2) 입력 단어들에 대해서 빈도 처리
	# ==> 기 등록된 여부 : key 있는지 ---> in
	# (in 리스트 : 값이 있냐(OR), in 딕셔너리 : 키가 있냐)
	if word in counts: #True --> 기 등록된 단어 : +1 갱신
		 counts[word] += 1
	else: #처음 등록된 단어 : 신규 단어
		counts[word] = 1

실행 결과

공백을 기준으로 단어와 그 빈도가 dict으로 저장된다.

2. Class

목적: 코드들을 기능 중심으로 구조화하고 

클래스를 통해 객체를 생성하여 관리한다.

 

객체 지향 언어

객체 지향 언어가 나오기 전 프로그래밍은 프로그램에게 어떤 일을 하고, 그 다음에는 어떤 일을 하고 이런식으로 절차가 진행되는 방식으로 일을 시켰었다. 그러나 객체 지향 언어에서는 프로그램 작성의 대상이 되는 실제 객체를 그대로 표현하고, 그것들이 어떻게 움직이는지 정해준다음 그 객체에게 일을 시키게 된다. 객체지향 프로그래밍을 잘 사용하면 좋은 프로그램을 빠르게 만들면서 수정하기도 편해진다.

실제 세계에 존재하는 실체(instance)를 객체(object)라고 하며, 객체들의 공통점을 간추려서 개념적으로 나타낸 것이 클래스(class)라고 한다.

 

  • 함수 : 하나의 기능을 가진 코드의 집합
    • 입력 / 출력 / 기능
    • 함수를 사용한다 = 함수를 호출한다.
    • 종류 :
      • 내장 함수 = 내부에서 만들어짐
      • 외장 함수 = import 필요
  • 클래스 : 내가 필요한 대상(속성, 기능)
    • 객체 지향 언어로 객체를 만들어서 사용한다.
    • 한 파이썬 파일 내에서 class class명(): 을 통해 선언함
    • 일반적인 함수와 구별하기 위해서 대문자로 시작
  • 모듈 (module) : 여러 기능들이 뭉쳐진 하나의. py파일
    • 함수, 클래스, 변수 등을 포함
  • 패키지(package) : 필요한 여러가지 들을 모아둔 것
    • 라이브러리라고도 부른다.
    • 특정 기능과 관련된 여러 모듈을 한 그룹으로 묶은 것이다.
    • 패키지 안에 패키지가 또 있을 수도 있다.
    • ex) pandas, scikit-learn + optuna, TF/PyTorch
    • 딥러닝 : TensorFlow —> Keras : 함수
    • 프로젝트(최신 것) PyTorch : 클래스!!!

간단 예제

학생들에 대한 국어, 영어, 수학, 과학 점수들을 처리하고자 할 때

 

주어진 정보들을 파이썬의 특징을 활용해서

방법 1) 그냥 리스트로 만들기

  1. 우리반 전체 학생들에 대해서 : 리스트
  2. 개별 학생에 대한 정보 : 딕셔너리
# 코드를 작성하면서 바로 만든다면 다음과 같이
students = [
    {"name":"AAA", "korean":98,"math":93, "english":79, "science":95},
    {"name":"BBB", "korean":78,"math":87, "english":87, "science":90},
    {"name":"CCC", "korean":90,"math":85, "english":89, "science":92},
    {"name":"DDD", "korean":80,"math":96, "english":99, "science":93},
    {"name":"EEE", "korean":70,"math":80, "english":89, "science":95},
]

# 우리반 학생별로 4과목 성적에 대한 총점/ 평균 점수를 출력하자!!!!
# 출력 : 학생이름, 4과목 총점, 4과목에 평균 출력!!!
print("이름","총점","평균", sep="\\t") 
# sep: 출력대상 사이에 진행, 
#end: 다 출력한 뒤 무언가 하기(기본:줄 바꿈)
for student in students:
    # 개별 학생에 대해서 할 일에!!!!
    score_sum = student["korean"] + student["math"] \\
                    + student["english"] + student["science"]
    score_avg = score_sum / 4
    print(student["name"], score_sum, score_avg, sep="\\t")

방법 2) 함수 형태로 객체 생성

# 2) 학생들에 대한 정보를 생성하는 함수!!!!!!
#    ===> 학생마다 정보를 만들 때 키값이 반복이 되고 있다..
#         귀찮으니,,,,함수로 만들어서 처리해보자!!!!
#    ===> 가장 반복없는 기본이 되는 정보들만 가지고 생성!!

#학생 생성 함수
def create_student( name, kor, math, english, science):
    return { "name":name, "korean":kor,
            "math":math, "english":english,
             "science": science}

#만든 함수로 개별 학생에 대한 정보를 생성한다면
students=[
    create_student("AAA", 98,93,79,95),
    create_student("BBB", 78,87,87,90),
    create_student("CCC", 90,85,89,92),
    create_student("DDD", 80,96,99,93),
    create_student("EEE", 70,80,89,95)
]
#출력은 위와 동일하게 진행

print("이름","총점","평균", sep="\\t")

for student in students:
    score_sum = student["korean"] + student["math"] \\
                    + student["english"] + student["science"]
    score_avg = score_sum / 4
    print(student["name"], score_sum, score_avg, sep="\\t")

방법 3) 필요한 기능은 모두 함수화

# 3) 필요한 기능들에 대해서 다 함수화를 최대한 해보자!!!!
# - 1명 학생에 대한 정보를 생성하는 함수
# - 1명 학생에 대한 정보를 바탕으로 총점을 구하는 함수
# - 1명 학생에 대한 정보를 바탕으로 평균을 구하는 함수
# - 1명 학생에 대한 정보를 출력하는 함수(이름, 총점, 평균)

# - 1명 학생에 대한 정보를 생성하는 함수
#   입력 : 이름, 국어, 수학, 영어, 과학
#   기능 : 학생 정보를 Dict 생성
#   출력 : 1명 학생 정보 Dict
def create_student( n, k, m, e, s):
    return 
    { "name":n, "korean":k, "math":m, "english":e,
    "science": s}

# - 1명 학생에 대한 총점을 계산해주는 함수
#   입력 : 1명 학생의 정보
#   기능 : 총점을 계산
#   출력 : 총점
def student_get_sum( student ): # student = {"name":"AAA",~~~~~}
    score_sum = student["korean"] + student["math"] \\
                + student["english"] + student["science"]
    return score_sum

# - 1명 학생에 대한 4과목 평균을 함수
# - 입력 : 학생 1명에 대한 정보
#   기능 : 4과목 점수 평균 계산
#   출력 : 평균 점수
def student_get_avg( student ):
    score_avg = student_get_sum(student) / 4
    return score_avg

# - 1명 학생에 대한 정보 출력하는 함수/기능!!!!
# - 입력 : 학생 1명에 대한 정보
#   기능 : 정보를 출력 문자열생성 ->이름, 총점, 평균
#   출력 : 출력할 문자열
def student_to_string(student):
    temp = "{0}\\t{1}\\t{2}".format( student["name"],
                               student_get_sum(student),
                                studnet_get_avg(student))
    return temp

방법 4) 클래스로 구현하기

class Studnet: # 일반적인 함수와 구별하기 위해서 대문자로 시작
    # 생성자 : 필용한 초기 속성들에 대한 초기화!!!!!
    #         ==> 파이썬에서 클래스 생성을 위한 미리 만든 특별함수
    #             _(양옆으로 2개)
    def __init__(self, name, korean,math,english,science):
        self.name = name
        self.korean = korean
        self.math = math
        self.english = english
        self.science = science

    # --> 필요한 기능 추가 : 총점계산, 평균계산, 출력(이름,총점,평균)
    def get_sum(self):
        score_sum = self.korean + self.math + self.english + self.science
        return score_sum
    def get_avg(self):
        score_avg = self.get_sum() / 4
        return score_avg
    def to_string(self):
        temp = "{0}\\t{1}\\t{2}".format(self.name, self.get_sum(),
                                   self.get_avg())

# 객체 생성 방식
students=[
    Studnet("AAA", 98,93,79,95),
    Studnet("BBB", 78,87,87,90),
    Studnet("CCC", 90,85,89,92),
    Studnet("DDD", 80,96,99,93),
    Studnet("EEE", 70,80,89,95)
]

+참고) 클래스 내부의 속성값에 외부의 접근을 막기 위해 속성값을 __ 지정할 수 있다.

class Square:
    def __init__(self, size):
    
		    #이런식으로
        self.__size = size
    def get_area(self):
        return self.__size * self.__size

참고) 파이썬의 문자열 표현 방식

a=345 일때

  1. % 연산자 활용 
    ex) print("나의 총점 :", a)
  2. format() 함수 표현
    ex) print("나의 총점 :{}".format(a))
  3. f-string 표현
    ex) print("나의 총점 :{}, 평균:{:.2f}".format(a,b))

 

사전 지식) while 반복문

 

조건이 참일 때까지 돌아가면서 무엇을 할지 설정할 수 있다.

일반적으로 사용할 때는 다음과 같이 사용한다.

# 예) 1부터 20까지 출력을 하자!!
i = 1 # --> 출력을 하기 위한 값의 변수
while i < 21: # 몇 번이 중요한 것이 아니라 해당 조건이 만족할 때 까지..
    print(i)  # 이론은 계속 돌아야 하는데,,파이썬은 중간에 세움!!!
    i += 1

# 예) 1부터 20까지 출력
#    --> 특정 조건이 되면 while 세우자!!!
i = 1
while True: # 일단 주구장창 돌리고,,밑에서 break
    print(i)
    if i==20:
        break
    i += 1
  • 보통은 무한으로 진행되게 되고 break를 통해 특정 조건에서 반복을 멈출 수 있도록 세팅을 한다.

 

사전 지식) Stack, Queue 자료구조

  1. 기본적인 내용 : 값을 처리하는 방식 --> 새롭게 추가가 되는 값 --> 지금 당장 처리해야 되는 값

Stack : 지하철 : 늦게온 사람이 제일 먼저 내린다

  • Last In First Out : LIFO
  • 비유 : 지하철 출입
  • 새로운 것 : 뒤로 쌓아 둔다. ⇒ .append()
  • 처리할 것 : 맨 뒤에 쓴 것부터 빠진다. ⇒ pop()

Queue : 놀이공원 매표소 줄서기 : 먼저 줄 선 사람 먼저 표 받음

  • First In First Out : FIFO
  • 비유 : 놀이공원 매표소
  • 새로운 것 : 뒤로 쌓아 둔다. ⇒ .append()
  • 처리할 것 : 맨 앞에 있는 것 부터 빠진다. ⇒ pop(0)

참고) 파이썬 리스트에서 대표적인 자료구조 queue를 구현하는 경우

  • 파이썬 언어의 특징상 앞 원소를 차출할 때 (pop(0))속도의 이슈 존재.
  • 따라서, 탐색 알고리즘에서 queue로 파이썬으로 구현하면 속도가 느려짐
    • 이론적으로는 맞으나 파이썬 특성상 문제가 생긴다.
    • 따라서, deque 패키지를 불러와서 사용해야 한다.
    • 정규식처럼 일반적인 코테 플랫폼에서 기본적으로 쓸 수 있다.

사전 지식) 재귀 함수

사전 정의 : 정의 단계에서 자신을 재참조하는 함수

일반적인 코드, 데이터 분석에서는 거의 사용하지 않음

단. 코테에서는 자주 사용된다.

⇒ 왜??: 구조적인 반복을 코드화 하면 되니까

참고) 파이썬 재귀함수의 특징

→ 일반 언어와는 다르게 무한 반복되지 않고 어느정도 선에서 limit가 걸려있다.

따라서, while을 사용하는 것처럼 종료에 대한 조건을 항상 넣어두어야 한다.

재귀함수의 예시

  • 4!
    • 4! = 4 * 3 * 2 * 1

for , while 반복문으로 팩토리얼을 만들어보기

# --> 1) for문
n = 4
fact = 1
for i in range(1, n+1, 1):
    fact *= i
print(fact)

# --> 2) while문으로 구현,,,,
#        => 조건이 만족할 때까지 주구장창!!!!
#           편한 점 : 도는 횟수를 신경 안 쓰고 돌릴 때...
#                     횟수 보다는 조건 중심으로 바라볼때..
#           단점 : 종료조건에 대한 세팅!!
n = 4
fact = 1

cnt = 1 # <--- while을 돌리는 종료 조건  세팅용.
while cnt <= n:
    fact *= cnt
    cnt += 1 # <--- 종료를 위한 모니터링 변수에 대한 작업!!!!!
print(fact)

재귀함수로 fact을 구현 해보기

# ==> !기능 중심으로 바라보자
#     n! = n * (n-1)!
# ==> 기능 중심의 규칙
# =========> 바로 코드화가 용이하다.
def my_fact(n):
    # 호출이 되었는지 체크용-->print
    print("My Fact 함수 불렀어요?:", str(n))

    if n <= 1:
      return 1
    else:
      return n * my_fact(n-1)

재귀함수 정리

  1. 기능 중심의 관계성/ 규칙성이 있는 부분을 간단하게 코드화 한다.
  2. while 처럼 종료조건, 일을 해결할 부분에 대한 세팅을 한다.
  3. 재귀 함수는 자기 자신을 계속 호출한다
    1. 해결 순서는 마지막에 호출된 함수 → 첫 호출 함수 순으로 감
    2. 즉, stack의 구조와 동일하다.

그래프 탐색

탐색 알고리즘의 종류

  • 이진 탐색
  • DFS: stack 형식으로 탐색을 하기에 재귀함수로 탐색이 가능하
  • BFS: Queue형식으로 탐색을 하기 때문에 기능 중심에서 재귀 함수로는 탐색이 불가능하다.

그래프의 개념?

다음과 같은 그림에 대한 수학적인 변환을 우리는 그래프라고 부른다. 그래프는 점과 선들로 이루어지게 되며 이를 수학적인 공식으로 나타내면 G = (V, E) 라고 할 수 있다.

→ 즉, 간단히 말하면, 노드(node)와 간선(edge)로 표현이 된다. 경우에 따라서 노드는 정점(Vertex)라고 표현을 하기도 한다!

결론: 그래프는 Node & Link or Vertext & Edge로 표현한다고 개념을 가지고 있어야 한다.

종류

  • 선에 대해서 방향을 생각할 수 있다.
  • 방향성이 없는 Undirected Graph, 방향성이 있는 Directed Graph
  • (Vi, Vj) = (Vj, Vi) : Undirected Graph
  • (Vi, Vj) ≠ (Vj, Vi) : Directed Graph

탐색 문제는 모든 경우들을 다 체크한다.

수학적인 모든 경우의 수 문제

최단 거리도 bfs 탐색 기반으로 할 수 있다.

여러 유형을 풀어봐야 한다. (유형별로 많이! 해봐야 한다.)

  • 문제별로 왜 이 문제가 탐색이지?
  • 어떤 탐색 알고리즘이 적당할까?

그래프에 대한 표시 예시

  • 두개의 그림 중 위 그림은 수학쪽에서 사용하는 그래프 표현
  • CS쪽에서 이에 대한 표현은 크게 두가지이다. 인접행렬(Adjacency Matrix), 인접리스트(Adjacency List)
  • 아래의 그림은 인접행렬로 표현 : 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식.
    • 파이썬에서는 2차원 리스트로 구현할 수 있다.

인접행렬 방식 표현

# 입접행렬방식으로 표현
# 중요!!! ) 파이썬의 리스트를 가지고 2차원 행렬 표현!!!!!
#         ===> 가로줄 단위로 묶어서,,,
#              최종 적으로 한 번 묶어준다!!!!!!
m = [
      [ 0, 7, 5],
      [7, 0, INF],
      [5, INF, 0]
]
# ---> 0번에서 1번 도시가 연결 되었나요?
m[0][1]

# ===> 행렬로 표현을 한다면 : 가로줄 --> Start : 지도[1번인덱스]
#                        세로줄 --> End   : 지도[1번][세로줄 인덱스]
# 쌩파이썬의 인덱스 입장으로 지도를 표현한 인접행렬을 바라본다면,,
#  지도[start][end]

# 참고) 명시적으로 2D numpy, df, tensor :파이썬 다른 패키지...
#       지도[가로,세로]

인접 리스트 방식 표현

# 인접리스트 방식으로 표현: 도로 연결 중심!!!!!
#  ==> 상황마다 조금씩 표현 스타일은 다를 수 있음!!!!!
g_1 = [
    [ (1,7), (2,5)], # --> 0번 도시의 연결 리스트업
    [ (0,7)], # --> 1번 도시의 연결 리스트업
    [ (0,5)], # --> 2번 도시의 연결 리스트업
]

# --> 0번 도시에서 1번 도시가 연결 되어 있나요??
g_1[0][0][1]
# --> 구체적인 연결성에 대한 질문에 대해서는 탐색을 해야되어서
#     좀 행렬보다는 직관성은 떨어진다!!!!!!

DFS (Depth First Search)

  • 기본 아이디어: 깊은 부분을 우선적으로 탐색해보자
  • DFS = Depth First Search
  • “Stack”을 활용해서 구현이 된다. ⇒ 따라서 FILO 방식이다.
  • 데이터를 집어넣는 순서와 꺼내는 순서가 역방향이다.

간단 구현 코드

# 0) 탐색에 대한 지도를 코드화!!!!!!
#     ==> 인접 리스트 : 리스트로 표현할 때
#         가상의 0번 도시가 있다고 가정하고 표현!!!!
graph_list = [
    [], # <-- 가상의 0번 도시는 연결되어 있지 않다 :인덱스처리용 더미
    [2,3,8], # <- 1번 도시와 연결된 도시들
    [1,7],   # <- 2번 도시와 연결된 도시들
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]
graph_list

# 입력 : 지도, 시작점
# 기능 : DFS방식으로 주어진 지도를 탐색/방문하겠다
# 출력 : 방문한 기록을 제출!!!!

def dfs_m1( graph, start):
    # 초기 변수들에 대한 세팅
    # - 1) 방문할 곳 리스트 (To Do List)
    # - 2) 방문한 곳 리스트 (Done List)
    need_visit = list()
    visited    = list()
    # --> 팀장한테 부여받은 출발점 : 할 일에 추가!!!!!!
    need_visit.append( start )

    # 출발!!!!!
    # ==> 언제까지 할 거냐? need_visit 할 목록이 없을 때 까지!!!
    #     언제, 몇 번에 없어질지 몰라요... 주구장창 while
    while need_visit:
        # 1) 나 이제 어디로 갈까 : 방문할 곳 하나 꺼내!!!!
        #    ==> 할 일의 선택 : 맨 뒤에서 꺼내겠다!!! Stack!!!
        node = need_visit.pop()
        # 2) node 내가 이미 갔던 곳인지, 신규방문지 체크!!!!
        #    ==> 갔던 곳이면 pass
        #    ==> 신규 방문 : 왔다고 도장 찍어야 함!!!
        #                    + 이 곳에서 연결된 곳들을 받아서
        #                      할 일에 추가를 해야함!!!!!!
        if node not in visited: # <- 신규 방문지
            # 2-1) 도장찍기!!!!
            visited.append(node)
            # 2-2) 연결된 도시(또 나 방문할 곳 있어요?)
            need_visit.extend(graph[node] )
    return visited

이대로 출력을 해보면 다음과 같은 결과가 나온다.

기대했던 결과는 [1, 2, 7, 6, 8, 3, 4, 5] 인데 왜 다른 결과가 나올까?

→ 그 이유는 graph_list를 세팅할 때 리스트에 1번 노드에 연결된 리스트가 [2,3,8]이렇게 되어 있어서 뒤에서 부터 값이 추가되는 특성상 8이 먼저 들어가는 방식이 되었다.

reversed() 메소드 사용한 코드

# reversed()를 활용해서 역방향으로 node들을 작은 순으로 방문할 수 있게 수정

# 입력 : 지도, 시작점
# 기능 : DFS방식으로 주어진 지도를 탐색/방문하겠다.
# 출력 : 방문한 기록을 제출!
def dfs_m2(graph, start):
    #초기 변수들에 대한 세팅
    # - 1) 방문할 곳 리스트 (To do List)
    # - 2) 방문한 곳 리스트 (Done List)
    need_visit = list()
    visited    = list()

    # 팀장에게 부여받은 출발점 : 할 일을 먼저 추가해야한다.
    need_visit.append(start)
    
    #출발!!
    # ==> 언제까지 할꺼냐? need_visit이 다 빌때까지

    while need_visit: #need_visit이 0이 되면 자동으로 멈추게 됨
        # 1) 나 이제 어디로 가야해? : 방문할 곳 하나 꺼내기
        #    ==> 할 일의 선택 : 맨 뒤에서 꺼내야지
        node = need_visit.pop()
       
        # 2) node: 내가 이미 갔던 곳인지, 신규 방문지인지 체크해야해
        # ==> 갔던 곳이면 pass
        # ==> 신규 방문 : 왔다고 도장 찍어야 한다.
        #               + 이 곳에서 연결된 곳들을 받아서
        #                 할 일에 추가를 해야한다. 
        if node not in visited: #신규 방문지이면 할일이 있으니까 not in 체크
            # 2-1) 도장 찍기
            visited.append(node)
            # 2-2) 연결된 도시 (또 나 방문할 곳이 있어?)
            #### ---> 여기서 순서를 지정 : 지도 구성의 역순으로 돌리면,
            # 역방향 : .reverse(), reversed(), [::-1]
            # ++ 도시별 정렬을 할 수도 있음!
            temp = graph[node]
            temp_reversed = list(reversed(temp))
            need_visit.extend(temp_reversed)
        else:
            pass
    return visited

BFS( Breadth First Search)

기본 원리 및 동작

  • 기본적인 동작 : 가까운 노드부터 탐색하는 알고리즘이다 (그렇기 때문에 아래로 들어가는 것이 아니라 같은 level에 있는 것부터, 수평적인 탐색을 하게 된다)
  1. 탐색 시작 노드를 큐에 삽입 & 방문 처리
  2. 큐에서 노드를 꺼낸다 → 인접 노드들 중에서 방문을 했는지 안 했는지 판단 → 방문하지 않았으면 큐에 넣어서 방문을 하도록 한다.
  3. 2번의 과정을 방문을 해야할 곳이 없을 때 까지한다.

간단 코드

## --> BFS 간단하게 pop(0)로 코드만 변환하게 된다면

def bfs_m1(graph, start):
    need_visit = list()
    visited    = list()
    need_visit.append(start)

    while need_visit:
        node = need_visit.pop(0) # <--- 여기서 속도에 걸리게 된다 파이썬에서!!

        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node])
        else:
            pass
    return visited

 

'데이터분석 > 파이썬' 카테고리의 다른 글

[ASAC 9일차] 파이썬 + SQL 기초  (0) 2024.04.02
[ASAC 8일차] 특강, 탐색: DFS, BFS  (1) 2024.04.01
[ASAC 5일차] 정렬, 정규식  (0) 2024.03.27
[ASAC 4일차] 알고리즘의 시작  (0) 2024.03.26
[ASAC2일차] 파이썬 기본기 쌓기  (1) 2024.03.22
'데이터분석/파이썬' Related Articles more