⭐⭐⭐[백준] [파이썬] [BFS] [구현] 9328번: 열쇠

문제집 추천, 이 문제집에 나온 유형들만 공부해도 코딩테스트는 거뜬: https://www.acmicpc.net/workbook/by/BaaaaaaaaaaarkingDog

 

9328번: 열쇠 문제 보러 가기 

9328번: 열쇠

문제

상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 필요하다. 상근이는 일부 열쇠를 이미 가지고 있고, 일부 열쇠는 빌딩의 바닥에 놓여져 있다. 상근이는 상하좌우로만 이동할 수 있다.

상근이가 훔칠 수 있는 문서의 최대 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다.

각 테스트 케이스의 첫째 줄에는 지도의 높이와 너비 h와 w (2 ≤ h, w ≤ 100)가 주어진다. 다음 h개 줄에는 빌딩을 나타내는 w개의 문자가 주어지며, 각 문자는 다음 중 하나이다.

• '.'는 빈 공간을 나타낸다.
• '*'는 벽을 나타내며, 상근이는 벽을 통과할 수 없다.
• '$'는 상근이가 훔쳐야하는 문서이다.
• 알파벳 대문자는 문을 나타낸다.
• 알파벳 소문자는 열쇠를 나타내며, 그 문자의 대문자인 모든 문을 열 수 있다.

마지막 줄에는 상근이가 이미 가지고 있는 열쇠가 공백없이 주어진다. 만약, 열쇠를 하나도 가지고 있지 않는 경우에는 "0"이 주어진다.

상근이는 처음에는 빌딩의 밖에 있으며, 빌딩 가장자리의 벽이 아닌 곳을 통해 빌딩 안팎을 드나들 수 있다. 각각의 문에 대해서, 그 문을 열 수 있는 열쇠의 개수는 0개, 1개, 또는 그 이상이고, 각각의 열쇠에 대해서, 그 열쇠로 열 수 있는 문의 개수도 0개, 1개, 또는 그 이상이다. 열쇠는 여러 번 사용할 수 있다.

출력

각 테스트 케이스 마다, 상근이가 훔칠 수 있는 문서의 최대 개수를 출력한다.

 

예제 입력 1

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

 

 

예제 출력 1

3
1
0

---

구현이라 있는 그대로 생각 그대로 했는데 안풀려서 힌트를 봤다. 

내가 놓친 것, 즉 중요한 실마리는 " 가장자리를 넘나들 수 있다는 것은 패딩으로 사이드 부분을 길로 만들어주는것 (즉, '.' 으로 감싸주면)" 이다. 

테스트케이스 첫번째에서 x 열쇠를 먹고 X 문을 열어 $를 하나 먹고 가장 오른쪽에 있는 X문을 열면 $ 2개를 먹을 수 있다. 그러나 어떻게 가장 오른쪽 X문쪽으로 갈것인가가 문제였다. 

패딩을 생각 못하였다. 

 

따라서 본 문제는 

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

2. 방문처리는 하던대로 board랑 같은 모양의 2차원 배열로 하되 새로운 열쇠를 찾으면 리셋해줘야 한다.

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

 

import sys

sys.stdin=open('input.txt', 'r')

from collections import deque

moves = [(0,1),(1,0),(0,-1),(-1,0)]


if __name__=="__main__":
    T=int(input())
    for _ in range(T):
        h,w=map(int, input().split())
        board = [['.'] + list(map(str, input().rstrip())) + ['.'] for _ in range(h)]
        board = [['.'] * (w + 2)] + board + [['.'] * (w + 2)]
        keys = list(map(str, input().rstrip()))
        
        
        cnt=0

        Q=deque()
        Q.append((0,0))
        visited = [[0] * (w + 2) for _ in range(h + 2)]
        visited[0][0]=1
        visited_doc = []  # 방문한 비밀문서 위치
        
        while Q:
            x,y = Q.popleft()
            visited[x][y]=1
            for dx,dy in moves:
                nx=x+dx
                ny=y+dy
                if 0<=nx<h+2 and 0<=ny<w+2 and board[nx][ny]!='*' and visited[nx][ny]==0:
                    
                    if board[nx][ny]=='.':              # 그냥 통로면
                        Q.append((nx,ny))
                        visited[nx][ny]=1
                        
                    elif 'a' <= board[nx][ny] <= 'z':    # 열쇠면
                        keys.append(board[nx][ny])
                        board[nx][ny]='.'
                        visited = [[0] * (w + 2) for _ in range(h + 2)]
                        Q.append((nx,ny))
                        visited[nx][ny]=1
                        
                    elif 'A' <= board[nx][ny] <= 'Z':      # 문 도달 
                        if board[nx][ny].lower() not in keys:
                            continue
                        else:
                            board[nx][ny]='.'
                            Q.append((nx,ny))
                            visited[nx][ny]=1
                            
                    elif board[nx][ny] == '$' and (nx,ny) not in visited_doc:   # 첫 비밀문서 위치 도달 
                        cnt += 1
                        board[nx][ny]='.'
                        visited_doc.append((nx,ny))
                        Q.append((nx,ny))
                        visited[nx][ny]=1
                        
        print(cnt)

 

 

처음에 항상 하던대로 위 코드로 했는데 중복되는 코드를 제거하고 깔끔하게 하면 아래와 같이 된다. 

 

import sys
from collections import deque

moves = [(0,1),(1,0),(0,-1),(-1,0)]

def in_range(nx,ny):
    return 0<=nx<h and 0<=ny<w

if __name__=="__main__":
    T=int(input())
    for _ in range(T):
        h,w=map(int, input().split())
        board = [['.'] + list(map(str, input().rstrip())) + ['.'] for _ in range(h)]
        board = [['.'] * (w + 2)] + board + [['.'] * (w + 2)]
        keys = list(map(str, input().rstrip()))
        
        
        cnt=0

        
        Q=deque()
        Q.append((0,0))
        visited = [[0] * (w + 2) for _ in range(h + 2)]
        visited[0][0]=1
        visited_doc = []  # 방문한 비밀문서 위치
        
        while Q:
            x,y = Q.popleft()
            visited[x][y]=1
            for dx,dy in moves:
                nx=x+dx
                ny=y+dy
                if nx<0 or nx>=h+2 or ny<0 or ny>=w+2 or board[nx][ny]=='*' or visited[nx][ny]==1:
                    continue
                
                # 문 도달 
                if 'A' <= board[nx][ny] <= 'Z':      
                    if board[nx][ny].lower() not in keys:   # 열 수 없음 
                        continue                
                    else:
                        board[nx][ny]='.'            
                
                # 열쇠면
                elif 'a' <= board[nx][ny] <= 'z':   
                    keys.append(board[nx][ny])
                    board[nx][ny]='.'
                    visited = [[0] * (w + 2) for _ in range(h + 2)]
                    
                # 첫 방문 비밀 문서 이면 
                elif board[nx][ny] == '$' and (nx,ny) not in visited_doc:
                    cnt += 1
                    board[nx][ny]='.'
                    visited_doc.append((nx,ny))

                
                # 그냥 통로거나, 열쇠거나, 열수있는 문이면 
                Q.append((nx,ny))
                visited[nx][ny]=1
                        
        print(cnt)