전체 글

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..

재귀함수는 루트 노드가 된다.

▶깊이우선탐색(DFS)에서 재귀함수는 루트 노드가 된다!!!(매우 중요) ▶넓이우선탐색(BFS)에서 큐에서 popleft()을 한 노드는 부모노드가 된다.

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..

7. 송아지 찾기(BFS)

송아지 찾기 현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다. 현수의 위치와 송아 지의 위치가 직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다. 현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다. 최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성 하세요. ▣ 입력설명 첫 번째 줄에 현수의 위치 S와 송아지의 위치 E가 주어진다. 직선의 좌표 점은 1부터 10,000 까지이다. ▣ 출력설명 점프의 최소횟수를 구한다. ▣ 입력예제 1 5 14 ▣ 출력예제 1 3 문제풀이 import sys from collections import deque sys...