문제- 생략
문제풀이
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) #위쪽
if __name__=="__main__":
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)
▶ main 함수에서 2가 나올 때까지 열(column)을 탐색한다.
▶ 2가 나온 열(column)을 찾으면 바로 함수를 호출한다. 그리고 그 찾은 spot은 이미 방문한 곳이므로
▶ ch[x][y]=1로 만들어서 방문한 흔적을 표시한다.
▶ if y-1>=0 and board[x][y-1]==1 and ch[x][y-1]==0:
▶ ↑ 내가 왼쪽 next지점(y-1)으로 이동하려하는데, y-1좌표는 0보다 커야 하며,
▶ board[x][y-1]==1로써 방문 가능한 곳이머야 하며,
▶ ch[x][y-1]==0: 로써 방문한 흔적이 없어야 한다.
'파이썬 알고리즘 > DFS, BFS 활용' 카테고리의 다른 글
18. 병합정렬 (0) | 2022.11.22 |
---|---|
17. 피자배달거리(DFS) (0) | 2022.11.22 |
15.토마토(BFS 활용) (0) | 2022.11.11 |
14. 안전영역(BFS) vs 안전영역(DFS) (0) | 2022.11.11 |
13.섬나라 아일랜드(BFS 활용) (0) | 2022.11.11 |