70.사다리 타기(DFS)
현수와 친구들은 과자를 사먹기 위해 사다리 타기를 합니다. 사다리 표현은 2차원 평면은 0으
로 채워지고, 사다리는 1로 표현합니다. 현수는 특정도착지점으로 도착하기 위해서는 몇 번째
열에서 출발해야 하는지 알고싶습니다. 특정 도착지점은 2로 표기됩니다. 여러분이 도와주세
요. 사다리의 지도가 10*10이면
0 1 2 3 4 5 6 7 8 9
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 0 1 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
특정목적지인 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(v,c):
if v==9:
if lst[c[0]][c[1]]==2:
print(i)
sys.exit(0)
else:
for j in range(3):
x=c[0]+dx[j]
y=c[1]+dy[j]
if 0<=x<10 and 0<=y<10 and lst[x][y]>0 and ch[x][y]==1:
ch[x][y]=0
if dy[j]==0:
print(i, x,y)
dfs(v,(x,y))
else:
print(i, x,y)
dfs(v+1,(x,y))
dx=[0,1,0]
dy=[1,0,-1]
lst=[list(map(int, input().split())) for _ in range(10)]
for i in range(10):
ch=[[1]*10 for _ in range(10)]
if lst[0][i]==0:
continue
else:
dfs(0,(0,i))첫 행에서 시작하여 값이 1인 곳은 dfs로 내려가는 방식을 택했는데, 방향설정을 제대로 못했다. 왼쪽, 오른쪽을 먼저 보고 값이 0이면 내려갔어야 하는데 반복문으로 우,하,좌 순서대로 보니 엉뚱한 곳으로 향했다. 또한 도착점에서 위로 올라가는 방식은 생각도 하지 못했다.
풀이
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)반성점
- 틀 밖에서 생각하는 능력이 결여되어 있다.
배운 것
