자료구조 알고리즘 복습

백준 2606 문제

바이러스

from collections import deque
import sys
I = sys.stdin.readline

def breadth_first_search(graph, root):
    queue = deque([root])
    discovered = [root]
    visited = []

    while len(queue) > 0:
        node = queue.popleft()
        visited.append(node)
        undiscovered = set(graph[node]).difference(set(discovered))

        if undiscovered:
            discovered.extend(undiscovered)
            for elem in sorted(undiscovered):
                queue.append(elem)

    return visited


def depth_first_search(graph, root):
    stack = [root]
    discovered = [root]
    visited = []

    while stack:
        node = stack.pop()
        visited.append(node)
        undiscovered = set(graph[node]).difference(set(discovered))

        if undiscovered:
            discovered.extend(undiscovered)
            data = sorted(undiscovered)
            while data:
                a = data.pop()
                stack.append(a)


    return visited


n = int(I())
m = int(I())
graph1 = {}
for i in range(1, n+1):
    graph1[str(i)] = []

for _ in range(m):
    vertex, data = I().split()
    graph1[vertex].append(data)
    graph1[data].append(vertex)

result = breadth_first_search(graph1, '1')
print(len(result) - 1)

결과

특별한 것은 없었으나, 그래프에서 directed가 기본이라고 생각하고 데이터 입력에 주의해야겠다.

백준 10026번

적록색약

from collections import deque
import sys
import copy
I = sys.stdin.readline


def breadth_first_search(graph, root):
    queue = deque([root])
    discovered = [root]
    visited = []

    while len(queue) > 0:
        node = queue.popleft()
        visited.append(node)
        undiscovered = set(graph[node]).difference(set(discovered))

        if undiscovered:
            discovered.extend(undiscovered)
            for elem in sorted(undiscovered):
                queue.append(elem)

    return visited


def depth_first_search(graph, root):
    stack = [root]
    discovered = [root]
    visited = []

    while stack:
        node = stack.pop()
        visited.append(node)
        undiscovered = set(graph[node]).difference(set(discovered))

        if undiscovered:
            discovered.extend(undiscovered)
            data = sorted(undiscovered)
            while data:
                a = data.pop()
                stack.append(a)


    return visited


def up(graph, paper, i, j):
    if paper[i][j] == paper[i-1][j]:
        graph[(i, j)].append((i-1,j))


def down(graph, paper, i, j):
    if paper[i][j] == paper[i+1][j]:
        graph[(i, j)].append((i+1,j))


def left(graph, paper, i, j):
    if paper[i][j] == paper[i][j-1]:
        graph[(i, j)].append((i,j-1))


def right(graph, paper, i, j):
    if paper[i][j] == paper[i][j+1]:
        graph[(i, j)].append((i, j+1))


def determine_group_color(graph, paper, n):
    for i in range(n):
        for j in range(n):
            if 1 <= i < n-1 :
                if j == 0:
                    up(graph, paper, i, j)
                    right(graph, paper, i, j)
                    down(graph, paper, i, j)
                elif j == n-1:
                    up(graph, paper, i, j)
                    left(graph, paper, i, j)
                    down(graph, paper, i, j)
                else:
                    up(graph, paper, i, j)
                    right(graph, paper, i, j)
                    down(graph, paper, i, j)
                    left(graph, paper, i, j)
            elif i == 0:
                if j == 0:
                    right(graph, paper, i, j)
                    down(graph, paper, i, j)
                elif j == n-1:
                    left(graph, paper, i, j)
                    down(graph, paper, i, j)
                else:
                    right(graph, paper, i, j)
                    down(graph, paper, i, j)
                    left(graph, paper, i, j)
            else:
                if j == 0:
                    up(graph, paper, i, j)
                    right(graph, paper, i, j)
                elif j == n-1:
                    up(graph, paper, i, j)
                    left(graph, paper, i, j)
                else:
                    up(graph, paper, i, j)
                    right(graph, paper, i, j)
                    left(graph, paper, i, j)


graph = {}
graph_dsb = {}

num = int(I())
li = []
for _ in range(num):
    li.append([color for color in I().rstrip('\n')])

li_dsb = copy.deepcopy(li)
for i in range(num):
    for j in range(num):
        if li_dsb[i][j] == 'G':
            li_dsb[i][j] = 'R'

for i in range(num):
    for j in range(num):
        graph[(i,j)] = []
for i in range(num):
    for j in range(num):
        graph_dsb[(i,j)] = []


determine_group_color(graph, li, num)
determine_group_color(graph_dsb, li_dsb, num)

li = []
li_dsb = []
cnt = 0
cnt_dsb = 0
for i in range(num):
    for j in range(num):
        if (i, j) not in li:
            li.extend(breadth_first_search(graph, (i, j)))
            cnt += 1

for i in range(num):
    for j in range(num):
        if (i, j) not in li_dsb:
            li_dsb.extend(breadth_first_search(graph_dsb, (i, j)))
            cnt_dsb += 1
print(cnt, cnt_dsb)

결과

처리 속도가 느렸고 코드가 난해하다. 문제를 푸는 알고리즘에 있어서 사람이 푸는 방식을 직관적으로 받아드려 가공하지 않은 채 구현해서 전문성이 없었다. 지금은 파이썬 문법에 익수해 지고 자료구조에 익숙해 지기 위함임으로 나중에 다시 풀어보기로 했다.

접한 오류

TypeError : unhashable type: 'set'
-> dictionary의 key data로 immutable 하지 않은 값을 넣었을 때 발생