백준 9328번 열쇠

빈칸, 벽, 문서, 열쇠, 문이 있는 평면도가 주어졌을 때, 최대로 가질 수 있는 문서의 개수를 구하는 문제입니다.

문과 같은 경우 초반에는 모두 잠겨있으므로 열쇠를 먼저 얻어야지만 문을 통과할 수 있습니다. 초반에 열쇠가 주어질 수도, 안 주어질 수도 있습니다.

처음 들어갈 수 있는 위치는 평면도의 가장자리입니다.

 

사용 변수들

X # 행 크기
Y # 열 크기
maps # 문제에서 주어진 평면도. 크기 : maps[X][Y]
keys # 열쇠를 저장할 집합
door # 평면도 탐색 중 열지 못한 문의 좌표 저장
visited # 평면도 방문 여부 저장. 크기 : visited[X][Y]

 

시작 위치 선정

들어갈 수 있는 부분은 평면도의 가장자리입니다. 그렇기 때문에 반복문을 통해 시작점의 위치를 찾을 수 있도록 했습니다.

열을 고정하고 행을 바꾸도록하고, 행을 고정하고 열을 바꾸는 식으로 가장자리를 모두 탐색할 수 있도록 했습니다.

# X: 행 크기, Y: 열 크기, find: 문서 찾기 시작 함수
for i in range(X):
    find(i,0)
    find(i,Y-1)
for i in range(1,Y-1):
    find(0,i)
    find(X-1,i)

 

시작점의 경우의 수

평면도의 가장자리에서 시작할 경우 시작하는 부분이 무엇인지 확인을 한 뒤, 탐색을 이어나가야 합니다.

시작점이 벽 혹은 이미 방문한 적이 있는 곳이라면 탐색을 이어나가지 않습니다.

def find(x,y):
    now=maps[x][y]
    
    if maps[x][y]=='*' or visited[x][y]:
        return

시작점이 빈 공간이라면 탐색을 시작합니다.

if now=='.':
    visited[x][y]=True
    dfs(x,y)

시작점이 소문자 알파벳이라면 keys 집합에 현재 소문자 알파벳을 넣어준 뒤 탐색을 시작합니다.

elif 'a'<=now<='z':
    visited[x][y]=True
    keys.add(now)
    dfs(x,y)

시작점이 대문자 알파벳이라면 두 가지 경우가 있습니다.

• 해당 알파벳의 소문자를 keys에 가지고 있다면 해당 문을 열고 나아갈 수 있으므로 탐색을 시작합니다.
• 해당 알파벳의 소문자를 keys에 가지고 있지 않다면 해당 문의 좌표를 door에 저장한 뒤 return합니다.

elif 'A'<=now<='Z':
    if now.lower() in keys:
        visited[x][y]=True
        maps[x][y]='.'
        dfs(x,y)
    else:
        door[now].append((x,y))

시작점이 문서라면 탐색을 시작합니다.

elif now=='$':
    visited[x][y]=True
    dfs(x,y)

 

전체 코드

def find(x,y):
    now=maps[x][y]

    if maps[x][y]=='*' or visited[x][y]:
        return 
        
    if now=='.':
        visited[x][y]=True
        dfs(x,y)
    elif 'a'<=now<='z':
        visited[x][y]=True
        keys.add(now)
        dfs(x,y)
    elif 'A'<=now<='Z':
        if now.lower() in keys:
            visited[x][y]=True
            maps[x][y]='.'
            dfs(x,y)
        else:
            door[now].append((x,y))
    elif now=='$':
        visited[x][y]=True
        dfs(x,y)

위와 같이 시작점의 종류에 따라 처리를 해줄 수 있도록 해주었습니다.

 

 

탐색

평면도를 탐색하는 방법은 dfs, bfs 중 어떤 것이든 상관없을 것 같습니다. 저와 같은 경우 dfs를 사용했습니다.

저와 같은 경우 문제에서 탐색 할 수 있는 모든 좌표는 dfs 함수에 거쳐가도록 했기 때문에 dfs 함수 초반에 현재 좌표가 문서일 경우 answer를 1 증가해주었습니다.

def dfs(x,y):
    global X,Y,answer
    
    if maps[x][y]=='$':
        answer+=1

그 다음 평면도 상에서 상하좌우로 움직일 수 있도록 했습니다.

상 하 좌 우로 움직이지 않는 경우는 다음과 같습니다.

• 다음 좌표가 평면도의 범위를 넘어가는 경우
• 다음 좌표가 벽일 경우
• 다음 좌표를 이미 방문한 경우

for i in range(4):
    nx,ny=moves[i][0]+x,moves[i][1]+y

    if not (0<=nx<X and 0<=ny<Y) or visited[nx][ny] or maps[nx][ny]=='*':
        continue

 

이제, 평면도에서 (nx,ny) 좌표의 종류에 따라 처리해주도록 했습니다.

• 대문자 알파벳인 경우, 문에 대한 키가 존재한다면 해당 좌표를 빈칸('.')으로 변경시켜주었습니다. 문에 대한 키가 존재하지 않다면 해당 좌표를 door에 넣어준 뒤 다음 반복문으로 넘어가도록 했습니다.

now=maps[nx][ny]
if 'A'<=now<='Z':
    if now.lower() in keys:
        maps[nx][ny]='.'
    else:
        door[now].append((nx,ny))
        continue

• 소문자 알파벳인 경우 해당 키를 keys 집합에 넣어주었습니다.

if 'a'<=now<='z':
    keys.add(now)

• 대문자 알파벳이고 해당 문에 대한 키가 존재하지 않는 경우를 제외하고는 다음 좌표로 이동 할 수 있는 경우이므로 visited값을 True로 바꿔주고 다음 좌표를 통해 dfs 함수를 재귀 호출했습니다.

visited[nx][ny]=True
dfs(nx,ny)

 

전체 코드

def dfs(x,y):
    global X,Y,answer
    
    if maps[x][y]=='$':
        answer+=1
        
    for i in range(4):
        nx,ny=moves[i][0]+x,moves[i][1]+y
        
        if not (0<=nx<X and 0<=ny<Y) or visited[nx][ny] or maps[nx][ny]=='*':
            continue
        
        now=maps[nx][ny]
        if 'A'<=now<='Z':
            if now.lower() in keys:
                maps[nx][ny]='.'
            else:
                door[now].append((nx,ny))
                continue
        
        if 'a'<=now<='z':
            keys.add(now)
        
        visited[nx][ny]=True
        dfs(nx,ny)

 

후 처리

위와 같은 방식으로 가장자리에서부터 탐색을 하게 된다면 가장자리에서부터 갈 수 있는 모든 좌표를 갈 수 있습니다. 하지만, 아직 가지 못한 부분도 존재합니다.

탐색을 하다보면 새로운 키를 찾기도 하는데 새로운 키보다 해당 키의 문을 먼저 찾았다면, 실제적으로는 해당 문을 통과 할 수 있으나 위의 로직 상에서는 문을 열지 못하게 됩니다.

그러므로, 탐색 중 찾은 문의 좌표들 중 가지고 있는 키로 열 수 있는 문이 있다면 또 탐색 할 수 있도록 해주었습니다.

while True:
    for key in list(keys):
        for x,y in door[key.upper()]:
            if visited[x][y]:
                continue

            maps[x][y]='.'
            visited[x][y]=True
            dfs(x,y)

저와 같은 경우 위의 반복문을 탈출하는 조건을 key의 개수로 파악했습니다.

위의 반복문은 현재까지 찾은 key와 맞는 문 중 방문하지 않은 문만 탐색합니다. 이 과정에서 새로운 키를 찾게 된다면, 그리고 그 새로운 키가 이전의 키들과 겹치지 않은 키라면 또 새로운 문을 열 수 있는 가능성이 생기게 되는 것입니다. 그러므로, keys 집합의 길이를 미리 저장해두고 모든 탐색이 끝난 다음, 두 길이를 비교해 반복문 탈출 여부를 정했습니다.

• 이전의 keys 집합의 길이와 현재 keys 집합의 길이가 같다면 새로운 키를 찾지 못했으므로 현재 키로 또 열 수 있는 문은 없다는 뜻이므로 반복문을 탈출합니다.
• 이전의 keys 집합의 길이와 현재 keys 집합의 길이가 다르다면 새로운 키를 찾았으므로 아직 열리지 않은 문 중 열 수 있는 문이 존재할 수 있다는 뜻이므로 다시 탐색하도록 했습니다.

while True:
    prevKeyLength=len(keys)

    ...

    if prevKeyLength==len(keys):
        break

 

dfs 함수 내에서 현재 좌표에 문서가 존재하면 정답을 1 증가시켜줬으므로, 마지막으로 답을 출력해주면 됩니다.

 

+ 리팩토링

시작점의 경우의 수에서 같은 코드가 많이 반복되는 것을 확인 할 수 있습니다. 이를 좀 더 간소화해주도록 했습니다.

각 if문 내부에서 방문 여부를 바꿔주고 dfs 함수를 실행해주는 부분이 반복되고 있으므로 이를 마지막으로 빼줌으로써 return 되지 않는 한 모든 조건에서 실행될 수 있도록 했습니다. 그리고 각 조건에서만 실행하는 부분은 if문을 통해 해당 조건에서만 실행해줄 수 있도록 바꾸어주었습니다.

def find(x,y):
    global answer
    now=maps[x][y]
    
    if maps[x][y]=='*' or visited[x][y]:
        return 
    
    if 'A'<=now<='Z':
        if now.lower() in keys:
            maps[x][y]='.'
        else:
            door[now].append((x,y))
            return
    
    if 'a'<=now<='z':
        keys.add(now)

    visited[x][y]=True
    dfs(x,y)

 

 

해결

조건들을 조금씩 빼먹고 코드를 작성하다보니 실수를 많이 했던 문제입니다. 그래도 스스로 문제를 풀어보고 리팩토링까지 해봄으로써 해결할 수 있었습니다.👍

 

문제 링크 : https://www.acmicpc.net/problem/9328

9328번: 열쇠