파이썬 큐

def bfs(i,j):

    queue = []
    visited = [[0] * N for _ in range(N)]
    queue.append((i,j))
    visited[i][j] = 1
    
    while queue:
        ci, cj = queue.pop(0)
        if len(result) > max_v:
            max_v = len(result)
            result_num = result[0]
        for di,dj in [(-1,0),(1,0),(0,-1),(0,1)]: #상하좌우
            ni = ci + di
            nj = cj + dj
            # 범위 내, 1큰, 노방문
            if 0<=ni<N and 0<=nj<N and board[ni][nj] == board[ci][cj] + 1 and not visited[ni][nj]:
                # 순화하면서 가장 작은 값과 리스트의 길이를 알아야 함
                #그리고 제일 긴 리스트의 길이를 알아야.
                queue.append((ni,nj))
                visited[ni][nj] = 1
                result.append(board[ni][nj])


T = int(input())
for tc in range(1,T+1):
    N = int(input())
    board = [list(map(int,input().split())) for _ in range(N)]
    result = []
    max_v = 0
    for i in range(N):
        for j in range(N):
            if
                bfs(i,j)
    print(f'#{tc} {max_v}')

선형 큐

N = 5
queue = [None] * N
#큐의 현재 맨 앞요소와 맨 뒷요소의 인덱스를 가지고 있는 변수
# front : 맨 앞요소의 -1 인덱스,
# rear : 맨 뒷요소의 인덱스
front = rear = -1
# is_empty() : 큐가 비었는지 확인하는 함수,
def is_empty(): # 큐가 비었으면 True를 반환 아니라면 False 반환
    # front랑 rear랑 같으면 비어있는거
    if front == rear:
        return True
    return False
# is_full()  : 큐가 가득 찼는지 확인하는 함수
def is_full():  #
    #선형 큐에서 full이란, rear가 queue마지막 인덱스를 가리키고 있을때
    if rear == N-1:
        return True
    return False
# enQueue(data) 큐의 맨뒤에 data 삽입
def enQueue(data):
    global rear
    if not is_full():
        rear += 1
        queue[rear] = data
    else:
        raise IndexError('큐가 가득 찼습니다.')
# deQueue() 큐의 맨 앞에서 데이터 반환 및 삭제
def deQueue():
    global front
    if not is_empty():
        front += 1
        return queue[front]
    else:
        raise IndexError('큐가 비었습니다.')

원형 큐

N = 5
queue = [None] * N
#큐의 현재 맨 앞요소와 맨 뒷요소의 인덱스를 가지고 있는 변수
# front : 맨 앞요소의 -1 인덱스,
# rear : 맨 뒷요소의 인덱스
front = rear = 0
# is_empty() : 큐가 비었는지 확인하는 함수,
def is_empty(): # 큐가 비었으면 True를 반환 아니라면 False 반환
    # front랑 rear랑 같으면 비어있는거
    if front == rear:
        return True
    return False
# is_full()  : 큐가 가득 찼는지 확인하는 함수
def is_full():  #
    # 원형큐에서는 rear가 움직일 다음칸이 front의 위치라면 full 상태
    if (rear+1) % N == front:
        return True
    return False
# enQueue(data) 큐의 맨뒤에 data 삽입
def enQueue(data):
    global rear
    if not is_full():
        rear = (rear + 1) % N
        queue[rear] = data
    else:
        raise IndexError('큐가 가득 찼습니다.')
# deQueue() 큐의 맨 앞에서 데이터 반환 및 삭제
def deQueue():
    global front
    if not is_empty():
        front = (front + 1) % N
        return queue[front]
    else:
        raise IndexError('큐가 비었습니다.')

 

BFS(너비 우선 탐색_)

 

• 탐색 시작점의 인접한 정점들을 먼저 모두 차례로 방문한 후에, 방문했던 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식.
• 그 정점의 인접한 정점들을 큐에 인큐한다/.(거리 순. 간선의 갯수가 많으면 멀다)
• 큐가 비어있으면 끝

 

• VISITED 배열 초기화
• 큐 생성
• 시작점 인큐
• 시작점 디큐
• A방문 표시
• A의 인접점 인큐
• 방문하는 점 하나씩 디큐하고 방문표시
• 큐가 비어 있으면 더 이상 탐색할 것이 없는 것이므로 끝!
• 시작점 방문표시<인큐되었다는 것을 표시\
• 출발 점이 여러개일수도 있음/

def bfs(v,n):
    visited = [0] * (n+1)   #visited 생성
    q =[v]  # 큐 생성
    # 시작점 인큐
    visited[v] =1 # 시작점 방문 표시(비지티드)
    while q: #큐가 비어있지 않으면
        t = q.pop(0) #디큐
        print(t,end=' ')    #t에서 처리할 일
        for i in adj_lst[t]:    # tㅇㅔ 인접이고 방문한 적 없는 v
            if visited[i] == 0:
                q.append(i)
                # v 인큐
                # v 인큐 표시(방문 표시)
                visited[i] = visited[t] + 1
    print()
    print(visited)
V,E = map(int,input().split())
arr = list(map(int,input().split()))
adj_lst = [[] for _ in range(V+1)]
for i in range(E):
    n1,n2 =arr[i*2], arr[i*2+1]
    adj_lst[n1].append(n2)
    adj_lst[n2].append(n1)

 

V, E = map(int,input().split())
data = list(map(int,input().split()))
adj_list =[[]for _ in range(V+1)]
for i in range(0,E*2,2):
    adj_list[data[i]].append(data[i+1])
    adj_list[data[i+1]].append(data[i])

# 현재 위치에서 방문할 수 있는 모든 경로를 일단 저장
# 저장한 순서대로 방문하기

visited = [0] * (V+1)
queue = [1]
visited[1] = 1

while queue:
    front = queue.pop(0) #젤 앞에거 빼겠다
    # dfs top = stack[-1]
    # dfs랑 다르게 한 번 방문하고 다시 돌아올 필요가 없어서 빼버리고 시작하는 것.
    print(front, end=' ')
    for node in adj_list[front]: # front랑 노드랑 연결됨
        if not visited[node]: #node 에 방문하지 않았으면 ... 방문 목록에 저장
            queue.append(node)
            visited[node] = 1
print()

bfs

먼저 발견하는 애들이 최단거리

최단거리를 찾는데 그래프 탐색 문제이면 bfs로 찾으면 좋다.(dfs는 최단거리를 찾으려면 모든 경우를 다 탐색한 뒤에 결정 지어야 하기 때문에 bfs가 좋다~)

arr = [
[0,0,1,0,0],
[0,1,1,1,1],
[0,0,1,1,0],
[0,0,0,1,0],
[0,0,0,0,0]
]
N = 5
#상하좌우로 연결된 1의 개수 찾기
queue = []  # 리스트지만...맨뒤에 넣고 앞에서 뺄꺼니까..queue라고 합시다
# 2차원 배열에서 각 요소가 정점이므로..모든 정점에 대해서 방문표시
visited = [[0] * N for _ in range(N)]

for i in range(N):
    for j in range(N):
        if arr[i][j]:
            # 여기에서 bfs 시작
            queue.append((i,j))
            # queue.append(i)
            # queue.append(j)
            visited[i][j] = 1   # 방문표시
            # 현재위치에서 갈 수 있는 모든 경로를 탐색
            # 경로를 발견하면 저장(enQueue)
            # 이후에 경로를 발견한 순서대로 방문(deQueue)
            cnt = 0
            while queue:    #큐에 저장된 노드를 방문하는 작업을 반복
                #현재위치
                ci, cj = queue.pop(0)  #먼저 발견한 순서대로 방문
                cnt += 1
                for di, dj in ([(-1,0),(1,0),(0,-1),(0,1)]):
                    ni, nj = ci + di , cj + dj
                    # 정상 범위 안에 있으면서,
                    if 0 <= ni < N and 0<= nj < N:
                        # 1이고, 방문하지 않았으면, 방문할 노드에 추가
                        if arr[ni][nj] and not visited[ni][nj]:
                            queue.append((ni, nj))
                            visited[ni][nj] = visited[ci][cj] + 1 #목적지까지 가는데 얼마나 걸리는지 표시해줌
            print(cnt)
            print('여러번 실행 될 걸요??')

# 2차원 배열에서 bfs 돌기
arr = [
[0,0,1,0,0],
[0,1,1,1,1],
[0,0,1,1,0],
[0,0,0,1,0],
[0,0,0,0,0]
]
# 이걸 노드로 바바
N = 5
# 연결된(상하좌우로) 1의 총 개수를 찾기.
# 행 우선 탐색을 하다가 1을 만나면 그때부터 연결된 거 다 찾기.
queue = [] #리스트지만 맨 뒤에 넣고 앞에서 뺄 꺼니까 큐
visited = [[0] * N for _ in range(N)] #2차원 배열에서 각 요소가 정점이므로 모든 정점에 대해서 방문 표시를 해야 함
# 시작점 정해주기
for i in range(N):
    for j in range(N):
        if arr[i][j]: #arr에 1을 찾아서
            # 요 시점에서 bfs를 시작
            queue.append((i,j,0)) # 큐에 시작점 넣어주기 ,(좌료, 거리)
            visited[i][j] = 1 # 방문 표시해서 재방문 방지
            # 현재 위치에서 갈 수 있는 모든 경로 탐색
            # 경로를 발견하면 저장하고 (enqueue)
            # 이후에 경로를 발견한 순서대로 다시 방문
            cnt = 0
            while queue: # 큐에 저장된 노드를 방문하는 작업을 반복(큐가 있을 때까지)
                # 현재 위치/
                ci,cj,distance = queue.pop(0) # 젤 앞에 있는 거 빼기, 방문했다는 뜻
                # 네 방향 다 살펴보기
                cnt += 1
                for di,dj in ([(-1,0),(1,0),(0,-1),(0,1)]):
                    next_i, next_j = ci + di, cj +dj #내가 갈려고 하는 위치
                    if 0 <= next_i <=N and 0 <= next_j <N: # 범위 지정
                        if arr[next_i][next_j] and not visited[next_i][next_j]:
                            # 1이고, 방문하지 않았으면.
                            queue.append((next_i,next_j,distance+1))
                            visited[next_i][next_j] = 1
            # 반복문이 끝나는 지점
            print(cnt)