글 읽기 - 파이썬3 15684번 문제 제 코드에 대한 반례 케이스를 알려주실 수 있을까요?

starkisuk305 3년 전 0

가로로 길 놓는 방법은

board라는 변수에 1이랑 2를 넣어 좌,우 구분과 함께 길 유무를 나타내었습니다.

일단 파이썬3로 돌렸을때 시간초과가 나는데.. 이부분은 너무 많은 for구문때문에 그런것 같긴한데..

pypy3로 채점이 돌려져서 돌려봤더니 틀렸다고 나옵니다.

질문게시글에 있는 반례들을 넣어 봤는데 틀리게 나온는 반례가 없어서 어디서 문제가 생기는지 계속 못 찾고 있습니다.

반례가 뭐가 있을까요..?

from sys import stdin
import copy
from itertools import combinations
input = stdin.readline
n, m, h = map(int,input().strip().split())
road_location = [[(int(i)-1) for i in input().strip().split()] for _ in range(m)]
board = [[0]*n for _ in range(h)]
ans = -1
for i in range(h):
    for j in range(n):
        if [i,j] in road_location:
            board[i][j] = 1
            board[i][j+1] = 2

def bf(b):
    a = 0
    while a<h:
        if c_board[a][b] == 1:
            b += 1
        elif c_board[a][b] == 2:
            b -= 1
        a += 1
    return b

if m == 0:
    ans = 0
else:
    no_location = []
    for i in range(h):
        for j in range(n):
            if board[i][j] == 0:
                if j+1<n:
                    if board[i][j+1] == 0:
                        no_location.append((i,j,i,j+1))
    count = 0
    e = 1
    ans = -1
    if count == 0 and e == 1 and len(no_location) >= 1:  # 선1개
        count += 1
        c_board = copy.deepcopy(board)
        for i,j,k,t in no_location:
            c_board[i][j] = 1
            c_board[k][t] = 2
            v_count = 0
            for v in range(n):
                if bf(v) == v:
                    v_count += 1
            if v_count == n:
                e = 0
                ans = 1
                break
            c_board[i][j] = 0
            c_board[k][t] = 0
    if count == 1 and e == 1 and len(no_location) >= 2:  # 선2개
        count += 1
        c_board = copy.deepcopy(board)
        no_location_2 = list(combinations(no_location, 2))
        for z in no_location_2:
            temp = []
            for i,j,k,t in z:
                temp.append((i,j,k,t))
                c_board[i][j] = 1
                c_board[k][t] = 2
            v_count = 0
            if temp[0][0] == temp[1][0]:
                if temp[0][1] == temp[1][1]-1 or temp[0][1] == temp[1][1]+1:
                    for i, j, k, t in z:
                        c_board[i][j] = 0
                        c_board[k][t] = 0
                    continue
            for v in range(n):
                if bf(v) == v:
                    v_count += 1
            if v_count == n:
                e = 0
                ans = 2
                break
            for i,j,k,t in z:
                c_board[i][j] = 0
                c_board[k][t] = 0
    if count == 2 and e == 1 and len(no_location) >= 3:  # 선3개
        count += 1
        c_board = copy.deepcopy(board)
        no_location_3 = list(combinations(no_location, 3))
        for z in no_location_3:
            temp = []
            for i,j,k,t in z:
                temp.append((i, j, k, t))
                c_board[i][j] = 1
                c_board[k][t] = 2
            v_count = 0
            if temp[0][0] == temp[1][0]:
                if temp[0][1] == temp[1][1]-1 or temp[0][1] == temp[1][1]+1:
                    for i, j, k, t in z:
                        c_board[i][j] = 0
                        c_board[k][t] = 0
                    continue
            if temp[1][0] == temp[2][0]:
                if temp[1][1] == temp[2][1]-1 or temp[1][1] == temp[2][1]+1:
                    for i, j, k, t in z:
                        c_board[i][j] = 0
                        c_board[k][t] = 0
                    continue
            if temp[2][0] == temp[0][0]:
                if temp[2][1] == temp[0][1]-1 or temp[2][1] == temp[0][1]+1:
                    for i, j, k, t in z:
                        c_board[i][j] = 0
                        c_board[k][t] = 0
                    continue
            for v in range(n):
                if bf(v) == v:
                    v_count += 1
            if v_count == n:
                e = 0
                ans = 3
                break
            for i,j,k,t in z:
                c_board[i][j] = 0
                c_board[k][t] = 0
print(ans)

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

문제

문제

출처

ICPC

파이썬3 15684번 문제 제 코드에 대한 반례 케이스를 알려주실 수 있을까요?

starkisuk305 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말