오늘 배운 것들

1. DFS/BFS

그래프를 탐색하는 알고리즘의 대표적인 두 분류.
트리에서도 많이 사용한다.

1. DFS(Depth First Search)

시작 정점부터 한 경로를 끝까지 탐색한 후 돌아와 다른 경로를 탐색하는 방식.
주로 스택이나 재귀를 이용해서 구현한다.
현재 경로가 아닌 정점을 저장하지 않으므로 메모리가 효율적일 수 있으나 너무 깊은 그래프의 경우 스택 오버플로우의 위험이 있다.
경로 탐색, 사이클 탐지 등에 유용하다.

2. BFS(Breadth First Search)

시작 정점부터 인접한 모든 노드를 방문한 후, 그 다음 깊이의 인접 노드들을 방문하는 방식.
주로 큐를 이용해서 구현한다.
현재 경로 외의 정점도 큐에 저장하므로 메모리 사용량이 많을 수 있으나 깊은 그래프에도 정상적으로 탐색할 수 있다.
(가중치가 없을 때) 최단 경로 탐색, 레벨 탐색에 유용하다.

2. 문제풀이

2-1. 이분 그래프(백준 1707)

import sys
from collections import deque

input = sys.stdin.readline

class Vertex:
    def __init__(self, key: int) -> None:
        self.key = key
        self.value = None
        self.conn = []  # connected to _

def main() -> None:
    def bfs(n: int) -> bool:
        all_vertexes = set(range(1, n + 1))
        visited = set()
        q = deque()
        while len(visited) < n:
            start = (all_vertexes - visited).pop()
            q.append(start)
            vertexes[start].value = 0
            while q:
                v = q.popleft()
                visited.add(v)
                for i in vertexes[v].conn:
                    if i not in visited:
                        q.append(i)
                        if vertexes[i].value is None:
                            vertexes[i].value = (vertexes[v].value + 1) % 2
                        elif vertexes[i].value == vertexes[v].value:
                            return False
        return True

    N = int(input())
    for _ in range(N):
        V, E = map(int, input().split())
        A = [tuple(map(int, input().split())) for _ in range(E)]
        vertexes = {i: Vertex(i) for i in range(1, V + 1)}
        for a, b in A:
            vertexes[a].conn.append(b)
            vertexes[b].conn.append(a)

        print("YES" if bfs(V) else "NO")

if __name__ == "__main__":
    main()

최초에 내가 작성한 코드이다.
bfs로 큐에서 노드를 하나씩 빼내며 방문한다.
너무 느려서 gpt에 개선을 부탁해봤다.

    def bfs(n: int) -> bool:
        visited = set()
        q = deque()
        for start in range(1, n+1):
            if start not in visited:
                q.append(start)
                vertexes[start].value = 0
            while q:
                v = q.popleft()
                if v not in visited:
                    visited.add(v)
                    for i in vertexes[v].conn:
                        if vertexes[i].value is None:
                            vertexes[i].value = (vertexes[v].value + 1) % 2
                            q.append(i)
                        elif vertexes[i].value == vertexes[v].value:
                            return False
        return True

변경된 bfs만 살펴보면

1. all_vertexes가 사라졌다.
   비연결 그래프인 경우에도 모든 정점을 탐색하기 위해서 나는 모든 정점을 가진 집합 all_vertexes를 이용하여 visited집합과의 차집합을 이용했다.
   gpt는 간단하게 1부터 n(정점의 수)까지 반복문을 돌려 방문하지 않았는지를 체크하는 방법을 택했다.
2. 방문한 정점의 인접노드 i의 방문여부를 다시 체크하지 않는다.
   i의 색깔(value)가 None이면 방문하지 않았다는 것이고, None이 아니라면 방문했거나 큐에 들어있다는 뜻이다.
   굳이 체크할 필요가 없었다.

특히 1.에서 차집합을 계산한 것이 시간을 많이 소모한 것 같다.

2-2. 아침 산책(백준 21606)

import sys
sys.setrecursionlimit(10**6)

input = sys.stdin.readline

class Vertex:
    def __init__(self, key: int, value: any=None) -> None:
        self.key = key
        self.value = value
        self.conn: list[int] = [] # connected to _

N = int(input())
vertexes: dict[int, Vertex] = {}
outside = []
result = 0
visited = [0]*(N+1)
for i, v in enumerate(list(input().rstrip()), 1):
    vertexes[i] = Vertex(i, int(v))
    if v == '0':
        outside.append(i)
for _ in range(N-1):
    a, b = map(int, input().split())
    vertexes[a].conn.append(b)
    vertexes[b].conn.append(a)
    if vertexes[a].value + vertexes[b].value == 2:
        result += 2

def dfs(now: int) -> None:
    visited[now] = 1
    n_inside = 0
    for adj in vertexes[now].conn:
        if vertexes[adj].value == 1:
            n_inside += 1
            visited[adj] = 1
        elif not visited[adj]:
            n_inside += dfs(adj)
    return n_inside
        
for i in outside:
    if not visited[i]:
        n = dfs(i)
        result += n * (n-1)

print(result)

시간 초과나서 결국 혼자 못 풀었다.
동기가 수학적 접근법을 보여주었지만 내 머리로 만들어 낼 수 없을 것 같아 다른 힌트를 받아 풀었다.
힌트는 실외를 기준으로 접근하는 것.

아직도 직관적인 구현(생각을 그저 언어로 번역할 뿐인)으로 충분한 문제인지, 압축적인 해법을 찾아야 하는 것인지 감이 잘 오지 않는다.

2-3. 빙산(백준 2573)

import sys
from collections import deque

input = sys.stdin.readline
dx = [1, 0, 0, -1]
dy = [0, 1, -1, 0]

def main() -> None:
    def melt():
        def check_4way(i: int, j: int) -> int:
            result = 0
            for d in range(4):
                if (i+dx[d], j+dy[d]) not in ices:
                    result += 1
            return result
        items_pop = []
        for idx, h in ices.items():
            h -= check_4way(*idx)
            if h <= 0:
                items_pop.append(idx)
            else:
                ices[idx] = h
        for idx in items_pop:
            ices.pop(idx)
    # 하나의 덩어리이면 True
    def check_unity() -> bool:
        ices_ = ices.copy()
        q = deque()
        q.append(ices_.popitem()[0])
        while q:
            i, j = q.popleft()
            for d in range(4):
                if (idx:=(i+dx[d], j+dx[d])) in ices_:
                    ices_.pop(idx)
                    q.append(idx)
        return not bool(ices_)
        
    N, M = map(int, input().split())
    ices = {}
    for i in range(N):
        temp = []
        for j, h in enumerate(map(int, input().split())):
            temp.append((i, j))
            if h > 0:
                ices[(i, j)] = h
    time = 1
    melt()
    while ices:
        if not check_unity():
            print(time)
            return
        time += 1
        melt()
    print(0)
    
main()

맵을 반전시켜서 시프트할까 등 많은 생각을 했었지만
그냥 무식하게 얼음 하나씩 체크해서 녹이고
또 무식하게 bfs로 분할 체크하는게 답인 문제였다.

2-4. 특정 거리의 도시 찾기(백준 18352)

import sys
from collections import deque

input = sys.stdin.readline

def main() -> None:
    N, M, K, X = map(int, input().split())
    roads = {i: [] for i in range(1, N+1)}
    for _ in range(M):
        frm, to = map(int, input().split())
        roads[frm].append(to) if to not in roads[frm] else None
    
    q = [i for i in roads[X]]
    visited = {X: 1}
    for _ in range(K-1):
        visit_now = q
        q = []
        for now in visit_now:
            visited[now] = 1
            q.extend([i for i in roads[now] if i not in visited and i not in visit_now and i not in q])
    
    print(*sorted(q) if q else [-1], sep="\n")

main()

또 다른 무식한 bfs문제.
문제 조건에 중복 간선이 없다는 말이 없어서(중복 간선이 있을 수 있다)
예외 처리를 하지 못 해 많이 헤맸다.

20번 줄에 긴 조건문을 줄일 방법이 있을 것 같은데 잘 생각나지 않는다.

소감

정신적으로 힘들다.
발전하는 느낌이 안 들고 오히려 뒷걸음질 하는 것 같다.
답은 이미 안다.
지나가길 기다리는 수 밖에