백준 2606번

1번째 문제 풀이(bfs)

from sys import stdin
from collections import deque

com = int(stdin.readline())
compair = int(stdin.readline())

graph = [[] for i in range(com + 1)]
visited = [0] * (com + 1)

for i in range(compair):
    com1, com2 = map(int, stdin.readline().split())
    graph[com1] += [com2]
    graph[com2] += [com1]
    
visited[1] = 1
queue = deque([1])

while queue:
    virus = queue.popleft()
    for nv in graph[virus]:
        if visited[nv] == 0:
            queue.append(nv)
            visited[nv] = 1
            
print(sum(visited)-1)

문제 풀이

bfs(너비 우선 탐색)을 이용하여 컴퓨터의 수와 컴퓨터 쌍의 수를 입력한 후 쌍의 수 만큼 입력을 받아서 양방향 연결을 시킵니다. 1번 컴퓨터를 방문 처리 하고 큐에 삽입 후 하나씩 꺼내 방문하지 않은 컴퓨터라면 큐에 추가하고 방문 처리를 해 반복을 하고 마지막으로 1번 컴퓨터를 제외한 방문한 컴퓨터 수를 출력합니다.

2번째 문제 풀이(union find)

from sys import stdin


def init_parent(parent, count) -> None:
    for i in range(count + 1):
        parent.append(i)


def find_parent(parent, node) -> int:
    if parent[node] == node:
        return node
    parent[node] = find_parent(parent, parent[node])
    return parent[node]


def has_same_parent(parent, a, b) -> bool:
    return find_parent(parent, a) == find_parent(parent, b)


def unite_parent(parent, a, b) -> None:
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b


def main() -> None:
    link_to: list[int] = []
    computer_count = int(stdin.readline())
    connection_count = int(stdin.readline())

    init_parent(link_to, computer_count)
    for _ in range(connection_count):
        from_x, to_y = map(int, stdin.readline().split())
        unite_parent(link_to, from_x, to_y)
        # print(link_to)
        # print()

    count = sum(
        1 for i in range(2, computer_count + 1) if has_same_parent(link_to, 1, i)
    )
    print(count)


if __name__ == "__main__":
    main()

문제 풀이 union-find를 사용하여 문제를 풀기위해 기본 연산을 정의한다.

find(find_parent) same(has_same_parent) unite(unite_parent)

union-find, 서로소 집합의 자료 구조로 사용하기 위해 컴퓨터(node)의 개수 만큼 배열을 선언하며, 각각의 index의 요소가 자기자신을 가리키도록 한다.

입력 받은 각 노드를 연결시킨다. 이때 unite를 사용하여 동일한 집합에 속함을 의미하도록 값을 저장한다. 이때 find를 수행할 때 경로 압축을 통해 배열의 대표값을 가리키게된다.

[!info] union-find를 사용할 경우 각 배열이 요소가 가리키는 값은 각 노드가 속하는 집합의 대표값이 된다.

집합에 속한 노드의 연결성이 보장되었으므로, 1번(노드)을 제외한 모든 요소(노드)에 대하여 same을 통해 해당 노드가 1번 컴퓨터와 연결된 집합에 속하는지 확인하며, 동일한 집합에 속하는 경우 count를 증가시킨다.

계산된 count 값이 정답이 된다.

백준 16928번

from sys import stdin
from collections import deque


roll_count = 0
board = [location for location in range(101)]
visited = [False]*101

def bfs(start_num):
    visited[start_num] = True
    q = deque()
    q.append((start_num,0))
    while len(q) > 0:
        now_location,now_roll_count = q.popleft()
        if now_location == 100:
            return now_roll_count
        for dice_eye in range(1,6+1):
            if now_location + dice_eye <= 100 and not visited[now_location + dice_eye]:
                visited[now_location+dice_eye] = True
                visited[board[now_location+dice_eye]] = True
                q.append((board[now_location+dice_eye],now_roll_count+1))

n,m = map(int,stdin.readline().strip().split())

for i in range(n):
    start,end = map(int,stdin.readline().strip().split())
    board[start] = end
for i in range(m):
    start,end = map(int,stdin.readline().strip().split())
    board[start] = end
print(bfs(1))

문제 풀이

기본적인 bfs, 주사위 눈 1..6 고려해서 진행, board가 뱀, 사다리면 도착점 위치로 지정 후 이동, 현재 위치가 100일 때 주사위 수 반환 (단, 큐에 푸시할 때 방문했음을 현재 점과 이동 점의 방문을 표시할 것)