from collections import defaultdict, deque

INF = float('inf')

def floyd(n, dist_list):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist_list[i][j] = min(dist_list[i][j], dist_list[i][k] + dist_list[k][j])

    min_sum = INF
    result = 0
    for i, sum_dist in enumerate(map(sum, dist_list), start=1):
        if min_sum > sum_dist:
            min_sum = sum_dist
            result = i

    return result

def main():
    N, M = map(int, input().split())

    dist_list = [[INF] * N for _ in range(N)]
    for i in range(0, N):
        dist_list[i][i] = 0

    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        dist_list[a][b] = 1
        dist_list[b][a] = 1
    
    print(floyd(N, dist_list))


if __name__ == "__main__":
    main()

INF = float("inf")


def floyd(n, dist_list):
    """플로이드 워셜"""

    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                dist_list[i][j] = min(
                    dist_list[i][j], dist_list[i][k] + dist_list[k][j]
                )

    return dist_list


def print_result(dist_list):
    """결과 출력"""
    for dist in dist_list[1:]:
        for d in dist[1:]:
            print(d if d != INF else 0, end=" ")
        print()


def main():
    n = int(input())
    m = int(input())

    dist_list = [[INF] * (n + 1) for _ in range(n + 1)]

    for _ in range(m):
        a, b, c = map(int, input().split())
        dist_list[a][b] = min(dist_list[a][b], c)

    for i in range(1, n + 1):
        dist_list[i][i] = 0

    dist_list = floyd(n, dist_list)
    print_result(dist_list)


if __name__ == "__main__":
    main()

첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N)

둘째 줄부터 M개의 줄에 걸쳐서 두 개의 자연수 A, B가 공백을 기준으로 구분되어 주어진다. 이는 A번 도시에서 B번 도시로 이동하는 단방향 도로가 존재한다는 의미다. (1 ≤ A, B ≤ N)

출력

X로부터 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 K인 모든 도시의 번호를 한 줄에 하나씩 오름차순으로 출력한다.

이 때 도달할 수 있는 도시 중에서, 최단 거리가 K인 도시가 하나도 존재하지 않으면 -1을 출력한다.

단방향 그래프에서 특정 노드로부터의 최단 거리를 구하는 문제이다. 모든 간선의 가중치가 1이므로 BFS 또는 다익스트라로 해결할 수 있다.

import heapq
from collections import defaultdict

INF = float("inf")

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

graph = defaultdict(list)

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


def dijkstra(start):
    dist_list = [INF] * (N + 1)
    dist_list[start] = 0
    q = [(0, start)]

    while q:
        dist, cur_node = heapq.heappop(q)
        if dist_list[cur_node] < dist:
            continue

        for n_node in graph[cur_node]:
            if dist + 1 < dist_list[n_node]:
                dist_list[n_node] = dist + 1
                heapq.heappush(q, (dist + 1, n_node))

    return dist_list


inf_cnt = 0
for node, dist in enumerate(dijkstra(X)[1:], start=1):
    if dist == K:
        print(node)
    else:
        inf_cnt += 1

if inf_cnt == N:
    print(-1)

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

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

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