첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)이 주어진다. 둘째 줄에는 A₁, A₂, …, Aₙ이 주어진다. (1 ≤ Aᵢ ≤ 100) 셋째 줄에는 덧셈, 뺄셈, 곱셈, 나눗셈의 개수가 순서대로 주어진다.

출력

첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력한다.

이 문제는 백트래킹을 이용한 브루트포스 문제이다. 가능한 모든 연산자 조합을 시도하여 최대값과 최소값을 찾는다.

1. DFS를 이용하여 모든 연산자 배치 조합을 탐색
2. 각 단계에서 사용 가능한 연산자를 선택하고 계산
3. 모든 수를 사용했을 때 결과를 비교하여 최대/최소 갱신

• 현재 결과값과 사용할 다음 수를 가지고 재귀
• 각 연산자 종류별로 남은 개수가 있으면 시도
• 연산 후 다음 단계로 진행
• 백트래킹: 연산자 개수 복구

operate = ['+', '-', '*','/']

N = int(input())
nums = list(map(int, input().split()))
operator_counter = list(map(int, input().split()))
operator_cnt = sum(operator_counter)

max_com = -float('inf')
min_com = float('inf')


def compute(a, b, op_i):
    if op_i == 0:
        return a + b
    elif op_i == 1:
        return a - b
    elif op_i == 2:
        return a * b
    elif op_i == 3:
        return int(a / b)

def dfs(operator_counter, result, n=0):
    global max_com, min_com
    if n == operator_cnt:
        max_com = max(max_com, result)
        min_com = min(min_com, result)
        return
    for i, cnt in enumerate(operator_counter):
        if cnt == 0:
            continue
        operator_counter[i] -= 1
        dfs(operator_counter, compute(result, nums[n+1], i), n+1)
        operator_counter[i] += 1


dfs(operator_counter, nums[0])

print(max_com)
print(min_com)

1. (0, 0)에서 시작
2. 오른쪽(→), 아래(↓) 방향으로만 이동
3. 값이 1인 칸만 이동 가능
4. (M-1, N-1)에 도달하면 성공

from collections import deque

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

space = [list(map(int, input().split())) for _ in range(M)]

dyx = ((1, 0), (0, 1))

q = deque([(0, 0)])
visited = set([(0, 0)])

is_possible = False

if N == 1 and M == 1:
    is_possible = True

while q:
    y, x = q.popleft()
    for dy, dx in dyx:
        ny, nx = y + dy, x + dx
        if not(0 <= ny < M and 0 <= nx < N):
            continue
        if space[ny][nx] == 0:
            continue
        if (ny, nx) in visited:
            continue
        if (ny, nx) == (M - 1, N - 1):
            is_possible = True
            break

        q.append((ny, nx))
        visited.add((ny, nx))
    else:
        continue
    break

# print(visited)
print('Yes' if is_possible else 'No')

m = int(input())
s = 0  # 비트마스크

for _ in range(m):
    command = input().strip().split()
    
    if command[0] == 'add':
        x = int(command[1])
        s |= (1 << x)
    elif command[0] == 'remove':
        x = int(command[1])
        s &= ~(1 << x)
    elif command[0] == 'check':
        x = int(command[1])
        print(1 if s & (1 << x) else 0)
    elif command[0] == 'toggle':
        x = int(command[1])
        s ^= (1 << x)
    elif command[0] == 'all':
        s = (1 << 21) - 1
    elif command[0] == 'empty':
        s = 0

class Network:

    def __init__(self, N, M):
        self.N, self.M = N, M
        self.cnt = 0
        self.visited = [False] * (N + 1)
        self.visited[1] = True
        self.network = defaultdict(list)
        self._make_network()

    def _make_network(self):
        for _ in range(self.M):
            s, e = map(int, input().split())
            self.network[s].append(e)
            self.network[e].append(s)

    def search_computer(self, node=1):
        for n_node in self.network[node]:
            if self.visited[n_node]:
                continue
            self.visited[n_node] = True
            self.cnt += 1
            self.search_computer(n_node)


def main():
    N = int(input())
    M = int(input())

    network = Network(N, M)
    network.search_computer()
    print(network.cnt)


if __name__ == "__main__":
    main()

for i in range(1, n + 1):
    if not visited[i]:
        nodes = set()
        edges = set()

        # 사이클 확인
        if not dfs(i, 0, nodes, edges):
            continue

        # 사이클이 없고, 간선의 수가 노드의 수 - 1이면 트리
        if len(edges) == len(nodes) - 1:
            tree_count += 1

• 방문하지 않은 각 연결 요소에 대해 DFS 수행
• 사이클이 없고 간선 수 = 정점 수 - 1이면 트리로 카운트

if tree_count == 0:
    print(f"Case {case_num}: No trees.")
elif tree_count == 1:
    print(f"Case {case_num}: There is one tree.")
else:
    print(f"Case {case_num}: A forest of {tree_count} trees.")

def toggle_switch(switches, N, gender, num):
    if gender == 1:
        # 남학생은 스위치 번호가 자기가 받은 수의 배수이면, 그 스위치의 상태를 바꾼다.
        for i in range(num - 1, N, num):
            switches[i] = (switches[i] + 1) % 2
    else:
        # 여학생은 자기가 받은 수와 같은 번호가 붙은 스위치를 중심으로 좌우가 대칭이면서 가장 많은 스위치를 포함하는 구간을 찾아서, 그 구간에 속한 스위치의 상태를 모두 바꾼다.
        num -= 1
        switches[num] = (switches[num] + 1) % 2

        i = 1
        while num - i >= 0 and num + i < N:
            if switches[num - i] != switches[num + i]:
                break

            switches[num - i] = (switches[num - i] + 1) % 2
            switches[num + i] = (switches[num + i] + 1) % 2
            i += 1
    return switches

N = int(input())
switches = list(map(int, input().split()))

M = int(input())
for _ in range(M):
    gender, num = map(int, input().split())
    switches = toggle_switch(switches, N, gender, num)

for i in range(N // 20 + 1):
    print(*switches[i*20:(i + 1)*20])

첫째 줄에 동영상의 개수 N (1 ≤ N ≤ 5,000)과 질문의 개수 Q (1 ≤ Q ≤ 5,000)가 주어진다.

다음 N-1개의 줄에는 두 동영상을 연결하는 간선 정보 p, q, r이 주어진다. 이는 동영상 p와 동영상 q가 연관도 r로 연결되어 있음을 의미한다. (1 ≤ r ≤ 1,000,000,000)

다음 Q개의 줄에는 k, v가 주어진다. 이는 유사도가 k 이상인 동영상을 동영상 v를 기준으로 찾는 질의이다.

출력

Q개의 줄에 각 질문에 대한 답변을 출력한다.

이 문제는 트리 구조에서 특정 노드로부터 도달 가능한 노드들 중 경로상의 최소 가중치가 특정 값 이상인 노드의 개수를 세는 문제이다.

두 동영상 간의 유사도는 경로상의 최소 연관도이다. 따라서 시작 노드에서 BFS/DFS를 수행하며, 각 노드까지의 경로에서의 최소값을 유지하면서 탐색한다.

풀이 1: BFS를 이용한 방법

각 쿼리마다 BFS를 수행하여 유사도가 k 이상인 노드를 센다.

첫째 줄에 N, L, R이 주어진다. (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)

둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. (0 ≤ A[r][c] ≤ 100)

인구 이동이 발생하는 일수가 2,000번 보다 작거나 같은 입력만 주어진다.

출력

인구 이동이 며칠 동안 발생하는지 첫째 줄에 출력한다.

이 문제는 시뮬레이션과 BFS를 결합한 문제이다. 매일 국경선이 열리는 나라들을 찾아 연합을 만들고, 인구를 재분배하는 과정을 반복해야 한다.

인구 이동이 일어나는 하루는 다음과 같은 과정을 거친다:

1. 연합 찾기: BFS를 사용하여 국경선이 열리는 나라들의 연합을 찾는다.
2. 인구 재분배: 각 연합의 평균 인구수를 계산하고 재분배한다.
3. 종료 조건 확인: 어떤 연합도 만들어지지 않으면 인구 이동 종료.

1. 연합 찾기 (open 함수)

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

floor = [list(input()) for _ in range(N)]

def search_tiles(start, visited, tile_shape):
    # 타일 모양에 따라 탐색 방향 설정
    if tile_shape == '-':
        dy, dx = 0, 1
    else:
        dy, dx = 1, 0

    q = deque([start])
    while q:
        y, x = q.popleft()

        ny, nx = y + dy, x + dx

        # 범위 벗어났을 경우
        if not (0 <= ny < N) or not (0 <= nx < M):
            return 1
        # 이미 방문했을 경우
        if visited[ny][nx]:
            return 1
        # 타일 모양이 다를 경우
        if floor[ny][nx] != tile_shape:
            return 1

        q.append((ny, nx))
        visited[ny][nx] = True

visited = [[False] * M for _ in range(N)]
tile_cnt = 0

for y in range(N):
    for x in range(M):
        if visited[y][x]:
            continue
        tile_cnt += search_tiles((y, x), visited, floor[y][x])

print(tile_cnt)