수테크📱⌚️👀

문제😂

bfs(V, E, R) {  # V : 정점 집합, E : 간선 집합, R : 시작 정점
    for each v ∈ V - {R}
        visited[v] <- NO;
    visited[R] <- YES;  # 시작 정점 R을 방문 했다고 표시한다.
    enqueue(Q, R);  # 큐 맨 뒤에 시작 정점 R을 추가한다.
    while (Q ≠ ∅) {
        u <- dequeue(Q);  # 큐 맨 앞쪽의 요소를 삭제한다.
        for each v ∈ E(u)  # E(u) : 정점 u의 인접 정점 집합.(정점 번호를 오름차순으로 방문한다)
            if (visited[v] = NO) then {
                visited[v] <- YES;  # 정점 v를 방문 했다고 표시한다.
                enqueue(Q, v);  # 큐 맨 뒤에 정점 v를 추가한다.
            }
    }
}

내 풀🦷

# 24444. 알고리즘 수업 - 너비 우선 탐색1
from collections import deque # 요거 안하고 그냥 stack으로 하면 에러 나요...
import sys  
input = sys.stdin.readline

def bfs(R, V): # V: 정점 개수, E 간선, R : 시작 정점
    global visited
    visited = [0] * (V+1)
    q = deque([R])   # deque = deque() => 비어있는 큐 만들기
    visited[R] = 1
    order = 1   # 몇번째인지 알기위해서 순서를 1로 초기화해주고
    while q:
        t = q.popleft() # pop(0)
        # num[t].sort()
        for i in num[t]:
            # for i in sorted(num[t]): #sorted를 쓸꺼면 이렇게!!!
            if visited[i] == 0:
                q.append(i)
                order += 1 # 찾을떄마다 순서를 1씩 더해준다
                visited[i] = order


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

for _ in range(M):
    v1, v2 = map(int, input().split())
    num[v1].append(v2)
    num[v2].append(v1)

for k in num:
    k.sort()

bfs(R, N)

for s in visited[1::]:
    print(s)

문제 풀면서 어려웠던 점...

1. 시간초과 => import collections import deque와 import sys로 해결!!

- deque와 stack과 다른 점들... 

• deque = deque() => 비어 있는 큐 만들어주기  (stack은 q = [])
• popleft() => 제일 첫 값 빼주기 (stack은 pop(0))

2. 오름차순으로 뽑아 입력받은것들을 오름차순으로 정렬 (나는 입력 받은 순 고대로 만들어서 계속 정답이 안 나왔다...)

• num[t].sort()
• for i in sorted(num[t])
• for k in num: k.sort() .... 등등 여러 방법이 있다(이차원 배열이라 쉽지않음..)

참고하면 좋을 개념들 ✍️

1) BFS(너비우선탐색)

: 그래프와 트리의 가까운 노드부터 탐색하는 알고리즘.. 큐의 자료구조를 이용

- 동작과정

• 탐색 시작 노드를 큐에 삽입하고 방문 처리
• 큐에서 노드를 꺼내 해당 노드의 인접 노드 중 방문하지 않은 곳을 큐에 삽입하고 방문처리
• 큐가 없어질 때까지 반복!!

def bfs(s, V): # 시작 정점 s, 마지막 정점 V
    # visited 생성 => 이 순서 기억하기!!!!!
    visited = [0] * (V + 1)
    # 큐생성
    q = []  # 이 타이밍에 q = [s] 해도 됩니당
    # 시작점 인큐
    q.append(s)
    # 시작점 방문 표시
    visited[s] = 1
    while q: # 큐에 정점이 남아있으면 계속 진행... (front != rear 라고도 사용가능!! 같으면 빈거니까
        t = q.pop(0) # 디큐, 앞에서 뽑아야겟쥬
        print(t)    # 방문한 정점에서 할일
        # 인접한 정점 중 인큐되지 않은 정점 w가 있으면
        for w in adj_l[t]:
            if visited[w] == 0:
                # w를 인큐, 인큐 되었음을 표시
                q.append(w)
                # visited[w] = 1
                visited[w] = visited[t] + 1 #### 최소거리를 구할 때 좋아용 ###
    # print(visited[1:])

저희 시험이 import를 사용할 수 가 없어가지구...

문제 풀때 deque를 쓰지 않아 생소한데요... 데크 쓰는 법은 👇👇

from collections import deque

def bfs(start):
    global graph, visited
    
    queue = deque([start]) # 시작점을 큐에 넣어줍니다
    visited[start] = True  # 방문 표시를 해줍니다
    
    while queue: # 큐에 남아있는 값이 없을 떄까지 반복!!
        v = queue.popleft() # 큐의 첫번째 값을 빼옵니다
        print(v, end = '') # 어떤 경로로 방문했는지 적어줍니다
        
        for i in graph[v]:  # v에 인접한 곳을 돌면서
            if not visited[i]: # 방문하지 않았다면
                queue.append(i) # 큐에 넣어주고
                visited[i] = True # 방문 표시를 해줍니다

bfs(1) # 1은 그냥 시작점 예를 1로 든거..