[백준] 9328번 : 열쇠

9328번: 열쇠

9328번: 열쇠

🤔 문제분석

BFS 탐색 및 구현 문제로, 문제만 정확히 이해 한다면 쉽게 풀 수 있는 문제입니다.

문의 Key를 확인하고자 딕셔너리 자료구조를 활용하였습니다.

1. 출발할 수 있는 곳을 구하기 ( 단, 끝자락이 벽인경우, 열쇠인경우, 알파벳인경우를 예외처리 해주어야합니다. )
2. 탐색하기 : 출발지로부터 갈 수 있는곳을 탐색하며 열쇠와 문서의 개수를 업데이트 합니다.
   1. 만약, 문서와 열소의 개수를 얻지 못한다면, 다음 탐색에도 똑같기 때문에 여기서 게임을 종료합니다.

📝 의사코드

1. 갈 수 없을때까지 2번사항과 3번 사항을 무한 반복
2. 출발 할 수 있는 곳 구하기
   1. 그래프의 가장자리를 방문해본다.
   2. 알파벳인경우 대문자면 키가 있는지 확인해보고 있다면 ‘.’로 바꾼다. 그리고 출발지로 설정한다.
   3. 알파벳인경우 소문자면 키에 업데이트해주고, ‘.’로 바꾼다. 그리고 출발지로 설정한다.
   4. ‘.’ 인경우 출발지로 설정한다.
   5. ‘$’인경우 문서의 개수를 추가하고 출발지로 설정한다.
3. 출발지로부터 갈 수 있는곳 탐색하기
   1. 상, 하, 좌, 우로 이동하면서 갈 수 있는곳을 탐색한다.
   2. 알파벳인경우 대문자면 키가 있는지 확인해보고 있다면 ‘.’로 바꾼다. 이어서 탐색한다.
   3. 알파벳인경우 소문자면 키에 업데이트해주고, ‘.’로 바꾼다. 이어서 탐색한다.
   4. ‘.’인경우 이어서 탐색한다.
   5. ‘$’인경우 문서의 개수를 추가하고 이어서 탐색한다.

💻 코드

import sys
input = sys.stdin.readline

def start_pos():
    global ans
    start = []
    for i in range(h):
        for j in range(w):
            if (i == h-1 or i == 0 or j == w-1 or j == 0) and table[i][j] != '*':
                if table[i][j] == '.':
                    start.append((i, j))
                elif table[i][j].isalpha():
                    if table[i][j].islower():
                        key.setdefault(table[i][j].upper(), True)
                        start.append((i, j))
                        table[i][j] = '.'
                    else:
                        if table[i][j] in key:
                            table[i][j] = '.'
                            start.append((i, j))
                elif table[i][j] == '$':
                    table[i][j] = '.'
                    ans += 1
                    start.append((i, j))
    return start

def can_go(start):
    queue = []
    visited = [[False for _ in range(w)] for _ in range(h)]
    for i, j in start:
        queue.append((i, j))
        visited[i][j] = True
        
    get_key = False
    cnt = 0
    while queue:
        y, x = queue.pop()
        for dy, dx in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            ny, nx = dy + y, dx + x
            if h > ny >=0 and w > nx >=0 and not visited[ny][nx] and table[ny][nx] != '*':
                visited[ny][nx] = True
                if table[ny][nx].isalpha():
                    if table[ny][nx].isupper():
                        if table[ny][nx] in key:
                            table[ny][nx] = '.'
                            queue.append((ny, nx))
                    else:
                        get_key = True
                        key.setdefault(table[ny][nx].upper(), True)
                        table[ny][nx] = '.'
                        queue.append((ny, nx))
                else:
                    if table[ny][nx] != '*':
                        queue.append((ny, nx))
                        if table[ny][nx] == '$':
                            table[ny][nx] = '.'
                            cnt += 1
    return get_key, cnt
    

T = int(input())
for _ in range(T):
    h, w = map(int, input().split())
    table = [list(str(input().strip())) for _ in range(h)]
    already_key = str(input().strip())
    key = {}
    ans = 0
    
    for k in already_key:
        key.setdefault(k.upper(), True)
    
    while True:
        start = start_pos()
        get_key, cnt = can_go(start)
        #print(get_key, cnt, key)
        if not get_key and cnt == 0:
            break
        ans += cnt
        
    print(ans)

🎯 피드백 및 개선사항

구현 문제는 문제를 잘 파악하여, 내가 생각지도 못했던 허점을 잘 파악해야합니다.

처음 문제를 해결할때 출발지에서의 ‘.’ 만 체크하여 문제를 한번에 해결하지 못하였습니다.