구현 문제 풀이

💙 백준 골드1 달이 차오른다, 가자.

문제번호	언어	메모리	시간
1194	Python 3	- KB	- ms

• 3차원 visited 사용 DFS + 비트마스킹
• DFS 종료문 : 1을 발견한 경우 Return
• Deque를 사용하여, depth가 작은 순서대로 순차적으로 append하면서 index 순서대로 pop
• 2차원 visited 배열을 사용한다면, 키를 가지고 다시 같은 위치에 돌아오지 못하므로, key값을 가지고 3차원 배열로 visited 배열을 만든다
• 그러나 2차원 visited 배열에 비트마스킹 값을 넣어주면서 해당 키를 가지고 온 적이 있냐를 확인하는 식으로 처리함 (어차피 key를 버리진 못해서 | (OR) 계산 후 같은 값이면 이미 같은 상태로 온 적이 있다는 것이기 때문에 이런식으로 계산함)
• 비트마스킹이 생소할 경우, 아래 링크 참조해서 공부해보기

비트마스킹 개념 https://travelbeeee.tistory.com/451

from collections import deque
import sys
input = sys.stdin.readline

def solve():
    n,m = map(int,input().split())
    board = [list(input().rstrip()) for _ in range(n)]
    visit = [[-1]*m for _ in range(n)]
    key = {'a':1,'b':2,'c':4,'d':8,'e':16,'f':32}
    door = {'A':1,'B':2,'C':4,'D':8,'E':16,'F':32}
    move = [(0,1),(1,0),(0,-1),(-1,0)]

    # 시작점 찾기
    q = deque()
    for i in range(n):
        for j in range(m):
            if board[i][j] == '0':
                q.append((i,j,0,0)) # x,y,cnt,bit masking
                visit[i][j] = 0
                board[i][j] = '.'
                break
        else:
            continue
        break

    while q:
        x,y,cnt,bit = q.popleft()
        for a,b in move:
            dx=x+a; dy=y+b
            if dx>=n or 0>dx or dy>=m or 0>dy or board[dx][dy] == "#":
                continue

            # 이미 왔던 곳인데 열쇠를 더 획득하지 못한 상태
            if not visit[dx][dy] == -1 and visit[dx][dy] | bit == visit[dx][dy]:
                continue
            visit[dx][dy] = bit 

            # 처음 방문
            if visit[dx][dy] == -1:
                visit[dx][dy] = 0

            if board[dx][dy] == '.':
                q.append((dx,dy,cnt+1,bit))
                continue

            if board[dx][dy] == '1':
                print(cnt+1)
                sys.exit()

            k = key.get(board[dx][dy])
            if k != None:
                # 얻은 열쇠 목록을 비트마스킹으로 갱신
                q.append((dx,dy,cnt+1,bit|k))
                continue

            # 열쇠가 있어 문을 열 수 있는 경우 큐에 담음
            d = door.get(board[dx][dy])
            if d | bit == bit:
                q.append((dx,dy,cnt+1,bit))
    print(-1)
solve()

df

문제번호	언어	메모리	시간
1194	Python 3	- KB	- ms

# 15898 피아의 아틀리에 ~신비한 대회의 연금술사~
def permutation(arr, cnt):
    result = []
    def permute(c, index):
        if len(c) == cnt:
            result.append(c)
            return
        for idx, data in enumerate(arr):
            if idx not in index:
                permute(c + [data], index + [idx])
    permute([], [])
    
def rotate(arr):
    n = len(arr)
    new = [0 * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            new[i][j] = arr[n-j-1][i]
    return new


# 3개의 4X4를 각각 (0,0), (0,1), (1,0), (1,1) 시작해서 계산하기
def bomb(a1, a2, a3, c1, c2, c3):
    kiln = [0 * 5 for i in range(5)]
    
    startIdx = [(0,0), (0,1), (1,0), (1,1)]
    for x1, y1 in range(startIdx):
        k1, color = 
        for x2, y2 in range(startIdx):
            for x3, y3 in range(startIdx):
                


n = int(input())
met = []
effect = []

for _ in range(n):
    met.append([list(map(int, input().split())) for _ in range(4)])
    effect.append([list(map(int, input().split())) for _ in range(4)])
    
# 순서가 중요하니 총 재료에서 3개 순열로 뽑음:nP3=(n==4)
# 각 재료를 4번 돌리고, 4개 위치에 넣을 수 있음:4*4
# 재료는 3개 :*3개

result = 0 # 가장 큰 값 찾기
com = [i for i in range(n)]
# 총 재료에서 3개 순열로 뽑은 거 브루트포스
for selectMets in permutation(com, 3):
    met1, met2, met3 = met[selectMets[0]], met[selectMets[1]], met[selectMets[2]]
    eff1, eff2, eff3 = effect[selectMets[0]], effect[selectMets[1]], effect[selectMets[2]]
    
    # met1 4번 rotate
    for i in range(4):
        met1 = rotate(met1)
        eff1 = rotate(eff1)
        # met2 4번 rotate
        for j in range(4):
            met2 = rotate(met2)
            eff2 = rotate(eff2)
            # met3 4번 rotate
            for k in range(4):
                met3 = rotate(met3)
                eff3 = rotate(eff3)
                # 폭탄돌리기기
                bomb(met1, met2, met3, eff1, eff2, eff3)