BOJ (열쇠)9328

작성일 | In

열쇠

  • 빌딩에서 문서를 훔치는 문제
  • 지도에는 문과 열쇠가 있다.

  • 열쇠를 얻으면 문을 열 수 있다.

  • 키는 c와 z가 있다면

  • C를 찾아서 C를 열고, p열쇠를 가져오고 p를 열어서 a열쇠를 얻고 a를 열어서 x를 얻고 나가서 x를 열고 그런 방식

  • 이 문제가 까다로운 이유 -> 같은 곳을 여러번 방문해야한다.

  • 문서의 최대개수만 구하면 되는거지, 방법이 어떻게 되는지는 구할 필요가 없다.

  • 문이 나오면 문을 열기위해서 기다리고 있는거다.-> 사람 한명 기다려두고,
  • 못 열면 또 사람한명 기다리고 있고.
  • 기다리고 있다는 것은 -> 다시 되돌아갈 수 있다는 것을 의미
from collections import deque
dx = [0,0,1,-1]
dy = [1,-1,0,0]
t = int(input())
for _ in range(t):
    n,m = map(int,input().split())
    a = ['*.'+input()+'.*' for _ in range(n)]
    n += 4
    m += 4
    a = ['*'*m,'*'+'.'*(m-2)+'*'] + a + ['*'+'.'*(m-2)+'*','*'*m]
    key = set(input())
    ans = 0
    check = [[False]*m for _ in range(n)]
    q = deque()
    door = [deque() for _ in range(26)] # q를 26개를 만들었다. 문 앞에서 기다리고 있는 q다.
    q.append((1,1))
    check[1][1] = True
    while q:
        x,y = q.popleft()
        for k in range(4):
            nx,ny = x+dx[k],y+dy[k]
            if check[nx][ny]:
                continue
            w = a[nx][ny]
            if w == '*':
                continue
            check[nx][ny] = True
            if w == '.':
                q.append((nx,ny))
            elif w == '$':
                q.append((nx,ny))
                ans += 1
            elif 'A' <= w <= 'Z': # 문을 만났을 때.
                if w.lower() in key: # 열쇠를 가지고 있으면 q에 넣는다
                    q.append((nx,ny))
                else: # 그게 아니라면  문 앞에서 기다리고 있는 큐에 넣는다.
                    door[ord(w)-ord('A')].append((nx,ny))
            elif 'a' <= w <= 'z': # 열쇠를 얻었을 때,
                q.append((nx,ny)) # 방문
                if not w in key: # 키가 없었을 때-> 처음으로 그 키 얻음
                    key.add(w)
                    q.extend(door[ord(w)-ord('a')])  # 문 앞에서 기다리고 있는 사람을 다 넣어준다.
    print(ans)
  • BFS는 사람이 복제되어있는 것이라고 생각하면 문제 풀이가 간단해질 수 있다.
  • extend 함수는 lst.extend('ef') >> ['a','b','c','d','e','f']
  • append는 lst2.append('ef') >> ['a','b','c','d','ef']

참고자료 codeplus extend참고

0%