10.미로탐색(DFS) - 섹션6의 순열구하기 문제참고

문제 -생략

 

 

문제풀이

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==6 and y == 6:  #if문을 만족하는 여러 case가 나올 것이다.
       cnt+=1
    else:
        for i in range(0, 4): #range의 범위는 트리의 가지(자식) 수를 의미한다. i는 branch의 값을 의미한다.  
          xx=x+dx[i]
          yy=y+dy[i]

          if 0<=xx<=6 and 0<=yy<=6 and board[xx][yy] ==0:  # xx,yy는 next좌표를 의미한다.
                board[xx][yy]=1
                DFS(xx, yy)              #재귀함수가 root노트가 된다. 
                board[xx][yy]=0

if __name__=="__main__":
  board=[list(map(int, input().split())) for _ in range(7)]
  board[0][0] = 1 #최초 시작점에 발자국 남김
  cnt=0
  DFS(0,0)
  print(cnt)

 

Hint

▶ 재귀함수가 root노드가 된다.(가장 중요)

 

▶ xx, yy좌표는 next좌표 즉 나아가고자하는 좌표를 의미한다.

 

▶ 지나온 지점은 board[x][y] =1을 대입해서 발자국을 표시한다.

 

▶ 다만 DFS(깊이우선탐색)은 앞으로 forward and back을 반복하는 구조이므로

     back 할때 board[x][y] =0 을 대입시켜서 방금 앞에 갔었던 흔적을 지운다.

 

▶ x ==6 and y ==6 일때 도착지점에 도착한다. 따라서 도착하는 여러 case를 카운팅한다.