[Algorithms] 깊이/넓이 우선 탐색 (DFS, BFS) 활용-사다리 타기(DFS, BFS 2가지 방법으로)

 

 

• 특정 목적지의 좌표에서부터 출발해서 행이 0인 라인에 도착할 때까지 이동하면 되는 문제 
• 이동은 오른쪽 , 왼쪽, 위 순으로 하도록 한다 - 사다리 타기는 위 보다는 좌우 이동이 먼저이다 
• 다시 뒤로 돌아가는 경우를 생각하면 안되니 중복을 방지해야 한다 

 

 

BFS 방법으로 풀어보기 

if __name__=='__main__':
 
    game = [list(map(int, input().split())) for _ in range(10)]
    dx = [0, 0, -1]
    dy = [1, -1, 0]
 
    queue = deque()
    for i in range(10):
        if game[9][i] == 2:
            des_x, des_y = 9, i
            queue.append((des_x, des_y))
 
    while queue:
        now = queue.popleft()
        if now[0] == 0:
            print(now[1])
            break
 
        for i in range(3):
            x = now[0] + dx[i]
            y = now[1] + dy[i]
            if 0<=x<10 and 0<=y<10 and game[x][y]==1:
                game[x][y]=0        # 중복을 방지하기 위해서 
                queue.append((x,y))
                break
 

def DFS(x, y):
 
    game[x][y] = 0
 
    if x == 0:
        print(y)
    else:
        if y+1 < 10 and game[x][y+1] == 1:
            game[x][y+1] = 0
            DFS(x, y+1)
        elif y-1 >= 0 and game[x][y-1] == 1:
            game[x][y-1] = 0
            DFS(x, y-1)
        elif x-1 >= 0 and game[x-1][y] == 1:
            game[x-1][y] = 0
            DFS(x-1, y)
 
if __name__=='__main__':
 
    game = [list(map(int, input().split())) for _ in range(10)]
 
    for i in range(10):
        for j in range(10):
            if game[i][j] == 2:
                DFS(i, j)