파이썬 알고리즘/DFS, BFS 활용

11. 등산경로(DFS)

문제-생략 문제풀이 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

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

9.미로의 최단거리 통로(BFS)

미로의 최단거리 통로(BFS) -문제는 생략 문제풀이 import sys from collections import deque sys.stdin=open("input.txt", "r") dx=[-1, 0, 1, 0] dy=[0, 1, 0, -1] board=[list(map(int, input().split())) for _ in range(7)] board[0][0] =1 #이미 방문 dis=[[0]*7 for _ in range(7)] dis[0][0] = 0 #0으로 세팅한다. Q=deque() Q.append((0,0)) while Q: tmp=Q.popleft() #tmp에는 튜플 1개만 저장된다 tmp는 현재시점에서의 부모를 의미한다. for i in range(4): x=tmp[0]+dx[i..

8. 사과나무(BFS) -섹션3 봉우리 참고

문제 - 생략 문제풀이 import sys from collections import deque sys.stdin=open("input.txt", "r") dx=[-1, 0, 1, 0] dy=[0, 1, 0, -1] n=int(input()) a=[list(map(int, input().split())) for _ in range(n)] ch=[[0]*n for _ in range(n)] #발자국 좌표를 만든다. sum=0 Q=deque() ch[n//2][n//2]=1 #최초 발자국을 표시한다. sum+=a[n//2][n//2] Q.append((n//2, n//2)) L=0 #L은 최상위 노드의 부모이면서 step의 출발점 이므로 0으로 세팅한다. while True: if L==n//2: break..