문제의 내용이 궁금하시다면, 아래의 링크를 확인해주세요!
문제 보러 가기
접근 과정
W, U, D, L, R 로 구성된 문자열 안에서, 하나씩 읽어나가며 그에 맞는 동작을 수행해나간다는 점에서 기본적으로 시뮬레이션 문제라는 점을 알 수 있었다!
그리고, 와드를 설치하였을 때, 해당 칸이 속한 영역을 전부 탐색하며 시야를 확보한다는 점에서 BFS를 사용해야 한다는 점도 알 수 있었다.
2차원 배열 상에서의 이동에 대한 시뮬레이션 문제라는 점에서, 이전에 풀어보았던 23031번 문제가 떠올랐다!
해당 문제에 대한 풀이는 이 글을 참고해주세요!
해당 문제와 이번 와드 문제의 차이라면, 와드 명령 수행시 현재 위치한 칸과 동일한 영역에 속한 칸들을 탐색한다는 점이 될 것 같다.
주의할 점 1
모든 동작이 끝나기 전까지는, 지나온 경로에 대해서 시야를 확보하지 않는다!
다시 말하자면, W가 아닌 U, D, L, R 명령에 맞게 맵 안에서 이동하는 과정에서는 위치한 칸과 인접한 4방향에 시야를 확보하는 작업을 하지 않는다는 것을 말한다.
이 부분을 처음에 파악하지 못해 어려움을 겪었다. 이래서 문제를 끝까지 읽어야 한다..
주의할 점 2
문제에서 주어지는 한별이의 위치는 2차원 배열의 크기 R과 C 이내의 값인데, R과 C 모두 1부터 시작하므로 주어지는 위치 HR과 HC의 값에서 1을 먼저 빼주는 편이 다루기에 편리하다!
정리하면?
- 주어지는 일련의 명령에 따라, 동작을 수행하는 시뮬레이션 문제이다!
- 주어진 명령이 W(와드 심기)가 아니라면, 방향에 맞게 이동해나간다.
- W 명령이 들어왔을 때만 BFS를 진행한다!
- 모든 명령을 수행한 후에, 현재 위치를 포함한 인접 4방향의 시야를 밝힌다.
- 최종적으로 밝혀진 시야 맵을 한 줄씩 출력해주자!
풀이
import sys
from collections import deque
direction = {'W': (0, 0), 'U': (-1, 0), 'D': (1, 0), 'L': (0, -1), 'R': (0, 1)}
def ward(x, y, type):
Q = deque()
Q.append([x, y])
sight_map[x][y] = "."
while Q:
x, y = Q.popleft()
for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
tx, ty = x + dx, y + dy
if 0 <= tx < R and 0 <= ty < C and sight_map[tx][ty] != "." and isekai_map[tx][ty] == type:
sight_map[tx][ty] = "."
Q.append([tx, ty])
input = sys.stdin.readline
R, C = map(int, input().strip().split())
isekai_map = [list(input().strip()) for _ in range(R)]
sight_map = [["#"] * C for _ in range(R)]
now_x, now_y = map(int, input().strip().split())
now_x -= 1
now_y -= 1
order = list(input().strip())
for single_order in order:
order_x, order_y = direction.get(single_order)
if order_x == order_y:
ward(now_x, now_y, isekai_map[now_x][now_y])
else:
now_x, now_y = now_x + order_x, now_y + order_y
sight_map[now_x][now_y] = "."
for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
tx, ty = now_x + dx, now_y + dy
if 0 <= tx < R and 0 <= ty < C:
sight_map[tx][ty] = "."
for _ in sight_map:
print("".join(_))통과!
느낀 점
이번 문제를 풀이하며, 딕셔너리 객체에서 get() 메서드를 사용하는 방법에 대해 알게 되었다!
이전까지는 딕셔너리 객체 내에 키와 값들을 정의하고, 키를 통해 접근하는 방식을 사용하곤 하였다.
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
direction = {'U': 0, 'D': 1, 'L': 2, 'R': 3}
for single_move in order:
changed_x, changed_y = now_x + dx[direction[single_move]], now_y + dy[direction[single_move]]이 경우, 딕셔너리에 정의되지 않은 키의 경우 KeyError가 발생하게 된다.
하지만 딕셔너리의 get() 메서드를 사용하면, 인자로 전달한 키의 값을 반환해준다. 참조하고자 하는 키가 딕셔너리 객체에 존재하지 않더라도, 키에러를 발생시키지 않고 None 값을 리턴한다!
조금 더 안전하게 작동하는 코드를 사용하는 법을 배우게 된 것 같다.
읽어주셔서 감사합니다!
