Tag: graph traversal

def distance(x1, y1, x2, y2, r_squared):
    dist_sq = (x2 - x1) ** 2 + (y2 - y1) ** 2
    return dist_sq <= r_squared

def solve():

    N, R, D, X, Y = map(int, input().split())

    graph = [[0, 0]]
    for _ in range(N):
        graph.append(list(map(float, input().split())))

    v = [False] * (N + 1)
    
    q = deque([(X, Y, 0)])
    
    result = 0.0
    
    r_sq = R * R

    while q:
        cur_x, cur_y, count = q.popleft()

        for i in range(1, N + 1):
            target_x, target_y = graph[i]

            if not v[i] and distance(cur_x, cur_y, target_x, target_y, r_sq):
                v[i] = True

                result += (D / (2 ** count))
                
                q.append((target_x, target_y, count + 1))

    print(result)
solve()

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)

def bfs(n):
    q = deque([1])
    while q:
        cur = q.popleft()
        for n_num in (cur * 10 + 0, cur * 10 + 1):
            if len(str(n_num)) > 100:
                continue
            
            if n_num % n == 0:
                return n_num
            q.append(n_num)

while True:
    n = int(input())
    if n == 0:
        break

    print(bfs(n))

O(2^100) (worst case, but pruned by modulo check)

input = sys.stdin.readline

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

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

def bfs(start):
    q = deque([(start, 0)])
    visited = [-1] * (N + 1)
    visited[start] = 0
    
    while q:
        cur_node, d = q.popleft()
        for n_node in graph[cur_node]:
            if visited[n_node] != -1:
                continue
            visited[n_node] = d + 1
            q.append((n_node, d + 1))

    return visited[1:]

print(*bfs(R), sep='\n')

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)

field = list(map(list, [input() for _ in range(12)]))

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

def bfs(sy, sx):
    visited = set()
    q = [(sy, sx)]
    visited.add((sy, sx))
    while q:
        y, x = q.pop(0)
        for dy, dx in dyx:
            ny, nx = y + dy, x + dx
            if not(0 <= ny < 12 and 0 <= nx < 6):
                continue
            if (ny, nx) in visited:
                continue
            
            if field[ny][nx] == field[sy][sx]:
                visited.add((ny, nx))
                q.append((ny, nx))
    
    if len(visited) >= 4:
        for y, x in visited:
            field[y][x] = '.'
        return True
    return False

cnt = 0
while True:
    is_remove = False
    for i in range(12):
        for j in range(6):
            if field[i][j] == '.':
                continue

            if bfs(i, j):
                is_remove = True

    if not is_remove:
        break

    # 블록 내리기
    for j in range(6):
        stack = []
        for i in range(11, -1, -1):
            if field[i][j] == '.':
                continue
            
            stack.append(field[i][j])
            field[i][j] = '.'
        
        i = 11
        while stack:
            field[i][j] = stack.pop(0)
            i -= 1

    cnt += 1

print(cnt)

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

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

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


def bfs(x, y):
    q = deque([(x, y)])

    while q:
        x, y = q.popleft()

        for dx, dy in dxy:
            nx, ny = x + dx, y + dy

            nx %= N
            ny %= M

            if grid[nx][ny] == 1:
                continue

            grid[nx][ny] = 1
            q.append((nx, ny))

    return 1


result = 0

for x in range(N):
    for y in range(M):
        if grid[x][y] == 1:
            continue

        result += bfs(x, y)

print(result)

R, C = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(R)]

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

visited = [[False] * C for _ in range(R)]

q = deque()
for i, floor in enumerate(grid[0]):
    if floor == 1:
        q.append([0, i, 0])
        visited[0][i] = True

result = -1
while q:
    x, y, t = q.popleft()
    
    if x == R - 1:
        result = t
        break
    
    for dx, dy in dxy:
        nx, ny = x + dx, y + dy
        if not(0 <= nx < R and 0 <= ny < C):
            continue
        if grid[nx][ny] == 0 or visited[nx][ny]:
            continue
        
        q.append([nx, ny, t + 1])
        visited[nx][ny] = True

print(result)

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

dxy = ((1, 2), (2, 1), (-1, 2), (2, -1), (1, -2), (-2, 1), (-1, -2), (-2, -1))

x, y = map(int, input().split())

enemy_list = [tuple(map(int, input().split())) for _ in range(M)]
result = [0] * M

q = deque([(x, y, 1)])
find_cnt = 0
visited = set([(x, y)])

while q:
    cur_x, cur_y, t = q.popleft()

    for dx, dy in dxy:
        n_x, n_y = cur_x + dx, cur_y + dy
        if (n_x, n_y) in visited:
            continue
        if (n_x, n_y) in enemy_list:
            enemy_idx = enemy_list.index((n_x, n_y))
            if result[enemy_idx] != 0:
                continue
            result[enemy_idx] = t
            find_cnt += 1
        if find_cnt == M:
            break
        q.append((n_x, n_y, t + 1))
        visited.add((n_x, n_y))
    else:
        continue
    break

print(*result)