graph 문제 모음

나이트의 이동 (7562)

from collections import deque

def bfs(start, goal, n):
    queue = deque([(start[0], start[1], 0)])
    visited = set([start])

    directions = [(2, 1), (2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2), (-2, 1), (-2, -1)]

    while queue:
        r, c, count = queue.popleft()
        # you need to keep track of count (~path), and return that,
        # Not visited <- its all nodes visited, not found shortest path
        if r == goal[0] and c == goal[1]:
            return count

        for direction in directions:
            next_r, next_c = r + direction[0], c + direction[1]
            if 0 <= next_r < n and 0 <= next_c < n:
                if (next_r, next_c) not in visited:
                    visited.add((next_r, next_c))
                    queue.append((next_r, next_c, count + 1))
    # if not found
    return -1


tests = int(input())

for _ in range(tests):
    n = int(input())
    current_r, current_c = map(int, input().split())
    goal_r, goal_c = map(int, input().split())
    print(bfs((current_r, current_c), (goal_r, goal_c), n))

숨바꼭질 (1697)

from collections import deque

n, k = map(int, input().split())

def bfs_solver(n, k):

    queue = deque([(n , 0)])
    visited = set([n])

    while queue:
        loc, time = queue.popleft()

        # check if current state is the goal_state
        if loc == k:
            return time

        for next_loc in (loc + 1, loc - 1, loc * 2):
            if 0 <= next_loc <= 100000 and next_loc not in visited:
                queue.append((next_loc, time + 1))
                visited.add(next_loc)

    return -1

result = bfs_solver(n, k)
print(result)

뱀과 사다리 게임 (16928)

from collections import deque

ladder_total, snake_total = map(int, input().split())
events = {}

for _ in range(ladder_total):
    cur, new = map(int, input().split())
    events[cur] = new
for _ in range(snake_total):
    cur, new = map(int, input().split())
    events[cur] = new

def bfs(start, end, events):
    queue = deque([(start, 0)])
    visited = set([start])

    possible_dice = [1, 2, 3, 4, 5, 6]

    while queue:
        current, count = queue.popleft()
        # check if meets goal
        if current == end:
            return count

        for dice in possible_dice:
            next_position = current + dice

            # Skip positions beyond the board
            if next_position > end:
                continue

            if next_position in events:
                next_position = events[next_position]
            if next_position not in visited:
                visited.add(next_position)
                queue.append((next_position, count + 1))
    return -1

print(bfs(1, 100, events))

OR

from collections import deque

def preprocess_board(ladders, snakes):
    # Create a direct access board where each position points to itself initially
    board = list(range(101))  # since positions are 1 to 100
    for start, end in ladders:
        board[start] = end
    for start, end in snakes:
        board[start] = end
    return board

def bfs(start, end, board):
    queue = deque([start])
    visited = set([start])
    depth = 0

    while queue:
        for _ in range(len(queue)):
            current = queue.popleft()

            if current == end:
                return depth

            for dice_roll in range(1, 7):
                next_pos = current + dice_roll
                if next_pos > end:
                    continue

                final_pos = board[next_pos]
                if final_pos not in visited:
                    visited.add(final_pos)
                    queue.append(final_pos)

        depth += 1

    return -1

# Example usage
ladders = [(input pairs)]
snakes = [(input pairs)]
board = preprocess_board(ladders, snakes)
print(bfs(1, 100, board))

벽 부수고 이동하기 (2206)

from collections import deque
n, m = map(int, input().split())
grid = []

for _ in range(n):
    row = input().strip()
    grid.append([int(char) for char in row])

# visited = [[False] * m] * n
# above does not create independent sublist for each row, but creates multiple references to the same list
# which means modifying one row's visited status will modify all rows
# visited = [[False] * m for _ in range(n)]

# We have to add with or without wall breaking to track visits
# 1st True/ False = 부수지않고 도착하거나 아직 안부수고 도착하지 않음
# 2nd True/False = 부수고 도착하거나 아직 그 부수고 도착하지 않음

visited = [[[False, False] for _ in range(m)] for _ in range(n)]

def bfs(grid, n, m, visited):
    queue = deque([(0, 0, 1, False)]) # row, col, count, wallBroken
    # 0 -> no break 1-> break
    visited[0][0][0] = True # visited (0,0) without breaking a wall

    directions = [(0,1), (1,0), (0,-1), (-1,0)]
    while queue:
        row, col, count, wallbroken = queue.popleft()

        if row == n-1 and col == m-1:
            return count

        for dr, dc in directions:
            new_row, new_col = row + dr, col + dc
            if 0 <= new_row < n and 0 <= new_col < m:

                # if you can move -> 0 OR you can break it and move
                if grid[new_row][new_col] == 0 and not visited[new_row][new_col][1 if wallbroken else 0]:
                    visited[new_row][new_col][1 if wallbroken else 0] = True
                    queue.append((new_row, new_col, count + 1, wallbroken))

                # if you can NOT move -> 1 & not already broken
                # then break it and move
                elif grid[new_row][new_col] == 1 and not wallbroken and not visited[new_row][new_col][1]:
                    visited[new_row][new_col][1] = True
                    queue.append((new_row, new_col, count + 1, True))
    return -1

print(bfs(grid, n, m, visited))

Visited 가 벽을 부수지 않은 상태 와 부순 상태 둘다 저장한다

Queue 는 position 과 count 이외에도 wallbroken boolean variable 를 통해 한번이라도 부서졌는지 아닌지를 저장한다. 그에따라 if 문은 2가지로 나뉘게 된다.