.PNG)
70. 사다리 타기(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
<내 풀이>
여러가지의 수가 나와서(7 외에도 1,2,5,9) 뭐지..?했는데 사다리의 속성을 고려하지 않으면 7 외에도 2가 있는 지점을 향해 갈 수는 있다. 그렇다면 사다리의 속성을 고려해줘야 하는데 어떻게 고려할 수 있는 것일까?
(1) 여러가지 수가 나와서 실패
def dfs(x,y):
if x==0:
print(y)
else :
for i in range(4):
xx=x+dx[i]
yy=y+dy[i]
if 0<=xx<10 and 0<=yy<10 and a[xx][yy]==1 and ch[xx][yy]==0:
ch[xx][yy]=1
if xx==0:
dfs(xx,yy)
if __name__=='__main__' :
dx=[1,0,-1,0]
dy=[0,-1,0,1]
a=[list(map(int, input().split())) for _ in range(10)]
ch=[[0]*10 for _ in range(10)]
for i in range(10) :
for j in range(10) :
if a[i][j]==2:
dfs(i,j)
(2) - 왼쪽과 오른쪽을 우선 탐색하고, 없으면 그때서야 위를 탐색 (아래는 탐색할 필요 없음) 이라는 속성을 염두에 두고 짜봄, 그러나 여전히 7외에도 5랑 9도 출력된다
==>왼쪽과 오른쪽, 위쪽 탐색할 거였으면
dx=
dy=
==>행이랑 열을 잘 구분하자
def dfs(x,y):
if x==0:
print(y)
else :
for i in range(2):
xx=x+dx[i]
yy=y+dy[i]
if 0<=xx<10 and 0<=yy<10 and a[xx][yy]==1 and ch[xx][yy]==0:
ch[xx][yy]=1
dfs(xx,yy)
else :
xx=x+dx[2]
yy=y+dy[2]
if 0<=xx<10 and 0<=yy<10 and a[xx][yy]==1 and ch[xx][yy]==0:
ch[xx][yy]=1
dfs(xx,yy)
if __name__=='__main__' :
dx=[1,-1,0]
dy=[0,0,1]
a=[list(map(int, input().split())) for _ in range(10)]
ch=[[0]*10 for _ in range(10)]
for i in range(10) :
for j in range(10) :
if a[i][j]==2:
dfs(i,j)
(3) dx, dy 범위 수정후
=> 그럼에도 문제 있던 게 왼쪽-오른쪽-위쪽 살필 때 가장 먼저 발견하는 것 있으면 그거 선택해서 dfs호출하고 빠져나가야 하는데 나는
for i in range(2) 라고 해서 왼쪽에서 찾았어도 오른쪽도 보고, 둘다 있으면 둘다 dfs호출하는 방식으로 선택해서 틀린 풀이였음
<풀이>
- 왼쪽과 오른쪽을 우선 탐색하고, 없으면 그때서야 위를 탐색 (아래는 탐색할 필요 없음) => dx,dy 안 쓰시고 직접 좌우를 보고 위를 보심
def dfs(x,y):
if x==0:
print(y)
else :
if y-1>=0 and a[x][y-1]==1 and ch[x][y-1]==0:
ch[x][y-1]=1
dfs(x,y-1)
elif y+1<10 and a[x][y+1]==1 and ch[x][y+1]==0:
ch[x][y+1]=1
dfs(x,y+1)
else :
ch[x-1][y]=1
dfs(x-1,y)
if __name__=='__main__' :
a=[list(map(int, input().split())) for _ in range(10)]
ch=[[0]*10 for _ in range(10)]
for i in range(10) :
for j in range(10) :
if a[i][j]==2:
ch[i][j]=0
dfs(i,j)
<반성점>
- 아래와 같이 일일이 ch=1으로 변경해주는 것보다
def dfs(x,y):
if x==0:
print(y)
else :
if y-1>=0 and a[x][y-1]==1 and ch[x][y-1]==0:
ch[x][y-1]=1
dfs(x,y-1)
elif y+1<10 and a[x][y+1]==1 and ch[x][y+1]==0:
ch[x][y+1]=1
dfs(x,y+1)
else :
ch[x-1][y]=1
dfs(x-1,y)
- 이렇게 dfs가 호출될 때마다 ch=1로 해주는 게 훨씬 효율적!
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)
- 행이랑 열을 구분하지 않고 내 직감대로 하다가 자꾸 틀린다
행이랑 열을 잘 구분하자
a[i][j] 에서 i는 행, j는 열
j[0] j[1]..j[5]
000000
i[0]
000000
i[1]
000000
i[2]
- 왼쪽-오른쪽-위쪽 살필 때 가장 먼저 발견하는 것 있으면 그거 선택해서 dfs호출하고 빠져나가야 하는데 나는
for i in range(2) 라고 해서 왼쪽에서 찾았어도 오른쪽도 보고, 둘다 있으면 둘다 dfs호출하는 방식으로 선택해서 틀린 풀이였음
<배운 점>
- 사다리 타기의 속성 = 왼쪽 탐색 - 오른쪽 탐색 - 위쪽 탐색 순으로 진행
- 이때 동시다발적으로 하는 게 아니라 if,elif,elif로 처리해주기
<2차 내 풀이>
(1) => 실패, 왜냐면
- 사다리타기에선 한번 간 곳은 다시는 가면 안되는데 (최단 거리랑 동일한 맥락) 나는 ch를 만들어두지 않아서 recursion error 걸림
- 두번째로 y>1 이 아니고 0까지도 가능하니깐 y>=1 임
def dfs(x,y):
if x==0:
return y
else :
if 0<=y<9 and a[x][y+1]==1:
dfs(x,y+1)
elif y>1 and a[x][y-1]==1:
dfs(x,y-1)
elif x>1 and a[x-1][y]==1:
dfs(x-1,y)
if __name__=='__main__' :
a=[list(map(int,input().split())) for _ in range(10)]
for i in range(10) :
for j in range(10) :
if a[i][j]==2:
dfs(i,j)
=>
(2) 수정 후 내 풀이
def dfs(x,y):
if x==0:
print(y)
else :
if 0<=y<9 and a[x][y+1]==1 and ch[x][y+1]==0:
ch[x][y+1]=1
dfs(x,y+1)
elif y>=1 and a[x][y-1]==1 and ch[x][y-1]==0:
ch[x][y-1]=1
dfs(x,y-1)
elif x>=1 and a[x-1][y]==1 and ch[x-1][y]==0:
ch[x-1][y]=1
dfs(x-1,y)
if __name__=='__main__' :
a=[list(map(int,input().split())) for _ in range(10)]
ch=[[0]*10 for _ in range(10)]
for i in range(10) :
for j in range(10) :
if a[i][j]==2:
dfs(i,j)