SWEA 1211. Ladder2(Python)(D4)

Wjong·2023년 2월 1일
0

swea

목록 보기
19/36


설명을 안보고 2차원 배열만 보고 무작정 bfs로 접근했다가, 시간낭비..
우리가 알고있는 사다리타기 문제다.
기본적으로 한 출발지점에서 내려가면서, 좌 or 우 에 경로가 있을 경우 내려가지 않고 건너간다.
여기서 좌, 우에 동시에 다리가 있는경우는 없다! 그런사다리타기는 존재하지않으므로(좌우 동시에 존재할 경우 bfs를 써야겠지..?)
그리고 도착횟수가 같을경우 출발지점의 idx가 높은것을 리턴 --> 어차피 출발지점을 idx 1 부터 순회하므로 크게 문제없음!)

res=[]
def go(st):
    global tmp
    x,y=1,st
    count=1
    while x!=100:
        if 2<=y and li[x][y-1]==1:
            while 2<=y and li[x][y-1]==1:
                y-=1
                count+=1
        elif y<=99 and li[x][y+1]==1:
            while y<=99 and li[x][y+1]==1:
                y+=1
                count+=1
        x+=1
        count+=1
    if count<=tmp[1]:
        tmp=[st,count]

for m in range(10):
    tmp=[0,10**9]
    _=input()
    li=[[0]*(101)]
    for i in range(100):
        li.append([0]+list(map(int,input().split())))
    for i in range(1,101):
        if li[1][i]==1:
            go(i)
    
    res.append(tmp[0]-1)
for i in range(len(res)):
    print("#%d %s"%(i+1,res[i]))
profile
뉴비

0개의 댓글