[ 코드트리 삼성 SW 역량테스트 2024 하반기 오전 1번 문제 Python] 미지의 공간 탈출

https://www.codetree.ai/training-field/frequent-problems/problems/escape-unknown-space?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

⭕ CODE

import sys

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

from pprint import pprint
from collections import deque

input = sys.stdin.readline

# 동 서 남 북
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

n, m, f = map(int, input().split())

# 미지의 공간의 평면도
arr = [list(map(int, input().split())) for _ in range(n)]

# 시간의 벽의 단면도
cube = [[list(map(int, input().split())) for _ in range(m)] for _ in range(5)]

# 시간의 벽의 방문 처리
visited_cube = [[[0] * m for _ in range(m)] for _ in range(5)]

# 시간 이상 현상을 담을 time 리스트
time = []

for _ in range(f):
    x, y, d, v = map(int, input().split())
    # 여기도 못지나간다
    arr[x][y] = 1
    # x,y에서 d 방향으로 v주기 마다 생성되고
    # 0은 나중에 벽을 만나면 확산 멈추니까 그거를 판단하기 위한 0
    time.append((x, y, d, v, 0))

# 출발지는 큐브형태에 있다
for i in range(m):
    for j in range(m):
        if cube[4][i][j] == 2:
            sx = i
            sy = j
            sd = 4

# 큐브 탈출구
for i in range(4):
    for j in range(m):
        if cube[i][m - 1][j] == 0:
            ex = m - 1
            ey = j
            ed = i

# ssx, ssy는 미지의 공간 평면도 출발지점
# eex, eey는 미지의 공간 평면도 도착지점
ssx = 0
ssy = 0
eex = 0
eey = 0
flag = False
for i in range(n):
    for j in range(n):
        if arr[i][j] == 4:
            eex = i
            eey = j

# 미지의 공간 출발지점은
# 시간의 벽 단면도의 위치에 따라서 위치가 달라진다 그것을 체크하기 위해
for i in range(n):
    for j in range(n):
        if arr[i][j] == 3:
            if ed == 0:
                ssx = i + m - 1 - ey
                ssy = j + m - 1 + 1
            if ed == 1:
                ssx = i + ey
                ssy = j - 1

            if ed == 2:
                ssx = i + m - 1 + 1
                ssy = j + ey

            if ed == 3:
                ssx = i - 1
                ssy = j + m - 1 - ey

            flag = True
            break
    if flag:
        break

# 시간의 벽 탈출하기 위한 queue
q = deque()
q.append((sx, sy, 4))

visited_cube[4][sx][sy] = 1

while q:
    # x,y 좌표와 동,서,남,북,위 를 표현하기 위한 d
    x, y, d = q.popleft()

    # 탈출 좌표와 방향이라면 멈추기
    if x == ex and y == ey and d == ed:
        break

    # 같은 평면에서는 4방향으로 이동가능
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < m and 0 <= ny < m:
            if cube[d][nx][ny] == 0 and visited_cube[d][nx][ny] == 0:
                q.append((nx, ny, d))
                visited_cube[d][nx][ny] = visited_cube[d][x][y] + 1

    # 다른 평면으로 이동하는 경우

    # 현재 위치가 top 인경우
    if d == 4:
        # 맨 윗 줄에 있다면 north로 이동
        if x == 0:
            if cube[3][0][m - 1 - y] == 0 and visited_cube[3][0][m - 1 - y] == 0:
                q.append((0, m - 1 - y, 3))
                visited_cube[3][0][m - 1 - y] = visited_cube[d][x][y] + 1
        # 맨 아랫줄에 있다면 south로 이동
        if x == m - 1:
            if cube[2][0][y] == 0 and visited_cube[2][0][y] == 0:
                q.append((0, y, 2))
                visited_cube[2][0][y] = visited_cube[d][x][y] + 1
        # 가장 왼쪽이라면 west로 이동
        if y == 0:
            if cube[1][0][x] == 0 and visited_cube[1][0][x] == 0:
                q.append((0, x, 1))
                visited_cube[1][0][x] = visited_cube[d][x][y] + 1
        # 가장 오른쪽이라면 east로 이동
        if y == m - 1:
            if cube[0][0][m - 1 - x] == 0 and visited_cube[0][0][m - 1 - x] == 0:
                q.append((0, m - 1 - x, 0))
                visited_cube[0][0][m - 1 - x] = visited_cube[d][x][y] + 1

    # 현재 위치가 east 인경우
    if d == 0:
        # top으로 이동
        if x == 0:
            if cube[4][m - 1 - y][m - 1] == 0 and visited_cube[4][m - 1 - y][m - 1] == 0:
                q.append((m - 1 - y, m - 1, 4))
                visited_cube[4][m - 1 - y][m - 1] = visited_cube[d][x][y] + 1

        # south로 이동
        if y == 0:
            if cube[2][x][m - 1] == 0 and visited_cube[2][x][m - 1] == 0:
                q.append((x, m - 1, 2))
                visited_cube[2][x][m - 1] = visited_cube[d][x][y] + 1
        # north로 이동
        if y == m - 1:
            if cube[3][x][0] == 0 and visited_cube[3][x][0] == 0:
                q.append((x, 0, 3))
                visited_cube[3][x][0] = visited_cube[d][x][y] + 1

    # 현재 위치가 west 인경우
    if d == 1:
        # top으로 이동
        if x == 0:
            if cube[4][y][0] == 0 and visited_cube[4][y][0] == 0:
                q.append((y, 0, 4))
                visited_cube[4][y][0] = visited_cube[d][x][y] + 1

        # north로 이동
        if y == 0:
            if cube[3][x][m - 1] == 0 and visited_cube[3][x][m - 1] == 0:
                q.append((x, m - 1, 3))
                visited_cube[3][x][m - 1] = visited_cube[d][x][y] + 1
        # south로 이동
        if y == m - 1:
            if cube[2][x][0] == 0 and visited_cube[2][x][0] == 0:
                q.append((x, 0, 2))
                visited_cube[2][x][0] = visited_cube[d][x][y] + 1

    # 현재 위치가 south 인경우
    if d == 2:
        # top으로 이동
        if x == 0:
            if cube[4][m - 1][y] == 0 and visited_cube[4][m - 1][y] == 0:
                q.append((m - 1, y, 4))
                visited_cube[4][m - 1][y] = visited_cube[d][x][y] + 1

        # west로 이동
        if y == 0:
            if cube[1][x][m - 1] == 0 and visited_cube[1][x][m - 1] == 0:
                q.append((x, m - 1, 1))
                visited_cube[1][x][m - 1] = visited_cube[d][x][y] + 1
        # east로 이동
        if y == m - 1:
            if cube[0][x][0] == 0 and visited_cube[0][x][0] == 0:
                q.append((x, 0, 0))
                visited_cube[0][x][0] = visited_cube[d][x][y] + 1

    # 현재 위치가 north 인경우
    if d == 3:
        # top으로 이동
        if x == 0:
            if cube[4][0][m - 1 - y] == 0 and visited_cube[4][0][m - 1 - y] == 0:
                q.append((0, m - 1 - y, 4))
                visited_cube[4][0][m - 1 - y] = visited_cube[d][x][y] + 1

        # east로 이동
        if y == 0:
            if cube[0][x][m - 1] == 0 and visited_cube[0][x][m - 1] == 0:
                q.append((x, m - 1, 0))
                visited_cube[0][x][m - 1] = visited_cube[d][x][y] + 1
        # west로 이동
        if y == m - 1:
            if cube[1][x][0] == 0 and visited_cube[1][x][0] == 0:
                q.append((x, 0, 1))
                visited_cube[1][x][0] = visited_cube[d][x][y] + 1

# 미지의 공간 평면도 방문처리를 위한 visited
visited = [[0] * n for _ in range(n)]
visited[ssx][ssy] = visited_cube[ed][ex][ey] + 1

# 단면 큐브모양에서 빠져 나오는데 걸린 시간
count = visited_cube[ed][ex][ey]

# 그 시간동안 시간 이상 현상 적용해주기
for x, y, d, v, can in time:
    for i in range(1, (count // v) + 1):
        if 0 <= x + dx[d] * i < n and 0 <= y + dy[d] * i < n and arr[x + dx[d] * i][y + dy[d] * i] == 0:
            arr[x + dx[d] * i][y + dy[d] * i] = 1
        else:
            break

# 출발지점이 벽이라면 불가능하다
if arr[ssx][ssy] == 1:
    print(-1)
    sys.exit()


queue = deque()
queue.append((ssx, ssy))

# 탈출 가능한지 flag
result_flag = False

while queue:
    x, y = queue.popleft()
    # 지금까지 걸린 시간
    z = visited[x][y]

    for r, c, d, v, can in time:
        # 시간 이상 현상이 멈추었다면 넘김
        if can == 1:
            continue
        # 시간 이상 현상이 발생하는 시간이고
        # 이동하려는 좌표가 격자 안에 있다면
        if z % v == 0 and 0 <= r + dx[d] * (z // v) < n and 0 <= c + dy[d] * (z // v) < n:
            # 그리고 이동가능하다면
            # 1로 바꾸기
            if arr[r + dx[d] * (z // v)][c + dy[d] * (z // v)] == 0:
                arr[r + dx[d] * (z // v)][c + dy[d] * (z // v)] = 1
            # 이동 불가능하다면 시간 이상 현상이 앞으로 멈추게 can을 1로 바꾸기
            else:
                can = 1

    # 도착지점이라면 정답 출력하고 reuslt_flag를 가능하다고 바꾸기
    if x == eex and y == eey:
        print(visited[eex][eey] - 1)
        result_flag = True
        break

    # 4방향에 대해서
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        # 격자안에 존재하고
        if 0 <= nx < n and 0 <= ny < n:
            # 이동가능하고 방문한적이 없다면
            if arr[nx][ny] == 0 and visited[nx][ny] == 0:
                queue.append((nx, ny))
                visited[nx][ny] = visited[x][y] + 1
            # 탈출구라면
            if arr[nx][ny] == 4 and visited[nx][ny] == 0:
                queue.append((nx, ny))
                visited[nx][ny] = visited[x][y] + 1

# 만약 탈출이 불가능하다면
if result_flag == False:
    print(-1)

✏️ Comment

3차원 큐브 모양에서 빠져나온뒤 다시 2차원에서 최단 경로를 찾는것 그리고 시간 이상 현상이라는 것이 조금 구현하기 어려웠다.

큐브에서의 탈출은 단순 구현인데 신경 써야 할 부분이 조금 있다는 점에서 어렵기보다는 복잡했다. 윗면이라면 동,서,남,북 모두 이동 가능하고 동쪽에 있었다면 위, 남, 북 이런 형태로 갈 수 있는 방향이 다 달라서 그러한 내용을 하나하나 다 구현했다.
그리고 큐브에서 탈출하고 나온 장소가 이제 다시 평면에서 탈출 시작하는 위치인데 큐브 탈출 방향에 따라서 또 이 장소를 구하는 것이 달랐다.
동쪽으로 탈출한다면 y좌표가 +1, 서쪽으로 탈출한다면 y좌표가 -1, 남쪽으로 탈출한다면 x좌표 +1, 북쪽으로 탈출한다면 x좌표 -1 이런식으로 다 구하는게 조금 귀찮고 실수하기 좋았다.

그리고 출발지점이 시간이상현상으로 벽이 되는 경우를 잘 구현하지 못해서 테스트케이스에 걸렸다. 이게 만약 코테였다면 틀렸겠지

시간이상현상은 visited에 시간을 저장하였기에 visited를 기준으로 먼저 시간이상 현상을 발동시켜 arr에 변화를 주고 이동하는 방식으로 작성하였다

다른 사람들은 시간도 200ms 안이고 메모리도 25mb인데 나는 523ms시간이 걸리고 메모리도 23mb를 사용했다. 더 고민하자