DFS와 BFS

백준 1260 DFS와 BFS

# DFS 함수 정의
def dfs(graph, v, visited):
    # 현재 노드를 방문 처리
    visited[v] = True
    print(v, end=' ')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in sorted(graph[v]):
        if not visited[i]:
            dfs(graph, i, visited)

from collections import deque
# BFS 함수 정의
def bfs(graph, start, visited):
    # 큐(Queue) 구현을 위해 deque 라이브러리 사용
    queue = deque([start])
    # 현재 노드를 방문 처리
    visited[start] = True
    # 큐가 빌 때까지 반복
    while queue:
        # 큐에서 하나의 원소를 뽑아 출력
        v = queue.popleft()
        print(v, end=' ')
        # 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
        for i in sorted(graph[v]):
            if not visited[i]:
                queue.append(i)
                visited[i] = True

n, m, v = map(int, input().split())
graph = [[] for _ in range(1001)]
visited = [False]*1001

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

graph1 = graph.copy()
visited1 = visited.copy()

dfs(graph, v, visited)
print('')
bfs(graph1, v, visited1)

1. 전역변수를 함수안에 넣으면 지역변수가 되서 같은 객체를 DFS,BFS함수에 똑같이 넣어도 될 것 같았는데 함수내에서 변경한 것이 적용되서 copy해서 넣었다.
2. 노드가 연결된 관계를 만들때 양방향으로 다 넣어줘야한다.

dfs, bfs코드는 동빈나 코드를 참고했습니다.

SWEA 1865. 동철이의 일 분배

def permutation(result, depth, n):
    global max_value
    if result <= max_value:
        return
    elif depth == n and result>max_value:
        max_value = result
        return
    else:
        for i in range(n):
            if not visited[i]:
                visited[i] = True
                new_result = result*table[depth][i]*0.01
                permutation(new_result, depth+1, n)
                visited[i] = False

test = int(input())
for t in range(test):
    n = int(input())
    table = [list(map(int, input().split())) for _ in range(n)]
    visited = [False]*n
    max_value = -1
    permutation(1, 0, n)
    print('#{} {}'.format(t+1, format(max_value*100, '.6f')))

참고코드

1. 순열을 구하는 문제라고 볼 수 있다.
2. 단순히 순열을 구하는 문제와 다른 점은 순열만 구하는 것이 아니라 순열의 요소끼리 곱해서 최댓값을 구해야 한다.
3. 순열을 구하는 백준 N과 M 문제 코드에서 앞으로 돌아가는 조건을 더 추가해주면 된다.(말은 쉽지만 막상 생각해내려면 어렵드아,,)