23031. 으어어… 에이쁠 주세요..

문제의 내용이 궁금하시다면, 아래의 링크를 클릭해주세요!
문제 보러 가기

접근 과정

얼핏 보았을 때에는 BFS 유형의 문제가 아닐까 생각했지만, 주어지는 문자열 A의 길이만큼 동작을 수행하는 시뮬레이션 문제임을 알 수 있었다.

아리는 언제 기절할까?

문제에서 제시하는 조건을 고려했을 때, 아리가 기절하는 경우는 아래의 2가지이다.

• 불이 꺼진 칸이면서, 아리가 이동한 칸에 좀비가 있었던 경우
• 불이 꺼진 칸이면서, 좀비가 이동한 칸에 아리가 있었던 경우

두 경우 모두, 불이 꺼져있는 칸이라는 조건이 필요하다.

그리고 아리가 이동했는데, 그 칸에 좀비가 있었거나 또는 좀비가 이동했는데, 그 칸에 아리가 있었던 경우에 아리가 기절하게 된다.

여기서 유추할 수 있는 내용은 아래와 같다!

• 아리가 이동한 후에, 해당 좌표에 좀비가 있는지 확인해야 한다
• 좀비가 이동한 후에, 해당 좌표에 아리가 있는지 확인해야 한다

주의할 점 1

아리가 이동하면서 스위치(S)를 키는 경우, 해당 좌표와 인접한 8방향에 걸쳐 불을 키게 된다.
여기서, 인접한 8방향의 좌표들 안에 또 다른 스위치가 있을 수 있다.
이 때, 해당 스위치의 좌표는 별개로 취급해야 한다!!

아리가 스위치를 향해 아래로 한 칸 이동하는 상황을 가정해보자.

아리가 스위치에 있는 칸에 도착하면, 스위치를 키게 되며 인접한 8방향에 불을 키게 된다.

그런데 여기서, 인접한 칸 중에 스위치가 있다면 어떻게 처리해야 할까?

해당 칸 역시 스위치로부터 인접한 칸이기에 불이 켜지게 되지만, 아래의 예시 코드처럼 배열 내에서 불이 켜진 칸에 대해 별도의 값을 부여하는 경우, 기존 배열에서 스위치를 의미하는 값 S가 다른 값으로 덮어지는 문제가 발생한다!
이 경우, 이후에 해당 칸으로 이동했을 때 스위치가 동작하지 않을 수 있다.

for i in range(8):
    tx, ty = x + dx[i], y + dy[i]
    arr[tx][ty] = "lighted"

따라서, 스위치를 통해 불이 켜지는 인접 좌표 중 스위치가 있는 칸이 있다면, 해당 칸에 이동했을 때 스위치가 제대로 동작할 수 있게끔 별도 처리가 필요하다.

주의할 점 2

주어지는 키워드(L, R, F)에 따라 이동한 좌표가 주어진 배열 N x N의 범위를 벗어나는 경우, 아리는 그 자리에 머무르지만, 좀비는 제 자리에서 방향을 반대로 전환한다는 점을 주의해야 한다!

정리하면?

• 불이 꺼진 칸이라는 조건 하에, 아리는 2가지 경우에 기절할 수 있다.
  • 아리가 이동한 좌표에서 좀비를 만나거나
  • 좀비가 이동한 좌표에서 아리를 만나거나
• 주어지는 키워드(L, R, F)에 따라 아리를 먼저 이동시키고, 그 후에 좀비가 이동한다.
  • L이나 R인 경우, 아리는 방향만 좌/우로 전환한다.
  • F인 경우, 아리는 주어진 방향으로 한 칸 전진한다.
    • 아리가 이동한 좌표에 스위치가 있는 경우, 인접한 8방향을 밝히는데, 인접한 좌표 중 스위치가 있는 경우에는 스위치가 제대로 기능할 수 있게 별도로 처리한다.
  • 좀비는 키워드와 무관하게 무조건 바라보는 방향으로 한 칸 전진한다.
• 아리 또는 좀비가 이동을 완료하고 나면, 해당 좌표에서 각자가 만나는지 검증해 아리의 기절 여부를 확인한다.

풀이

move_x = [-1, 0, 1, 0, -1, 1, -1, 1] # 상우하좌 좌상좌하우상우하
move_y = [0, 1, 0, -1, -1, -1, 1, 1]

# 아리의 이동
def go_ari(x, y, direction):
    global faint_flag
    # 방향에 따라 이동한 좌표가 N x N 범위 내의 올바른 좌표인지 검증
    tx, ty = x + move_x[direction], y + move_y[direction]
    if 0 <= tx < N and 0 <= ty < N:
        # 이동한 좌표에 스위치가 있는 경우, 8방향에 걸쳐서 불을 킨다.
        if arr[tx][ty] == "S":
            for i in range(8):
                turn_on_x, turn_on_y = tx + move_x[i], ty + move_y[i]
                # 여기서 주의할 점은, 8방향 내 다른 스위치가 있는 경우, 그 스위치는 두어야 한다. 다른 값으로 덮어씌우지 말 것!
                if arr[turn_on_x][turn_on_y] != "S":
                    arr[turn_on_x][turn_on_y] = "L"
            return tx, ty
        # S(스위치), L(불 켜진 곳)도 아닌 좌표 -> 불 꺼진 좌표에서 좀비를 만난 경우는 기절한다.
        if arr[tx][ty] not in ["S", "L"] and zombie_map[tx][ty] == 1:
            faint_flag = True
            return tx, ty

        # 기절하지 않고 이동을 완료하였다.
        return tx, ty
    else:
        # 배열 범위를 벗어나는 좌표라면, 아리는 제자리에 머문다.
        return x, y


# 좀비의 이동
def go_zombie(x, y, direction):
    global faint_flag, ari_x, ari_y
    # 방향에 따라 이동한 좌표가 N x N 범위 내의 올바른 좌표인지 검증
    tx, ty = x + move_x[direction], y + move_y[direction]
    if 0 <= tx < N and 0 <= ty < N:
        # S(스위치), L(불 켜진 곳)도 아닌 좌표 -> 불 꺼진 좌표에서 아리를 만나면, 아리는 기절한다.
        if arr[tx][ty] not in ["S", "L"] and ari_x == tx and ari_y == ty:
            faint_flag = True
            return tx, ty, direction

        # 좀비의 이동에 따라, 위치를 변경한다.
        zombie_map[x][y] = 0
        zombie_map[tx][ty] = 1

        return tx, ty, direction
    else:
        # 배열 범위를 벗어나는 좌표라면, 좀비는 제 자리에서 반대 방향으로 방향을 전환한다.
        direction = (direction + 2) % 4
        return x, y, direction


N = int(input())
order = list(input())
arr = [list(input()) for _ in range(N)]
zombie_map = [[0] * N for _ in range(N)] # 좀비의 위치를 담는 N x N 사이즈의 배열
ari_x, ari_y = 0, 0                      # 아리의 초기 위치
ari_direction = 2                        # 아리의 초기 방향
zombie_list = [[x, y, 2] for x in range(N) for y in range(N) if "Z" in arr[x][y]]        # 좀비 역시 초기 방향은 아래이기에, [x축, y축, 2(방향)] 식으로 추가
for x, y, k in zombie_list:              # 좀비 배열 내 위치 값 추가
    zombie_map[x][y] = 1
faint_flag = False

# 주어진 배열 order의 순서에 따른 이동
for single in order:
    if single == 'F':
        ari_x, ari_y = go_ari(ari_x, ari_y, ari_direction)
    elif single == "L":
        ari_direction = (ari_direction - 1) % 4
    elif single == "R":
        ari_direction = (ari_direction + 1) % 4

    # 매 시점마다, 좀비(들)의 이동
    for i in range(len(zombie_list)):
        # 좀비의 위치를 zombie_map처럼 별개의 배열로 관리하고 있음
        zombie_x, zombie_y, zombie_direction = go_zombie(zombie_list[i][0], zombie_list[i][1], zombie_list[i][2])
        # 좀비의 이동 이후, zombie_list 내에서 각 좀비의 위치와 방향 값을 갱신한다.
        zombie_list[i] = [zombie_x, zombie_y, zombie_direction]

    # 아리의 이동, 좀비의 이동을 통해 아리가 기절해버린 경우
    if faint_flag:
        print("Aaaaaah!")
        break

# 기절하지 않은 경우
if not faint_flag:
    print("Phew...")

통과!

읽어주셔서 감사합니다!