백준 9328번 파이썬 문제풀이(열쇠 ) - (bfs + 구현)

---

해당 문제는 비트마스킹으로 접근할려고 했으나 1<< 26 * w * h 의 dp 방문처리를위한 배열을 미리만들어야 하므로 당연히 시간초과가 발생한다. 따라서 다른 접근방식을 생각 해야했는데 약간의 힌트를 참고했다. 

 

1. 방문처리는 2차원 배열로 하되 새로운 열쇠를 찾으면 리셋해줘야 한다.

2. 비밀문서를 찾을 때 해당 위치를 저장한 후에 다음번에 똑같은 곳을 찾으면 개수를 세지 않도록 처리해야 한다.

3. 가장자리를 넘나들 수 있다는 것은 패딩으로 사이드 부분을 길로 만들어주면 (즉, '.' 으로 감싸주면) 된다.

 

(개인적으로 정말 좋은 문제라고 생각한다. 코딩테스트에서도 어려운 문제로 충분히 나올 수 있다고 생각한다.)

from collections import deque

dr = [-1, 0, 1, 0]  # 상 우 하 좌
dc = [0, 1, 0, -1]  # 상 우 하 좌


def bfs(visited):
    global ans

    queue = deque([[0, 0]])
    visited[0][0] = True
    while queue:
        r, c = queue.popleft()

        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            # 범위를 벗어나거나 벽이거나 이미 방문했다면 컨티뉴
            if nc < 0 or nc >= w + 2 or nr < 0 or nr >= h + 2 or miro[nr][nc] == '*' or visited[nr][nc]:
                continue

            if 'A' <= miro[nr][nc] <= 'Z':  # 대문자라면(문이라면)
                if chr(ord(miro[nr][nc]) + 32) not in key:  # 해당 문을 열수있는 키가 없다면
                    continue  # 컨티뉴
            elif 'a' <= miro[nr][nc] <= 'z':  # 만약 소문자이고
                if miro[nr][nc] not in key:  # 아직 키에 없다면
                    key[miro[nr][nc]] = True  # 해당 키를 저장후
                    visited = [[False] * (w + 2) for _ in range(h + 2)]  # 방문체크 초기화
            elif miro[nr][nc] == "$" and (nr, nc) not in visited_doc:  # 비밀문서이고 아직방문하지 않았다면
                ans += 1  # 찾은 개수 1개 증가
                visited_doc.append((nr, nc))  # 해당 위치는 더이상 방문하면 안되기 때문에 저장

            visited[nr][nc] = True  # 방문처리
            queue.append([nr, nc])  # 다음 위치를 큐에 삽입


T = int(input())

for _ in range(1, T + 1):
    h, w = map(int, input().split())

    miro = ['.' + input() + '.' for _ in range(h)]
    miro = ['.' * (w + 2)] + miro + ['.' * (w + 2)]
    visited = [[False] * (w + 2) for _ in range(h + 2)]
    key = {}  # 가지고 있는 키 저장
    visited_doc = []  # 방문한 키 위치 저장

    for i in input():
        if i.isalpha():  # 만약 알파벳이면
            key[i] = True  # 키로 저장

    ans = 0
    bfs(visited)
    print(ans)