inflearn logo
강의

강의

N
챌린지

챌린지

멘토링

멘토링

N
클립

클립

로드맵

로드맵

지식공유

파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)

16. 사다리 타기(DFS)

혹시 이런방식으로 풀어도 괜찮을까요?

200

융s

작성한 질문수 4

0

선생님께선 bottom-up방식이셨네요... 전 처음에풀때 top-down방식으로 한번 해보았습니다. 혹시 이런방식도 가능한지 여쭤보고싶습니다~

def DFS(x,y):
    if x == n-1:
        if a[x][y] == 2:
            print(sp)
        return
    else:
        cnt = 0
        a[x][y] = 0

        // 갈림길 조정 - 만약에 아래로뻗는 방향밖에없다면 그대로 좌우아래 검색, 만약 아래랑 좌우중 한개가 같이있을경우 무조건 좌우만 검색하게끔
        for j in range(3):
            tx = x+dx[j]
            ty = y+dy[j]
            if 0<=tx<n and 0<=ty<n and (a[tx][ty] == 1 or a[tx][ty] == 2):
                cnt += 1
        if cnt == 1:
            loop = 3
        else:
            loop = 2
        for j in range(loop):
            tx = x+dx[j]
            ty = y+dy[j]
            
            if 0<=tx<n and 0<=ty<n and (a[tx][ty] == 1 or a[tx][ty] == 2):
                DFS(tx, ty)
                a[tx][ty] = 1
        
        for z in a:
            print(z)
        print()
n = 10
a = [
    [1,0,1,0,0,1,0,1,0,1],
    [1,0,1,1,1,1,0,1,0,1],
    [1,0,1,0,0,1,0,1,0,1],
    [1,0,1,0,0,1,0,1,1,1],
    [1,0,1,0,0,1,0,1,0,1],
    [1,0,1,1,1,1,0,1,0,1],
    [1,0,1,0,0,1,0,1,1,1],
    [1,1,1,0,0,1,0,1,0,1],
    [1,0,1,0,0,1,1,1,0,1],
    [1,0,1,0,0,2,0,1,0,1]
]

dx = [0, 0, 1]
dy = [1, -1, 0]
sp = 0
for i in range(len(a[0])):
    if a[0][i] == 1:
        sp = i
        print(sp)
        a[0][i] = 0
        DFS(0,i)

python 코테 준비 같이 해요!

답변 1

0

김태원

안녕하세요^^

네. 사다리타기는 시간복잡도를 따지는 어려운 문제는 아니라서 답만 잘 나오면 됩니다.

기존에 윈도우 10으로 잘 써왔는데 윈도우 11로 바꾸고 나서 채점이 안됩니다.

0

76

2

스택에서 ')'을 만나는 경우

0

78

3

문제가 어디있나요?

0

64

2

변수 or 함수명

0

61

1

침몰하는 타이타닉 문제 질문입니다

0

55

1

AA.py 책점 에러

0

57

1

오늘 구매했는데 파이썬 자료구조 궁금한거 있으면 답변이 잘 될까요.

0

111

2

5.동전분배하기 문제 밑에코드도 정답이될까요?

0

110

1

아나그램 비교 코드

0

116

2

AA.PY파일 복사 후 채점 진행할때 오류 발생합니다.

0

160

2

문제 링크가있나여?

0

147

2

채점기 Time Limit Exceeded 오류 문의

1

163

2

동적계획법은 사용하는 문제

0

126

2

제 코드 좀 봐주세요

0

148

1

예외가 존재할 가능성?

0

97

1

3번이 안풀립니다

0

93

0

5번 틀림

0

113

0

오류원인?

0

98

0

리스트 선언

0

106

1

침몰하는 타이타닉(그리디) 문제 질문

0

109

1

알고리즘

0

69

1

코딩테스트

0

92

1

DFS 순서 질문드립니다.

0

124

2

left, right를 사용한 풀이법에 대한 질문입니다

0

91

1