김낭만

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

백준(BOJ) 9328 열쇠 파이썬(Python)

문제 링크

BFS 구현 문제.
비트마스킹을 활용해서 열쇠의 소지 유무를 체크했다.
또한, BFS를 활용한다지만 최단거리를 구할 필요가 없다.
따라서, 열쇠나 문서의 개수를 배열 위치 별로 관리하지 않고 하나의 전역변수로 사용해도 된다.
보드의 가장자리에 접근하기 위해 가장자리에 빈 공간의 패딩을 한 줄씩 덧붙여 주었다.

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

# 알파벳을 숫자로 변환하는 딕셔너리
AB = dict(zip('abcdefghijklmnopqrstuvwxyz', (i for i in range(26))))

t = int(input())
for _ in range(t):
    h, w = map(int, input().split())
    
    # 보드에 .으로 된 패딩 부여
    w += 2
    board = ['.' * w] + [list('.' + input().rstrip() + '.') for _ in range(h)] + ['.' * w]
    h += 2
    visited = [[0] * w for _ in range(h)]
    
    # 문서 개수
    document = 0
    
    # 열쇠 비트마스킹
    key = 0
    temp = input().rstrip()
    if temp != '0':
        for alphabet in temp:
            key |= 1 << AB[alphabet]
    
    # 0, 0에서 시작한다
    # 패딩 때문에 가장자리 어디서 시작하든 무관
    q = deque()
    q.append((0, 0))
    
    # BFS
    while q:
        i, j = q.popleft()
        for di, dj in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            if 0<=i+di<h and 0<=j+dj<w and not visited[i+di][j+dj]:
                visited[i+di][j+dj] = 1
                # 벽이면 패스
                if board[i+di][j+dj] == '*':
                    continue
                # 빈 공간이면 이동
                elif board[i+di][j+dj] == '.':
                    q.append((i+di, j+dj))
                # 문서면 먹고 해당 공간으로 이동
                # 먹으므로 빈 공간으로 변해야 한다
                elif board[i+di][j+dj] == '$':
                    document += 1
                    q.append((i+di, j+dj))
                    board[i+di][j+dj] = '.'
                # 대문자면 해당하는 열쇠가 있는지 확인해서 이동 여부 결정
                elif 65 <= ord(board[i+di][j+dj]) <= 90:
                    if key & (1 << AB[board[i+di][j+dj].lower()]):
                        q.append((i+di, j+dj))
                # 소문자면 열쇠 유무에 따라 갱신하고 이동
                else:
                    if not (key & (1 << AB[board[i+di][j+dj]])):
                        key |= 1 << AB[board[i+di][j+dj]]
                        visited = [[0] * w for _ in range(h)]
                    q.append((i+di, j+dj))
    
    print(document)

2024

맨 위로 이동 ↑

2023

세그먼트 트리

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

벨만-포드 알고리즘

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

다익스트라 알고리즘

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

맨 위로 이동 ↑