문제-생략
문제풀이
import sys
sys.stdin=open("input.txt", "r")
dx=[-1, 0, 1, 0]
dy=[0, 1, 0, -1]
def DFS(x, y):
global cnt
if x==ex and y==ey:
cnt+=1
else:
for k in range(4): #range의 범위만큼 자식이 생긴다.
xx=x+dx[k]
yy=y+dy[k]
if 0<=xx<n and 0<=yy<n and ch[xx][yy]==0 and board[xx][yy]>board[x][y]:
ch[xx][yy]=1 #방문하려는 곳은 흔적을 만들어 놓는다.
DFS(xx, yy) #재귀함수는 루트노드가 된다.
ch[xx][yy]=0 #back하는 경우에는 방문한 흔적을 지운다.
if __name__=="__main__":
n=int(input())
board=[[0]*n for _ in range(n)]
ch=[[0]*n for _ in range(n)]
max=-2147000000
min=2147000000
for i in range(n):
tmp=list(map(int, input().split()))
for j in range(n):
if tmp[j]<min:
min=tmp[j]
sx=i
sy=j
if tmp[j]>max:
max=tmp[j]
ex=i
ey=j
board[i][j]=tmp[j]
ch[sx][sy]=1
cnt=0
DFS(sx, sy)
print(cnt)
해설
▶board[i][j] = tmp[j] 의미
윗쪽에 두개의 if문이 없다고 생각해보자
그러면 board[i][j] = tmp[j]
i 가 특정행 일때 j가 0~n-1열 까지 움직이면서 tmp의 j열에 해당하는 값을 board[i][j]에 대입한다.
그런데 i도 계속 0~n-1행까지 움직이므로
최종적으로는 board에는 n행 n열의 2차원 배열이 만들어진다.
▶다만, board에서 특정좌표에서의 "최소값"과 "최대값"을 찾기 위해
즉 출발지와 도착지를 찾기 위해서 2개의 if문이 윗줄에서 작동하고 있는 것이다.
▶재귀함수는 루트노드가 된다.
▶if 0<=xx<n and 0<=yy<n and ch[xx][yy]==0 and board[xx][yy]>board[x][y]:
→해석 : board[x][y]는 부모노드를 의미하며, board[xx][yy]는 next(자식)노드를 의미한다.
즉 next노드는 부모노드보다 항상 커야 하며, 경계선 밖으로 나가지 않기 위해
xx와 yy의 좌표는 항상 0보다 크거나 같아야하고, n보다 작아야 한다.
그리고 xx,yy좌표는 이전에 방문한 적이 없어야 한다. 따라서 ch[xx][yy]가 0이어야 한다.
▶DFS(xx, yy)
ch[xx][yy] ==0
→해석 : 재귀함수는 forward와 back을 반복하므로 back을 하는 경우에는 방문한 흔적을 없애주어야 한다.
따라서 재귀함수 밑에 ch[xx][yy] == 0 으로 한다.
'파이썬 알고리즘 > DFS, BFS 활용' 카테고리의 다른 글
13.섬나라 아일랜드(BFS 활용) (0) | 2022.11.11 |
---|---|
12.단지 번호 붙이기(DFS) (0) | 2022.11.11 |
10.미로탐색(DFS) - 섹션6의 순열구하기 문제참고 (0) | 2022.11.11 |
9.미로의 최단거리 통로(BFS) (1) | 2022.11.11 |
8. 사과나무(BFS) -섹션3 봉우리 참고 (0) | 2022.11.10 |