[DFS활용] - 사다리타기

사다리타기

 

현수와 친구들은 과자를 사먹기 위해 사다리 타기를 합니다.

사다리 표현은 2차원 평면은 0으 로 채워지고, 사다리는 1로 표현합니다.

현수는 특정도착지점으로 도착하기 위해서는 몇 번째 열에서 출발해야 하는지 알고싶습니다.

특정 도착지점은 2로 표기됩니다.

여러분이 도와주세 요. 사다리의 지도가 10*10이면

 

특정목적지인 2에 도착하려면 7번 열 출발지에서 출발하면 됩니다.

 

▣ 입력설명
10*10의 사다리 지도가 주어집니다.

▣ 출력설명
출발지 열 번호를 출력하세요.

 

▣ 입력예제 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 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

▣ 출력예제 1

7

 

나의 코드

def DFS(x,y):
    if x==0:
        print(y)

    if 0<=y+1<10 and arr[x][y+1]==1:
        arr[x][y+1]=0
        DFS(x,y+1)
    elif 0<=y-1<10 and arr[x][y-1]==1:
        arr[x][y-1]=0
        DFS(x,y-1)
    elif 0<=x-1<10 and arr[x-1][y]==1:
        
        arr[x-1][y]=0
        DFS(x-1,y)


arr=[list(map(int,input().split())) for _ in range(10)]
dx=[-1,0,1,0]
dy=[0,1,0,-1]

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

전형적인 DFS문제이다.

우선 도착 지점은 단 하나로 고정되어 있으니 도착 지점의 좌표를 구한뒤 DFS탐색을 진행한다.

양옆에 1이 있으면 양옆 방향으로 탐색하고 없으면 위로 한칸 이동한뒤 탐색한다.

 

import sys
sys.stdin=open("input.txt", "r")
def DFS(x, y):
    ch[x][y]=1
    if x==0:
        print(y)
    else:
        if y-1>=0 and board[x][y-1]==1 and ch[x][y-1]==0:
            DFS(x, y-1)
        elif y+1<10 and board[x][y+1]==1 and ch[x][y+1]==0:
            DFS(x, y+1)
        else:
            DFS(x-1, y)


board=[list(map(int, input().split())) for _ in range(10)]
ch=[[0]*10 for _ in range(10)]
for y in range(10):
    if board[9][y]==2:
        DFS(9, y)

정답 코드는 풀이의 편이를 위해 체크 리스트를 사용한 점 이외엔 모두 같다 ~