220720 BOJ 2579, 9375, DFS와 BFS

DFS : 스택이나 재귀함수를 이용함

visited = [False] * (n+1)
def dfs(N):
    visited[N] = True
    print(N, end=" ")
    for i in graph[N]:
        if not visited[i]:
            dfs(i)

******BFS : 큐를 이용함

(노드 간 비용이 같을 때 최단 거리 측정 문제에서 자주 쓰인다고 한다!!)

1) 스타트를 True 처리 + 큐에 넣어주기

2) while que(큐가 빌 때까지 반복)

3) 스타트 값을 popleft해서 추출(넣고 바로 빼기)

4) graph에서 스타트와 인접한 값들 중 방문하지 않은 것이 있따면 큐에 넣어주고, 방문했다고 하고 반복

5) 그렇게 for문이 끝나면 그땐 새롭게 늘어난 큐 값들을 빨리 넣은 순서대로 다시 반복

(큐는 먼저 넣은 순서대로 나가기 때문에, popleft 하기 전에 큐에 자꾸 넣음)

from collections import deque
def bfs(n):
    visited[n] = True
    que = deque([n])
    while que:
        v = que.popleft()
        print(v, end=" ")
        for i in graph[v]:
            if not visited[i]:
                que.append(i)
                visited[i] = True

 

최종 정답 

#1260

# cook your dish here
from collections import deque

n,m,start=map(int,input().split())
visited = [False] * (n+1)

graph = [[] for _ in range(n+1)]

for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

for i in range(n+1):
    graph[i].sort()

def dfs(start):
    visited[start] = True
    print(start, end= " ")
    for i in graph[start]:
        if not visited[i]:
            dfs(i)

def bfs(start):
    visited[start] = True
    que = deque([start])
    while que:
        v = que.popleft()
        print(v, end=" ")
        for i in graph[v]:
            if not visited[i]:
                visited[i] = True
                que.append(i)
                
dfs(start)

visited = [False] * (n+1)

print("")
bfs(start)

 

#dp #2579 #계단오르기

n = int(input())
s = [0 for i in range(301)]
dp = [0 for i in range(301)]
for i in range(n):
    s[i] = int(input())
dp[0] = s[0]
dp[1] = s[0] + s[1]
dp[2] = max(s[0], s[1]) + s[2]
for i in range(3, n):
    dp[i] = max(dp[i-3] + s[i-1], dp[i-2]) + s[i]
print(dp[n-1])

#딕셔너리 #9375 #패션왕 신해미

t = int(input())

for i in range(t):
    n = int(input())
    weardict = {}
    for j in range(n):
        wear = list(input().split())
        if wear[1] in weardict:
            weardict[wear[1]].append(wear[0])
        else:
            weardict[wear[1]] = [wear[0]]
    
    cnt = 1
    
    for k in weardict:
        cnt = cnt * (len(weardict[k])+1)
    
    print(cnt-1)