아래 코드를 보시면 아시겠지만...
많이 지저분 합니다..ㅠㅠ
아직 파이썬의 능력을 끌어내기에는 역부족인듯합니다...
이 복잡한 코드를 간략히 우선 설명드리자면
테스트코드를 포함하고있습니다.
재귀함수 형태로 구현하였습니다.
입력된 보드에서 행 또는 열이 모두 공백인 경우 해당 영역을 삭제합니다. (입력에따라서는 불필요 또는 안하니만 못한 상황이 발생할 수 있습니다)
해당 보드의 모든 칸에 대하여 가능성을 판단합니다.
2.1 3번 이상 꺽였거나, 보드를 벗어낫을 때 재귀 종료
2.2 공백이 아닌칸에 도달하였을 때 답을 체크하거나 종료
2.3 더 뻗어나가야할 경우 상하좌우로 재귀함수 호출
2.3.1 뒤로 가지는 못함
2.3.2 방향이 전환되었을 경우 코스변경카운트를 증가
2.2에서 답을 체크할때마다 결과값을 증가시키며, 해당 결과를 출력
이상입니다.
짝을 찾아내는 수학적(?) 알고리즘을 따로 생각해내지 못하여 탐색토록 하였습니다.
해당 문제는 오답이 아닌 시간초과인 관계로... 알고리즘 자체가 글러먹은 녀석일 수 있습니다..ㅠㅠ
랜덤으로 돌려보아도 작은 케이스가 아니고서는 답을 정확히 판단할 수가 없어서 큰 케이스는 결과가 나오는 것만 확인하였습니다.
채점에서 어떤 입력을 사용하는지는 알 수 없으나 5초라는 시간이 다 소비될만큼 길게 돌아가지는 않는 녀석으로 보입니다 ㅠㅠ
혹시 이 상황을 보고 '이게 문제네!!' 하고 딱 떠오르시거나 문제가 될만한 input 을 알고계신다면 답변 부탁드립니다
감사합니다!
코드 블럭
importrandomdefprintBoard():print''foriinboard:printreduce(lambdax,y:x+y,i)print''deffindRemovablePair(nextX,nextY,startX,startY,curveCount,lastDirection):globalfindCountifcurveCount>3:returnifnextX<0ornextX>board[0].__len__()-1ornextY<0ornextY>board.__len__()-1:returnifboard[nextY][nextX]==board[startY][startX]andlastDirection!=0:if(nextY,nextX,startY,startX)infindListor(startY,startX,nextY,nextX)infindList:returnelse:findList.append((nextY,nextX,startY,startX))findCount+=1returnifboard[nextY][nextX]!='.'andlastDirection!=0:returniflastDirection!=2:findRemovablePair(nextX+1,nextY,startX,startY,lastDirection==1andcurveCountorcurveCount+1,1)iflastDirection!=1:findRemovablePair(nextX-1,nextY,startX,startY,lastDirection==2andcurveCountorcurveCount+1,2)iflastDirection!=4:findRemovablePair(nextX,nextY+1,startX,startY,lastDirection==3andcurveCountorcurveCount+1,3)iflastDirection!=3:findRemovablePair(nextX,nextY-1,startX,startY,lastDirection==4andcurveCountorcurveCount+1,4)defrefreshBoard(target):iftarget.__len__()<1:returnforiinreversed(range(target.__len__())):iffilter(lambdax:x!='.',target[i]).__len__()==0:deltarget[i]foriinreversed(range(target[0].__len__())):count=0forjinrange(target.__len__()):iftarget[j][i]!='.':breakcount+=1ifcount==target.__len__():forkinrange(target.__len__()):deltarget[k][i]foriinrange(board.__len__()):board[i].insert(0,'.')board[i].append('.')board.insert(0,['.'forcolinrange(board[0].__len__())])board.append(['.'forcolinrange(board[0].__len__())])forlllinrange(input()):#for lll in range(100):globalboardglobalfindCountglobalfindListif1==2:boardSize=[random.randrange(3,51),random.randrange(3,51)]board=[['.'forcolinrange(boardSize[1])]forrowinrange(boardSize[0])]foriinrange(boardSize[0]):forjinrange(boardSize[1]):temp=random.randrange(97,117)iftemp<107:board[i][j]=chr(temp)else:boardSize=map(lambdax:int(x),raw_input().split())board=[['.'forcolinrange(boardSize[1])]forrowinrange(boardSize[0])]foriinrange(boardSize[0]):inputBoard=raw_input()forjinrange(inputBoard.__len__()):ifinputBoard[j]!='.':board[i][j]=inputBoard[j]refreshBoard(board)findCount=0findList=[]foriinrange(board.__len__())[1:board.__len__()]:forjinrange(board[0].__len__())[1:board[0].__len__()]:ifboard[i][j]!='.':findRemovablePair(j,i,j,i,0,0)printfindCount}
2번꺽는 것(직선3개)으로는 평행선으로는 가능하나 원위치로 올 수가 없어서 (ㄷ 형태이기때문에) 제자리로 오지 않을거라 판단하고 있습니다 ㅠ
새로운 언어 공부할 겸 알고리즘문제로 머리도 써볼겸 둘을 접목해서 파이썬으로 알고스팟을 뚫고있어요 ㅋ 원래 C 쪽이었는데 다른 코드들 퍼포먼스를 보면 막 C 로 하고싶어지네요
하지만 파이선 공부가 목적이니 끝까지 파이썬으로 ㅋㅋ
파이썬으로 한바퀴 돌고나면 Go를 써볼까 합니다
조언주신 부분은 적극 참고하도록 하겠습니다
감사해요!!
memorys
안녕하세요 사청성 문제 관련 문의 드립니다.
SHISENSHO
https://algospot.com/judge/problem/read/SHISENSHO
아래 코드를 보시면 아시겠지만...
많이 지저분 합니다..ㅠㅠ
아직 파이썬의 능력을 끌어내기에는 역부족인듯합니다...
이 복잡한 코드를 간략히 우선 설명드리자면
테스트코드를 포함하고있습니다.
재귀함수 형태로 구현하였습니다.
해당 보드의 모든 칸에 대하여 가능성을 판단합니다.
2.1 3번 이상 꺽였거나, 보드를 벗어낫을 때 재귀 종료
2.2 공백이 아닌칸에 도달하였을 때 답을 체크하거나 종료
2.3 더 뻗어나가야할 경우 상하좌우로 재귀함수 호출
2.2에서 답을 체크할때마다 결과값을 증가시키며, 해당 결과를 출력
이상입니다.
짝을 찾아내는 수학적(?) 알고리즘을 따로 생각해내지 못하여 탐색토록 하였습니다.
해당 문제는 오답이 아닌 시간초과인 관계로... 알고리즘 자체가 글러먹은 녀석일 수 있습니다..ㅠㅠ
랜덤으로 돌려보아도 작은 케이스가 아니고서는 답을 정확히 판단할 수가 없어서 큰 케이스는 결과가 나오는 것만 확인하였습니다.
채점에서 어떤 입력을 사용하는지는 알 수 없으나 5초라는 시간이 다 소비될만큼 길게 돌아가지는 않는 녀석으로 보입니다 ㅠㅠ
혹시 이 상황을 보고 '이게 문제네!!' 하고 딱 떠오르시거나 문제가 될만한 input 을 알고계신다면 답변 부탁드립니다
감사합니다!
코드 블럭
파이썬 2.7에 파이참사용하였습니다
8년 전