DFS 연습 - 사다리타기

이것도 인프런 김태원t 의 알고리즘 강의에서 제시되는 문제! DFS를 실컷 연습할 수 있어서 정말 좋다ㅎㅎ 이 강의 너무 감사하다💚

이번 문제도 손으로 정리 먼저하고 그 다음 코드를 써봤다.

 

역시나 계획단계에서 놓쳤던 점이 있었는데,

좌우에 대한 이동 후에는 방문처리를 했지만, 위로 올라간 경우에 대해서는 방문처리를 안해주었던 점이다.ㅎㅎ

이렇게 나는, 경우들을 나누다보면(혹은 우선순위에 따라 코드를 구분지어야 되게 되면..?), 동일하게 해주어야 할 처리들인데도 빼놓는 것 같다. 앞으로는 나누어진 경우더라도 동일하게 처리해야 할일이 무엇인지 짚어보는 것도 좋겠다 싶다.

board = [
    [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]
]

visit = [[0]*10 for _ in range(10)]
dx = [0, 0, -1]
dy = [-1, 1, 0]
which_column = 0

def DFS(L, x, y):
    global which_column
    if x == 0:
        which_column = y
        return
    else:
        side_exist = False
        for i in range(2):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<10 and 0<=ny<10 and board[nx][ny]==1 and visit[nx][ny] == 0:
                visit[nx][ny] = 1
                side_exist = True
                DFS(L+1, nx, ny)
        if side_exist is False:
            nx = x + dx[2]
            ny = y + dy[2]
            visit[nx][ny] = 1
            DFS(L+1, nx, ny)

for i in range(10):
    if board[9][i] == 2:
        DFS(0,9,i)

print(which_column)