[백준] 9328 열쇠 - 골드
[오늘의 문제]
https://www.acmicpc.net/problem/9328
[오늘의 학습 키워드]
- BFS, 너비 우선 탐색
- 그래프 이론, 그래프 탐색, 격자 그래프
- 구현
1. 문제설명
상근이가 빌딩을 탈출할 때 최대한 많은 비밀 문서를 가져오려고 합니다.
상근이는 빌딩의 외부에서 벽이 아닌 곳으로 출입하는데 이때 벽이 아니라는 의미는 빈 공간 혹은 문, 키 등을 의미합니다.
상근이는 문(대문자 영어)을 만났을 때 키(소문자 영어)가 있는 경우 해당 문을 열고 다음 위치로 이동합니다.
기존에 보유중인 키도 있고 빌딩에 흩어진 키를 주워서 문을 열어 이동할 수 도 있습니다.
상근이는 4방향으로만 이동이 가능할 때 최대한 많은 문서를 주울수 있는 경우를 찾아 출력하는 프로그램을 만들어야 합니다.
[제한사항]
- 시간 제한 1초
- 메모리 제한 256MB
- 2 ≤ N, M ≤ 100
- 테스트 케이스의 수는 100개를 넘지 않는다.
- '.'는 빈 공간을 나타낸다.
- '*'는 벽을 나타내며, 상근이는 벽을 통과할 수 없다.
- '$'는 상근이가 훔쳐야하는 문서이다.
- 알파벳 대문자는 문을 나타낸다.
- 알파벳 소문자는 열쇠를 나타내며, 그 문자의 대문자인 모든 문을 열 수 있다.
2. 접근방식
상근이가 최대한 많은 문서를 훔치기 위해서는 아래와 같은 전제조건이 필요합니다.
- 빌딩 외부에서 출입하기 위해 빌딩 가장자리에 빈 공간 '.' 추가
- BFS 시작위치 지정 -> 0, 0
- 키를 얻은 경우 기존에 못 열었던 문도 열 수 있기 때문에 BFS를 재시작 해주어야 한다.
- BFS를 재시작 할때 얻었던 키와 새로운 키를 구분해주어야 한다. -> 키를 얻으면 해당 자리를 빈공간으로 초기화
- BFS를 재시작 할때 얻었던 문서 역시 구분해 주어야 한다. -> 해당 자리를 빈공간으로 초기화
- BFS 재시작을 고려해 BFS는 무한 반복 되다가 재시작이 안될때 종료해주어야 한다.
- 문서를 얻게 되면 문서의 갯수를 늘려준다.
이렇게 전제조건을 모두 찾아 보았습니다.
이를 코드로 작성하고 설명해 보겠습니다.
3. 코드
import sys
input = sys.stdin.readline
from collections import deque
# 입력
T = int(input())
for _ in range(T):
N, M = map(int, input().split())
# 주변에 테두리 쳐주기
building = ['.' * (M + 2)] + [['.'] + list(map(str, input().strip())) + ['.'] for _ in range(N)] + ['.' * (M + 2)]
keys = set(input().strip()) # 중복 제거를 위해 set으로 관리
if '0' in keys:
keys = set()
# 문서 갯수 파악
answer = 0
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
# 키를 얻으면 BFS 자체를 재실시 해줘야 한다.
while True:
queue = deque([(0, 0)])
visited = [[False] * (M + 2) for _ in range(N + 2)]
visited[0][0] = True
is_restart = False # 재탐색 여부
while queue:
x, y = queue.popleft()
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
# 일단 모든 움직인은 격자 안에서
if 0 <= nx < N + 2 and 0 <= ny < M + 2:
# 방문 했거나 벽이면 건너뛰기
if visited[nx][ny] or building[nx][ny] == '*':
continue
# 아닌 경우 우선 방문처리
visited[nx][ny] = True
temp = building[nx][ny]
# 1. 문을 만난 경우
if 'A' <= temp <= 'Z':
# 문을 열수 있는 키가 없다면 건너뛰기
if temp.lower() not in keys:
continue
# 2. 키를 만난 경우
elif 'a' <= temp <= 'z':
# 키는 일단 이동할 수 있음
queue.append((nx, ny))
# 그런데 해당 키가 없는 경우
if temp not in keys:
keys.add(temp) # 키 추가후 재시작
is_restart = True # BFS 재시작
building[nx][ny] = '.' # 중복 제거를 위해 기존 키자리 없애주기
# 3. 문서를 만난 경우
elif temp == '$':
answer += 1
building[nx][ny] = '.' # 재시작시 발생될 문제 해결을 위해 초기화
queue.append((nx, ny))
# 4. 그냥 길인 경우
else:
queue.append((nx, ny))
# 재탐색 안할 경우 종료
if not is_restart:
break
print(answer)[코드설명]
import sys
input = sys.stdin.readline
from collections import deque
# 입력
T = int(input())
for _ in range(T):
N, M = map(int, input().split())
# 주변에 테두리 쳐주기
building = ['.' * (M + 2)] + [['.'] + list(map(str, input().strip())) + ['.'] for _ in range(N)] + ['.' * (M + 2)]
keys = set(input().strip()) # 중복 제거를 위해 set으로 관리
if '0' in keys:
keys = set()
# 문서 갯수 파악
answer = 0
우선 입력을 받아 줍니다.
입력을 받을때 입력받은 빌딩 정보에 테두리를 쳐줍니다.
또한 키는 중복 제거를 위해 set으로 선언해주었는데
만약 key의 입력이 0 이라면 key를 비워주었습니다.
문서의 개수를 파악하기 위해 answer를 선언하고 무한 BFS 를 구현합니다.
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
# 키를 얻으면 BFS 자체를 재실시 해줘야 한다.
while True:
queue = deque([(0, 0)])
visited = [[False] * (M + 2) for _ in range(N + 2)]
visited[0][0] = True
is_restart = False # 재탐색 여부
while queue:
x, y = queue.popleft()
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
# 일단 모든 움직인은 격자 안에서
if 0 <= nx < N + 2 and 0 <= ny < M + 2:
# 방문 했거나 벽이면 건너뛰기
if visited[nx][ny] or building[nx][ny] == '*':
continue
# 아닌 경우 우선 방문처리
visited[nx][ny] = True
temp = building[nx][ny]
일단 무한 반복할 때 시작할 때마다 BFS의 시작 위치를 고정해 주었습니다.
BFS가 재시작 될 때마다 해당 위치까지는 무조건 갈 수 있고 새롭게 찾은 길도 빈공간으로 바뀌게 되니 시작 위치를 고정해주어도
상관이 없습니다.
또한 재시작 할때마다 방문 배열을 생성해 주어야 하니 queue 탐색 밖에서 visited 배열을 생성해 주고 초기화 해주었습니다.
BFS 탐색을 실시하는데 탐색 범위는 항상 격자판을 벗어나면 안되는데 테두리를 쳐주어서 격자판의 크기가 커졌지만
BFS 시작 탐색 위치가 0, 0 으로 고정되어 있으니 범위를 설정해줍니다.
만약 해당 위치를 방문했거나, 벽이라면 해당 위치는 탐색을 할 필요가 없으니 다음 queue로 넘어갑니다.
그게 아닌 경우에는 우선 방문처리를 실시하고 해당 위치의 값을 temp로 임시 저장해줍니다.
# 1. 문을 만난 경우
if 'A' <= temp <= 'Z':
# 문을 열수 있는 키가 없다면 건너뛰기
if temp.lower() not in keys:
continue
# 2. 키를 만난 경우
elif 'a' <= temp <= 'z':
# 키는 일단 이동할 수 있음
queue.append((nx, ny))
# 해당 키가 없는 경우
if temp not in keys:
keys.add(temp) # 키 추가후 재시작
is_restart = True # BFS 재시작
building[nx][ny] = '.' # 중복 제거를 위해 기존 키자리 없애주기
# 3. 문서를 만난 경우
elif temp == '$':
answer += 1
building[nx][ny] = '.' # 재시작시 발생될 문제 해결을 위해 초기화
queue.append((nx, ny))
# 4. 그냥 길인 경우
else:
queue.append((nx, ny))
BFS 탐색을 실시하며 다음 위치를 만날때 나올 수 있는 경우의 수는 4가지가 있습니다.
1. 문을 만난 경우
문의 여부를 파악하기 위해서 해당 위치의 값이 대문자 문자인지를 파악해 줍니다.
이때 해당 문을 열수 있는 키가 없다면 해당 위치로는 이동이 불가능하기 때문에 건너뛰어 줍니다.
2. 키를 만난 경우
키를 만난 경우는 일단은 이동이 가능하기 때문에 queue의 다음 탐색 위치에 넣어줍니다.
그런데 해당 키가 기존에 없던 키라면 새로운 문을 열 수 있기 때문에 BFS를 재시작 해주어야 하죠
만약 기존에 가지고 있던 키라면 재시작을 할 필요가 없죠
기존에 없던 키라면 keys에 키를 추가해주고
BFS 재시작을 위해서 is_restart를 True로 바꿔줍니다.
이때 중복 탐색을 방지하기 위해서 기존에 키가 있던 자리를 빈공간으로 바꿔줍니다.
키가 있다면 queue에 새로운 이동 위치만 추가되고 넘어가겠죠
3. 문서를 만난 경우
문서를 찾은 경우 상근이가 훔칠 수 있는 문서의 갯수가 늘어났기때문에 answer 를 늘려주고
BFS 재시작시 중복 탐색 방지를 위해 문서의 위치를 빈공간으로 바꿔줍니다.
또 그 자리는 이동이 가능하니 queue에 넣어주죠
4. 그냥 길인 경우
이 경우는 무조건 이동이 가능하니 queue에 넣어줍니다.
# 키를 얻으면 BFS 자체를 재실시 해줘야 한다.
while True:
queue = deque([(0, 0)])
visited = [[False] * (M + 2) for _ in range(N + 2)]
visited[0][0] = True
is_restart = False # 재탐색 여부
.
.
.
# 재탐색 안할 경우 종료
if not is_restart:
break
print(answer)
이제 while문을 적절하게 종료해 주어야 합니다.
만약 is_restart가 True 면 재시작을 해주어야 하죠
False 인 경우 새로운 키를 찾지 못해 재시작할 필요가 없습니다.
따라서 이 경우 while문을 종료하고 answer를 출력하게 되죠
4. 결과
[회고]
처음에는 골드 1 난이도 치고는 쉽다고 생각 했습니다.
4가지의 조건만 구분해주면 되었기 때문이죠
그러나 키를 만난 경우 기존의 visited 배열을 초기화 하는데도 해당 칸으로 이동하지 못해서 고민을 많이 했습니다.
visited 배열을 초기화 하고 다음 이동 위치로 queue를 넣어 주었는데
생각해보면 그렇게 해도 기존에 있던 문으로는 이동이 불가능 할 수도 있어서 틀렸던 방법 이었습니다.
따라서 key를 얻으면 무조건 재시작을 위해서 함수로 구현할까 하다가 그냥 중첩 while문으로 구현 해보았습니다.
무한 반복하다가 적절하게 끊어주면 결과가 출력될 것 같았거든요
이때 또 고려하지 않았던 것은 새로운 키의 중첩 획득과 문서의 중첩 획득 이었죠
이를 파악하기 위해서 문서 배열과, 키 배열 등을 만들어서 방문 처리를 하려고 했는데
이렇게 하니까 코드가 쓸데없이 길어지고, 복잡해 졌습니다.
방법을 고민하다가 BFS를 재시작해도 기존의 building 값이 바뀌어도 BFS에는 아무 문제가 없다고 생각했고
무조건 이동이 가능한 빈 공간으로 바꿔주면 해결이 될 것 같았습니다.
따라서 그렇게 바꿔주고 실행해보니 예제 결과가 제대로 잘 나오더라구요
그대로 제출했고 통과할 수 있었습니다.
이전부터 구현 문제도 많이 풀어봤었고, BFS 문제는 기본적으로 좋아하는 문제이기도 해서 생각보다는 쉽게 맞힌 문제 같습니다.
다음에도 비슷한 문제들을 풀며 학습을 이어 나가겠습니다.