• 각 컴퓨터마다 BFS: O(N + M)
• 전체 N개 컴퓨터: O(N × (N + M))
• N ≤ 10,000, M ≤ 100,000
• 최악의 경우: 10,000 × 110,000 = 1,100,000,000

시간 제한이 5초이고, 파이썬은 초당 약 1억 번 연산이 가능하므로 통과 가능하다.

시간이 빡빡할 경우 다음 최적화를 고려할 수 있다:

1. 빠른 입출력: sys.stdin.readline() 사용

2. DFS 대신 BFS: 재귀 오버헤드 감소

3. 조기 종료: 이미 방문한 노드 재탐색 방지

4. 역방향 그래프: A→B가 아닌 B→A로 저장

5. 자기 자신 포함: 해킹한 컴퓨터 자신도 카운트에 포함

6. 오름차순 출력: 여러 개일 경우 정렬 필요

7. 빠른 입출력: N, M이 크므로 필수

이 문제는 “신뢰 관계”를 반대로 생각해야 한다:

• “A가 B를 신뢰” ≠ A를 해킹하면 B도 해킹됨 (X)
• “A가 B를 신뢰” = B를 해킹하면 A도 해킹됨 (O)

def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])
    return parent[x]

def union(parent, a, b):
    a = find(parent, a)
    b = find(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

N, M = map(int, input().split())
truth = list(map(int, input().split()))
truth_num = truth[0]
truth_people = set(truth[1:])

parent = list(range(N + 1))
parties = []

for _ in range(M):
    party = list(map(int, input().split()))
    party_people = party[1:]
    parties.append(party_people)
    
    # 같은 파티 사람들을 union
    for i in range(len(party_people) - 1):
        union(parent, party_people[i], party_people[i + 1])

# 진실을 아는 사람들과 같은 그룹인지 확인
result = 0
for party in parties:
    can_lie = True
    for person in party:
        for truth_person in truth_people:
            if find(parent, person) == find(parent, truth_person):
                can_lie = False
                break
        if not can_lie:
            break
    if can_lie:
        result += 1

print(result)

import re

N = int(input())
room = [input() for _ in range(N)]

# 가로
row_cnt = sum(len(re.findall(r'\.{2,}', row)) for row in room)

# 세로
transposed = [''.join(row[i] for row in room) for i in range(N)]
col_cnt = sum(len(re.findall(r'\.{2,}', col)) for col in transposed)

print(row_cnt, col_cnt)

정규표현식 \.{2,}는 “연속된 2개 이상의 .”을 의미한다.

N, K = map(int, input().split())
distance = [float('inf')] * 100001

def bfs_01(start):
    dq = deque([(0, start)])
    distance[start] = 0
    
    while dq:
        dist, c = dq.popleft()
        
        if distance[c] < dist:
            continue
            
        # 비용 0인 간선 (순간이동)
        n = c * 2
        if 0 <= n <= 100000 and dist < distance[n]:
            distance[n] = dist
            dq.appendleft((dist, n))  # 앞에 추가
        
        # 비용 1인 간선 (걷기)
        for n in (c + 1, c - 1):
            if 0 <= n <= 100000 and dist + 1 < distance[n]:
                distance[n] = dist + 1
                dq.append((dist + 1, n))  # 뒤에 추가

bfs_01(N)
print(distance[K])

첫째 줄에 수의 개수 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')

SELECT ins.name, ins.datetime
FROM animal_ins AS ins
WHERE ins.animal_id NOT IN (
    SELECT animal_id
    FROM animal_outs
)
ORDER BY ins.datetime
LIMIT 3

문제에서 요구한 결과를 만들기 위해 쿼리에서 실제로 쓴 것들이다.

• WHERE 로 조건에 맞는 행만 남김
• ORDER BY 로 정렬
• LIMIT 3 으로 상위 3건만 조회
• 서브쿼리를 사용

SELECT ins.animal_id, ins.animal_type, ins.name
FROM animal_ins AS ins
JOIN
animal_outs AS outs
ON ins.animal_id = outs.animal_id
WHERE ins.sex_upon_intake REGEXP 'Intact' 
    AND outs.sex_upon_outcome REGEXP 'Spayed|Neutered'
ORDER BY ins.animal_id

문제에서 요구한 결과를 만들기 위해 쿼리에서 실제로 쓴 것들이다.

• 테이블 1회 JOIN 으로 두 테이블을 연결
• WHERE 로 조건에 맞는 행만 남김
• ORDER BY 로 정렬

SELECT a_in.animal_id, a_in.name
FROM animal_ins AS a_in
JOIN 
animal_outs AS a_out
ON a_in.animal_id = a_out.animal_id
where a_in.datetime > a_out.datetime
ORDER BY a_in.datetime

문제에서 요구한 결과를 만들기 위해 쿼리에서 실제로 쓴 것들이다.

• 테이블 1회 JOIN 으로 두 테이블을 연결
• WHERE 로 조건에 맞는 행만 남김
• ORDER BY 로 정렬