알고리즘/백준

9328 열쇠

아메숑 2019. 3. 15. 01:09

1. 문제

  • '.'는 빈 공간을 나타낸다.
  • '*'는 벽을 나타내며, 상근이는 벽을 통과할 수 없다.
  • '$'는 상근이가 훔쳐야하는 문서이다.
  • 알파벳 대문자는 문을 나타낸다.
  • 알파벳 소문자는 열쇠를 나타내며, 그 문자의 대문자인 모든 문을 열 수 있다.
  • 각 테스트 케이스 마다, 상근이가 훔칠 수 있는 문서의 최대 개수를 출력한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
3
5 17
*****************
.............**$*
*B*A*P*C**X*Y*.X.
*y*x*a*p**$*$**$*
*****************
cz
5 11
*.*********
*...*...*x*
*X*.*.*.*.*
*$*...*...*
***********
0
7 7
*ABCDE*
X.....F
W.$$$.G
V.$$$.H
U.$$$.J
T.....K
*SQPML*
irony
cs


2. 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
from collections import deque
 
for T in range(int(input())):
    N, M = map(int,input().split())
    maps = [["."] * (M+2) for _ in range(N+2)]
    for i in range(1,N+1):
        maps[i] = ["."]+list(input())+["."]
    
    key = input()
    visit = [[-1]*(M+2) for _ in range(N+2)]
 
    #알파벳 형태의 키를 비트마스킹으로 숫자로 표현
    ikey = 0
    if key != '0':
        for i in range(len(key)):
            ikey |= (1<<ord(key[i])-97)
    cnt = 0
    row = [1,-1,0,0]
    col = [0,0,1,-1]
    q = deque()
    q.append(([0,0],ikey))
    while q:
        cur, k = q.popleft()
        for d in range(4):
            nx = cur[0] + row[d]
            ny = cur[1] + col[d]
            if nx <0 or ny <0 or nx >N+1 or ny >M+1:
                continue
 
            #같은 키꾸러미를 가지고 같은곳을 방문했을 때
            if visit[nx][ny] != -1 and visit[nx][ny] == k:
                continue
 
            if maps[nx][ny] == '*':
                continue          
 
            #처음 방문할 때 
            if visit[nx][ny] == -1:
                visit[nx][ny] = 0
 
            alpha = ord(maps[nx][ny])
            #소문자(key)
            if alpha >= 97 and alpha < 123:
                q.append(([nx,ny], k|(1<< (ord(maps[nx][ny])-97))))
                visit[nx][ny] |= k|(1<< (ord(maps[nx][ny])-97))
                maps[nx][ny] = '.'
 
            #대문자(door)
            elif alpha >= 65 and alpha < 91:
                #키를 가지고 있을 경우
                if k & (1 << (ord(maps[nx][ny])-65)) != 0:
                    maps[nx][ny] = '.'
                    q.append(([nx,ny],k))
                visit[nx][ny] = k
                
            #서류
            elif maps[nx][ny] == '$':
                cnt += 1
                maps[nx][ny] = '.'
                q.append(([nx,ny],k))
                visit[nx][ny] = k              
            
            #빈공간
            elif maps[nx][ny] == '.':
                q.append(([nx,ny],k))
                visit[nx][ny] = k
 
    print(cnt)
 
 
cs


3. 후기

역시 시간초과가 뜬다. 답은 제대로 나오는데 다른 블로그를 봐도 테두리에 '.'으로 채워주고, 문을 따거나, 열쇠를 찾거나, 문서를 발견하면 '.'로 바꿔주는 형식으로 진행했다. 방문 배열에 내가 가지고 있는 키를 비트마스크로 표현하여 저장해서, 키를 찾게되면 방문했던곳도 다시 검사하도록 설정했다. 하지만 두번째 테스트케이스에서 처럼 가지고 있는 키가 0개일 경우 visit[nx][ny] == k에서 k가 0이므로 더 이상 진행이 불가능해서 방문배열을 -1로 채웠다.