글 읽기 - [파이썬] [15684번 사다리 조작] 어떤 반례가 있을까요?

cmptr077 3년 전 0

ladder: 사다리를 탔을 때, 각 세로선에 걸린 값을 가로로 나누어 표현한 리스트

bridges: 가로선의 유무를 표현한 리스트

draw: 가로선 그리거나 지우는 함수

solve: 문제의 해답을 찾는 함수

find: x와 y를 바꿀 수 있는 가로선을 탐색하고, 각각의 경우마다 solve를 해보는 함수

반례 부탁드립니다.

추가로, 코드에 개선할 부분이 보이면 알려주셨으면 감사드리겠습니다.

import sys

def draw(ladder,bridge,N,H,bridges):    
    x=bridge[0]-1
    y=bridge[1]-1
    left=ladder[x][y]
    right=ladder[x][y+1]
    for i in range(x+1,H+1):
        for j in range(N):
            if ladder[i][j]==left:
                ladder[i][j]=right
            elif ladder[i][j]==right:
                ladder[i][j]=left
    if bridges[x][y]==True:
        bridges[x][y]=False
    else:
        bridges[x][y]=True

def find(x,y,ladder,bridges,N,H):
    for i in range(H):
        for j in range(N-1):
            if bridges[i][j]:
                continue
            if j>0:
                if bridges[i][j-1]:
                    continue
            if j<N-2:
                if bridges[i][j+1]:
                    continue            
            case1=ladder[i][j]==x and ladder[i][j+1]==y
            case2=ladder[i][j]==y and ladder[i][j+1]==x
            if case1 or case2:
                draw(ladder,[i+1,j+1],N,H,bridges)
                temp=solve(ladder,bridges,N,H)
                if temp<0:
                    draw(ladder,[i+1,j+1],N,H,bridges)
                    continue
                else:
                    return temp+1
    else:
        return -1

def solve(ladder,bridges,N,H):
    result=ladder[-1]
    if result==[i for i in range(N)]:
        return 0
    for x in range(N):
        if result[x]!=x:
            y=result[x]
            temp=find(x,y,ladder,bridges,N,H)
            if temp<0:
                continue
            else:
                return temp
    else:
        return -1 

N,M,H=map(int,sys.stdin.readline().split())
ladder=[[i for i in range(N)] for j in range(H+1)]
bridges=[[False for i in range(N-1)] for j in range(H)]
for i in range(M):
    bridge=list(map(int,sys.stdin.readline().split()))
    draw(ladder,bridge,N,H,bridges)

print(solve(ladder,bridges,N,H))

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

문제

문제

출처

ICPC

[파이썬] [15684번 사다리 조작] 어떤 반례가 있을까요?

cmptr077 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말