개구리

우물 안 개구리

처음에 비트마스킹을 잘못 이해했다. 보유할 수 있는 열쇠의 경우의 수를 비트마스킹으로 표현했다. (7bit)

visited를 2차원 배열로 만들고 특정 지점을 방문했을 때 가지고 있는 열쇠를 visited배열의 값으로 갖도록 코드를 짰다. ex)visited[x][y] = 0b1 000 001 : a 열쇠를 갖고 있고 해당 지점을 방문한 적이 있음, visited[x][y] = 0b0 100 001 : a,f 열쇠를 갖고 있고 해당 지점을 방문한 적이 없음

결과는 메모리 초과.

visited를 3차원 배열로 만들고 가질 수 있는 열쇠의 경우의 수만큼 3차원 배열에서 가장 안쪽의 배열 개수로 설계한다. ex)visited[x][y][0b0000001] = 1, a 열쇠를 갖고 있고 해당 지점을 방문한 적이 있음.

비트마스킹 기법은 배열의 개수를 비트의 수만큼 만드는 것이다.

코드

from collections import deque
N,M= map(int, input().split())
miro=[]

for i in range(N):
    line = input()
    miro.append(line)
    if '0' in line:
        startx=i
        starty=line.find('0')

visited=[[[0 for _ in range(64)] for _ in range(M)]for _ in range(N)] #visited[x][y] x=세로N, y=가로M
visited[startx][starty][0]=1

dx=[0,0,1,-1]
dy=[1,-1,0,0]

keylist=['a', 'b', 'c', 'd', 'e', 'f']
doorlist=['A', 'B', 'C', 'D', 'E', 'F']
sol=float('inf')

def BFS(ax, ay, akey, acost): #넣기 전에 잘 생각하고 넣고 방문처리하기, 처음 좌표 방문처리하기
    global sol
    tmp=1
    q=deque([[ax,ay,akey, acost]])

    while(q):
        x,y,key,cost=q.popleft()

        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
    
            if 0<=nx<N and 0<=ny<M and visited[nx][ny][key] != 1 and miro[nx][ny]!='#':
                
                if miro[nx][ny] in doorlist :
                    door=miro[nx][ny]
                    need=chr( ord(door)+32 ) #필요한 key 문자열
                    if key & 1<<keylist.index(need) !=0:
                        visited[nx][ny][key] = 1
                        q.append([nx,ny,key, cost+1])    

                elif miro[nx][ny] in keylist :
                    get = miro[nx][ny] #key 문자열
                    newkey= key | 1<<keylist.index(get)
                    visited[nx][ny][newkey] = 1
                    q.append([nx,ny,newkey,cost+1])
                    
                elif miro[nx][ny] =='.' or miro[nx][ny]=='0':
                    visited[nx][ny][key] = 1
                    q.append([nx,ny,key,cost+1])
                    
                elif miro[nx][ny] =='1':
                    sol=min(sol,cost+1)
                
                    
BFS(startx,starty, 0,0)
if sol==float('inf'):
    print(-1)
else:
    print(sol)

BFS로 탐색할 때 이동할 수 있는 경우는 4가지이다. 문을 만날 경우, 열쇠를 만날 경우, 빈 공간을 만날 경우, 도착지를 만날 경우. 벽을 만난 경우는 방문한 적이 있는지 체크하며 함께 예외 처리한다.

큐에는 위치, 가지고 있는 열쇠, 현재까지 이동한 횟수를 하나의 배열로 묶어 저장하고 꺼낸다.

큐에서 꺼낸 위치와 4방향으로 인접한 위치의 조건(주어진 그래프를 벗어나지 않는지, 방문한 적이 있는지, 벽이 아닌지)을 살펴본 뒤 큐에 넣으면서 방문 처리를 한다.

1. 문을 만날 경우

열쇠를 갖고 있으면 방문 처리를 하며 큐에 삽입한다. 열쇠를 갖고 있는 지 비교하기 위해 & 연산자를 사용한다.

열쇠와 문이 문자열 정보로 주어지므로 아스키코드를 활용하여 비교한다.

2. 열쇠를 만날 경우

방문처리를 하며 열쇠 정보를 갱신한다.

위치, 현재까지 이동한 횟수와 함께 새로운 열쇠를 큐에 삽입한다.

3. 빈 공간을 만날 경우

방문처리를 하며 큐에 삽입한다. 중요한 점은 출발지를 만날 경우를 빈 공간을 만날 경우와 동일하게 생각해야 되는 것이다.

4. 도착지를 만날 경우

이동한 횟수의 최소를 갱신한다.

300ms대로 다른 코드들에 비해 러닝타임이 오래걸렸다. 분기 처리를 잘 정리하면 줄일 수 있을 것 같다.

댓글남기기

참고