김낭만

재밌거나 필요하다고 생각하는 걸 만듭니다.

백준(BOJ) 1987 알파벳 파이썬(Python)

문제 링크

DFS 길찾기라는 발상은 금방 떠올렸는데, 구현에 있어서 놓친 게 있었던 문제.
일단 기본적인 아이디어는 DFS 백트래킹을 활용해서 가장 먼 거리를 찾는 것이다.
구현이 크게 어렵지는 않아서 금방 코드를 짰는데, pypy에서도 TLE가 떴다.
잘 생각해보니, 방문 처리를 하는 배열을 딕셔너리로 짠 게 문제가 되겠다 싶었다.
흔히 딕셔너리에서 원소 참조의 시간복잡도는 \(O(1)\)이라고 말하지만, 해시로 구현된 딕셔너리 특성 상 해시 충돌이 발생하면 시간복잡도는 \(O(N)\)까지 늘어날 수 있다.
또한 해싱에 들어가는 오버헤드를 감안하면, 같은 \(O(1)\)이라도 리스트의 참조가 더 빠르다고 보아야 한다.
방문 처리를 딕셔너리 대신 리스트로 하도록 변경한 후 AC를 맞을 수 있었다.

from sys import stdin
input = stdin.readline

r, c = map(int, input().split())
board = [input().rstrip() for _ in range(r)]
visited = [0] * 26
# 65는 A의 아스키코드
visited[ord(board[0][0]) - 65] = 1

def dfs(i, j, ans):
    ret = ans
    for di, dj in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        if 0<=i+di<r and 0<=j+dj<c and not visited[ord(board[i+di][j+dj]) - 65]:
            visited[ord(board[i+di][j+dj]) - 65] = 1
            ret = max(ret, dfs(i+di, j+dj, ans + 1))
            # 백트래킹이므로 지나간 길을 돌아올 때 방문 처리를 취소해야 함
            visited[ord(board[i+di][j+dj]) - 65] = 0
    return ret

print(dfs(0, 0, 1))

2024

맨 위로 이동 ↑

2023

세그먼트 트리

개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...

벨만-포드 알고리즘

개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...

다익스트라 알고리즘

개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...

맨 위로 이동 ↑