p.355 Chapter12 22번 블록이동하기 모범답안 시간초과

[ssooynn]

`

파이썬으로 해설과 똑같이 작성시 13번만 시간초과가납니다. 시간을 줄이는 방법을 모르겠네요 ㅜ new_board를 따로 선언해주지않고 기존의 board로 그대로 가져다써도 시간초과는 납니다..

from collections import deque


def get_nxt_pos(pos, board):
    nxt_pos=[]
    pos = list(pos)
    x1, y1, x2, y2 = pos[0][0], pos[0][1], pos[1][0], pos[1][1]
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
    for i in range(4):
        nxt_x1, nxt_y1, nxt_x2, nxt_y2 = x1+dx[i], y1+dy[i], x2+dx[i], y2+dy[i]
        if board[nxt_x1][nxt_y1] == 0 and board[nxt_x2][nxt_y2]==0:
            nxt_pos.append([(nxt_x1, nxt_y1), (nxt_x2, nxt_y2)])

    if x1 == x2:
        for i in [-1,1]:
            if board[x1+i][y1] == 0 and board[x2+i][y2] == 0:
                nxt_pos.append([(x1, y1), (x1+i, y1)])
                nxt_pos.append([(x2, y2), (x2+i, y2)])
    elif y1 == y2:
        for i in [-1,1]:
            if board[x1][y1+i] == 0 and board[x2][y2+i] == 0:
                nxt_pos.append([(x1, y1), (x1, y1+i)])
                nxt_pos.append([(x2, y2), (x2, y2+i)])
    
    return nxt_pos


def solution(board):
    n = len(board)
    visited = []
    robot =[(1, 1), (1, 2)]
    dq = deque()
    visited.append(robot)
    dq.append((robot,0))
    new_board = [[1]*(n+2) for _ in range(n+2)]
    for i in range(n):
        for j in range(n):
            new_board[i+1][j+1] = board[i][j]

    while dq:
        pos, time = dq.popleft()
        if (n,n) in pos:
            return time

        for nxt in get_nxt_pos(pos, new_board):
            if nxt not in visited:
                dq.append((nxt, time+1))
                visited.append(nxt)
    return 0

[ndb796]

안녕하세요, sy0127님.

지금 질문자님께서 작성하신 코드에서는 로봇이 존재하는 좌표 정보가 집합(set)이 아닌 리스트(list)로 관리되고 있습니다. 이렇게 하면 사실상 같은 곳을 방문했음에도 다른 지점을 방문한 것처럼 처리됩니다. 다시 말해 탐색 범위가 더 넓어지기 때문에 시간 초과 판정을 받을 여지가 있습니다.

작성하신 코드에서 nxt_pos에 들어가는 위치 정보 원소를 집합(set) 형태로 바꾸어주세요. 질문자님의 코드를 기반으로 정답 판정을 받을 수 있도록 수정한 것은 다음과 같습니다.

from collections import deque


def get_nxt_pos(pos, board):
    nxt_pos = []
    pos = list(pos)
    x1, y1, x2, y2 = pos[0][0], pos[0][1], pos[1][0], pos[1][1]
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]

    for i in range(4):
        nxt_x1, nxt_y1, nxt_x2, nxt_y2 = x1 + dx[i], y1 + dy[i], x2 + dx[i], y2 + dy[i]
        if board[nxt_x1][nxt_y1] == 0 and board[nxt_x2][nxt_y2] == 0:
            nxt_pos.append({(nxt_x1, nxt_y1), (nxt_x2, nxt_y2)})

    if x1 == x2:
        for i in [-1, 1]:
            if board[x1 + i][y1] == 0 and board[x2 + i][y2] == 0:
                nxt_pos.append({(x1, y1), (x1 + i, y1)})
                nxt_pos.append({(x2, y2), (x2 + i, y2)})
    elif y1 == y2:
        for i in [-1, 1]:
            if board[x1][y1 + i] == 0 and board[x2][y2 + i] == 0:
                nxt_pos.append({(x1, y1), (x1, y1 + i)})
                nxt_pos.append({(x2, y2), (x2, y2 + i)})

    return nxt_pos


def solution(board):
    n = len(board)
    visited = []
    robot = {(1, 1), (1, 2)}

    dq = deque()
    visited.append(robot)
    dq.append((robot, 0))
    new_board = [[1] * (n + 2) for _ in range(n + 2)]

    for i in range(n):
        for j in range(n):
            new_board[i + 1][j + 1] = board[i][j]

    while dq:
        pos, time = dq.popleft()
        if (n, n) in pos:
            return time
        for nxt in get_nxt_pos(pos, new_board):
            if nxt not in visited:
                dq.append((nxt, time + 1))
                visited.append(nxt)
    return 0

감사합니다. 나동빈 드림

[ssooynn]

감사합니다!