Tag: dfs

N, M = map(int, input().split())
grid = [list(input().strip()) for _ in range(M)]
visited = set()

dxy = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def bfs(x, y, team):
    q = deque([(x, y)])
    visited.add((x, y))
    count = 1
    
    while q:
        x, y = q.popleft()
        
        for dx, dy in dxy:
            nx, ny = x + dx, y + dy
            
            if not(0 <= nx < M and 0 <= ny < N):
                continue
            if (nx, ny) in visited:
                continue
            if grid[nx][ny] != team:
                continue
            visited.add((nx, ny))
            q.append((nx, ny))
            count += 1
    return count

white_power = 0
blue_power = 0

for i in range(M):
    for j in range(N):
        if (i, j) in visited:
            continue
        team = grid[i][j]
        count = bfs(i, j, team)
        if team == 'W':
            white_power += count ** 2
        else:
            blue_power += count ** 2

print(white_power, blue_power)

from collections import defaultdict, deque

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

taller = defaultdict(list)
shorter = defaultdict(list)

for _ in range(M):
    a, b = map(int, input().split())
    taller[a].append(b)
    shorter[b].append(a)

def bfs(graph, start):
    visited = set()
    q = deque([start])
    while q:
        node = q.popleft()
        for n in graph[node]:
            if n not in visited:
                visited.add(n)
                q.append(n)
    return visited

result = 0
for i in range(1, N+1):
    visited_taller = bfs(taller, i)
    visited_shorter = bfs(shorter, i)
    # 앞 뒤의 키를 모두 탐색 가능할 경우
    if len(visited_taller) + len(visited_shorter) == N - 1:
        result += 1

print(result)

• 각 컴퓨터마다 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)

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')

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.")

첫째 줄에 동영상의 개수 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를 수행하며, 각 노드까지의 경로에서의 최소값을 유지하면서 탐색한다.

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

test_case = int(input())

def chk_test():
    chk_a_list = [0] * k
    chk_b_list = [1] * k

    for w_i in range(w):
        is_success = False

        for d_i in range(d - k + 1):
            cur_chk = [film[tmp_i][w_i] for tmp_i in range(d_i, d_i + k)]
            if cur_chk == chk_a_list or cur_chk == chk_b_list:
                is_success = True
                break
        if not is_success:
            return False
    return True


def test_film(film, depth=0, cnt_inject=0, chk_list=[]):
    global min_inject
    
    if cnt_inject >= min_inject:
        return

    if chk_test():
        min_inject = min(min_inject, cnt_inject)
        return

    if depth >= d:
        return
    
    origin_membrane = film[depth][:]

    # 현재 층을 그대로
    test_film(film, depth + 1, cnt_inject)

    # 현재 층을 a로
    film[depth] = inject_a
    test_film(film, depth + 1, cnt_inject + 1)
    film[depth] = origin_membrane

    # 현재 층을 b로
    film[depth] = inject_b
    test_film(film, depth + 1, cnt_inject + 1)
    film[depth] = origin_membrane

for t in range(test_case):
    d, w, k = map(int, input().split())

    film = [list(map(int, input().split())) for _ in range(d)]
    
    inject_a = [0] * w
    inject_b = [1] * w

    min_inject = float('inf')

    test_film(film)
    print(f"#{t + 1} {min_inject}")

def max_subset_sum(arr):
    dp = [[0, 0] for _ in range(c + 1)]

    for num in arr:
        for j in range(c, num - 1, -1):
            if dp[j - num][0] + num > c:
                continue
            next_sq_value = dp[j - num][1] + num ** 2
            if next_sq_value > dp[j][1]:
                dp[j][0] = dp[j - num][0] + num
                dp[j][1] = next_sq_value
    _, max_sum = max(dp, key=lambda x: x[1])
    return max_sum

test_case = int(input())

for t in range(test_case):
    n, m, c = map(int, input().split())
    honey_map = [list(map(int, input().split())) for _ in range(n)]
    total_max = 0

    for fst_i in range(n):
        for fst_j in range(n - m + 1):

            fst_max = max_subset_sum(honey_map[fst_i][fst_j:fst_j + m])

            for snd_i in range(n):
                start = 0
                if snd_i == fst_i:
                    start = fst_j + m
                for snd_j in range(start, n - m + 1):
                    snd_max = max_subset_sum(honey_map[snd_i][snd_j:snd_j + m])

                    total_max = max(total_max, fst_max + snd_max)

    print(f"#{t + 1} {total_max}")