열쇠 ( 9328 번 )

9328번: 열쇠

 

---

🧠 알고리즘

• BFS + 문/열쇠 관리(대기열) + 외곽 진입 탐색

 

✔️ 동작 방식

[ 핵심 아이디어 ]

• 건물 지도를 탐색하며 **문서($)**를 최대한 많이 수집한다.
• 문(대문자)을 만나면 해당 키(소문자)가 없으면 지나갈 수 없다.
• 키를 얻는 순간, 이전에 막혀 있던 문들을 즉시 열고 탐색을 재개한다.
• 외곽(바깥)에서만 진입 가능하므로, 모든 탐색의 시작 방향은 외곽에서 BFS로 진행한다.
• 방문한 위치는 '#' 로 변경하여 중복 탐색을 방지한다

 

[ 로직 요약 ]

1) 초기 설정

• 지도 입력 후, 이미 가진 키 목록을 key_info로 저장
• 아직 열 수 없어서 막혀 있는 문들의 좌표를 저장하는 wait_door(dict) 생성
• 외곽(border line)에서 시작 가능한 좌표를 BFS 탐색 시작점으로 등록

2) BFS(now_x, now_y)

• 큐를 이용하여 상하좌우 탐색
• 각 칸에서 다음을 처리:

✔ 문서($)

→ 문서 수 doc 증가

 

✔ 키(소문자)

→ key_info에 저장
→ 이 키로 열 수 있는 문이 wait_door에 있으면 즉시 큐에 넣어 탐색 재개

 

✔ 문(대문자)

• 키가 없으면 → wait_door에 좌표 저장하고 패스
• 키가 있으면 → 통과 가능

✔ 빈 공간(.) 또는 이미 열린 통로

→ 그대로 BFS 진행

 

3) 외곽 탐색

• 벽(*)이 아니고
• 열 수 없는 문이 아니면 → 해당 지점에서 BFS 시작

4) 결과

• 모든 가능한 경로를 탐색한 뒤→ 얻은 문서 수(doc)를 출력

---

 

🧾 코드

import sys
from collections import deque

def _main():
    doc = 0 # 얻은 문서 갯수
    h, w = map(int, sys.stdin.readline().rstrip().split())
    map_list = [list(sys.stdin.readline().rstrip()) for _ in range(h)]
    key_str = sys.stdin.readline().rstrip()
    key_info = set() if key_str == '0' else set(key_str)

    # 잠긴 문 위치 저장
    wait_door = {}
    
    def _bfs(now_x, now_y):
        nonlocal doc
        queue = deque([(now_x, now_y)])
        if map_list[now_x][now_y].islower(): # 첫 시작이 key 인 경우..
            upper_key = map_list[now_x][now_y].upper()
            
            if upper_key in wait_door: # 문 있으면
                while wait_door[upper_key]:
                    go_x, go_y = wait_door[upper_key].popleft()
                    map_list[go_x][go_y] = '#'
                    queue.append((go_x, go_y))

        map_list[now_x][now_y] = '#'

        while queue:
            a, b = queue.popleft()

            for n_a, n_b in ((a+1, b), (a-1, b), (a, b+1), (a, b-1)):
                # 1. 경계 및 벽/방문 여부 검사
                if not (0 <= n_a < h and 0 <= n_b < w):
                    continue
                    
                cell_value = map_list[n_a][n_b]
                if cell_value in ('*', '#'): 
                    continue
                
                # 2. 문서 획득
                if cell_value == '$':
                    doc += 1
                
                # 3. 키 획득 (소문자)
                elif cell_value.islower():
                    key_info.add(cell_value)
                    upper_key = cell_value.upper()
                    
                    # 새로 얻은 키로 현재 wait_door에 잠겨있는 문들을 즉시 엽니다.
                    if upper_key in wait_door:
                        # 문들을 큐에 추가하고, wait_door에서 제거합니다.
                        while wait_door[upper_key]:
                            go_x, go_y = wait_door[upper_key].popleft()
                            map_list[go_x][go_y] = '#'
                            queue.append((go_x, go_y))
                
                # 4. 문 만남 (대문자)
                elif cell_value.isupper():
                    lower_key = cell_value.lower()
                    
                    if lower_key not in key_info:
                        # 키가 없으면 wait_door에 저장하고 현재 경로는 탐색 중단
                        wait_door.setdefault(cell_value, deque()).append((n_a, n_b))
                        continue
                        
                # 5. 문을 통과했거나, 키를 얻었거나, 문서를 얻었거나, 빈 공간을 지나갈 때
                map_list[n_a][n_b] = '#'
                queue.append((n_a, n_b))
        
            
    # 외곽 탐색
    border_line = []
    border_line += [(0, idx) for idx in range(w)]
    border_line += [(h-1, idx) for idx in range(w)]
    border_line += [(idx, 0) for idx in range(1, h-1)]
    border_line += [(idx, w-1) for idx in range(1, h-1)]

    for x, y in border_line:
        cell_value = map_list[x][y]
        if cell_value in ('*', '#'): # 벽이거나 이미 방문 pass..
            continue

        if cell_value.isupper() and cell_value.lower() not in key_info: # 문 인데.. 열수 없으면..
            wait_door.setdefault(cell_value, deque()).append((x, y))
            continue

        if cell_value in ('.', '$') or cell_value.islower() or (cell_value.isupper() and cell_value.lower() in key_info): # 빈 공간, 문서, 열쇠이면, 문 인데.. 열수 있으면 gogo..
            if cell_value == '$':
                doc += 1
            elif cell_value.islower():
                key_info.add(cell_value)
                
            _bfs(x, y)
            
    return doc


case = int(sys.stdin.readline().rstrip())
for _ in range(case):
    print(_main())

---

 

⏱️ 시간 복잡도

for x, y in border_line : 모든 칸 을 순회 ( 이차형 시간 )

해당 알고리즘 시간 복잡도 : 이차형 시간 복잡도 ( O(n ** 2) )