글 읽기 - 제 파이썬 코드의 잘못된 부분을 찾고 싶습니다.

mizuharaeki 3년 전 0

기존에 풀었던 코드가 채점이 거의 20분 가까이 걸리고 5300ms로 통과해서 줄이고 싶어서 2048(easy)문제에서 사용한 배열 돌리기 방법을 사용해 풀어보았습니다. 웬만한 질문 게시판의 반례는 다 돌려봤는데 전부 정답처리가 되는데, 제출해보니 채점 중간에(32%) 틀렸습니다가 나오네요.

혹시 어떤 부분이 틀렸는지 지적해주실 수 있는 분이 있으실까요.. 찾고 싶습니다. 어제 저녁과 오늘 아침 10시부터 5시간 가량 찾아보려고 해도 못 찾겠습니다 ㅜㅜ.

from copy import deepcopy
INF = 987654321

N, M = map(int, input().split())
board = [list(input()) for _ in range(N)]


def rotate(arr, N, M):
    return [[arr[i][j] for i in range(N-1, -1, -1)] for j in range(M)]


def red_rolling(lst, red, ogr):
    while lst[red-1] == '.':
        red -= 1
    if red != ogr:  # 만약 같다면 바로 옆이 .이 아니란 소리므로 이동 X
        lst[red] = 'R'
        lst[ogr] = '.'


def blue_rolling(lst, blue, ogb):
    while lst[blue-1] == '.':
        blue -= 1
    if blue != ogb:
        lst[blue] = 'B'
        lst[ogb] = '.'


def rolling(lst):
    new_lst = deepcopy(lst)
    red, blue = -1, -1
    origin_red, origin_blue = -1, -1
    if new_lst.count('R'):
        red = new_lst.index('R')
        origin_red = red
    if new_lst.count('B'):
        blue = new_lst.index('B')
        origin_blue = blue
    if red != -1 and blue != -1:
        if red < blue:  # 둘 다 같은 행에 있을 경우 작은 쪽 먼저 진행
            red_rolling(new_lst, red, origin_red)
            blue_rolling(new_lst, blue, origin_blue)
        else:
            blue_rolling(new_lst, blue, origin_blue)
            red_rolling(new_lst, red, origin_red)
    elif red != -1:
        red_rolling(new_lst, red, origin_red)
    elif blue != -1:
        blue_rolling(new_lst, blue, origin_blue)

    return new_lst


def DFS(A, time, N, M):
    if time > 10:
        return INF
    result = INF
    for _ in range(4):
        X = [rolling(i) for i in A]
        second_result = INF
        for i in X:
            o = i.count('O')
            r = i.count('R')
            b = i.count('B')
            if o and r and b:
                o_idx, r_idx, b_idx = i.index('O'), i.index('R'), i.index('B')
                if o_idx+1 == r_idx and r_idx+1 != b_idx or b_idx+1 != r_idx and r_idx+1 == o_idx:
                    second_result = time
                    break
                elif o_idx+1 == r_idx and r_idx+1 == b_idx or b_idx+1 == r_idx and r_idx+1 == o_idx or b_idx+1 == o_idx or o_idx+1 == b_idx:
                    second_result = 0
                    break
            elif o and r:
                o_idx, r_idx = i.index('O'), i.index('R')
                if o_idx+1 == r_idx or r_idx+1 == o_idx:
                    second_result = time
                    break
            elif o and b:
                o_idx, b_idx = i.index('O'), i.index('B')
                if o_idx+1 == b_idx or b_idx+1 == o_idx:
                    second_result = 0
                    break
        if second_result and second_result != INF:
            result = min(result, second_result)
        elif second_result == INF and X != A:
            result = min(result, DFS(X, time+1, N, M))
        A = rotate(A, N, M)
        N, M = M, N
    return result


res = DFS(board, 1, N, M)
if res == INF:
    print(-1)
else:
    print(res)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

제 파이썬 코드의 잘못된 부분을 찾고 싶습니다.

mizuharaeki 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말