[코테 준비 : day21]

재밌는데? 재밌다고 생각해야겠는데?

요즘은 에이블스쿨에서 진행하는 코딩마스터스가 끝나고 백준 문제를 푸는 중이다🔥코딩마스터스 2차도 있다고하여 그 때는 80문제 이상을 풀기위해! 멀리 보면 취업을 위한 코테를 위해! 코테준비? 재밌다고 생각해야겠는데?😝

1. DFS와 BFS
   https://www.acmicpc.net/problem/1260
   
   이 문제는 DFS, BFS의 특성을 이해하고, 비교하기에 좋았다!

rdef bfs(V):
    q = deque([V])  # pop메서드의 시간복잡도가 낮은 덱 내장 메서드를 이용한다
    visited2[V] = True  # 해당 V 값을 방문처리
    while q:  # q가 빌때까지 돈다.
        V = q.popleft()  # 큐에 있는 첫번째 값 꺼낸다.
        print(V, end=" ")  # 해당 값 출력
        for i in range(1, N + 1):  # 1부터 N까지 돈다
            if not visited2[i] and graph[V][i]:  # 만약 해당 i값을 방문하지 않았고 V와 연결이 되어 있다면
                q.append(i)  # 그 i 값을 추가
                visited2[i] = True  # i 값을 방문처리

def dfs(V):
    visited1[V] = True  # 해당 V값 방문처리
    print(V, end=" ")
    for i in range(1, N + 1):
        if not visited1[i] and graph[V][i]:  # 만약 i값을 방문하지 않았고 V와 연결이 되어 있다면
            dfs(i)  # 해당 i 값으로 dfs를 돈다.(더 깊이 탐색)

 
from collections import deque

N, M, V = map(int, input().split())

graph = [[False] * (N + 1) for _ in range(N + 1)]

for _ in range(M):
    a, b = map(int, input().split())
    graph[a][b] = True
    graph[b][a] = True

visited1 = [False] * (N + 1)  # dfs의 방문기록
visited2 = [False] * (N + 1)  # bfs의 방문기록

dfs(V)
print()
bfs(V)

2. MooTube (Silver)
   https://www.acmicpc.net/problem/15591
   
   이 문제는 DFS, BFS의 특성을 이해하고 적용시키기에 좋았던 문제다!

from sys import stdin
from collections import deque, defaultdict
input = stdin.readline

def bfs(k, v):
    num = 0
    q = deque([v])
    vi = [0] * (N + 1)
    vi[v] = 1 
    
    while q:
        v= q.popleft()
        for nv, nw in graph[v]:
            if vi[nv] == 0 and nw >= k:
                vi[nv] = 1
                q.append(nv)
                num += 1
    return num

N, Q = map(int, input().split())

graph = defaultdict(list)

for _ in range(N-1):
    p,q,r = map(int, input().split())
    graph[p].append([q,r])
    graph[q].append([p,r])

for _ in range(Q):
    k, v = map(int ,input().split())
    print(bfs(k, v))