BFS - 미로 찾기
이코테 p.152 - 미로찾기 N x M 크기의 미로가 있다. (1,1)에서 (N,M)으로 가기위한 최소 이동 칸 수를 구하라. 괴물(0), 길(1) BFS를 이용하고.. 방문한 노드는 (이전 노드값+1)을 해서 방문표시를 한다. (N,M)위치의 노드 값을 읽으면 최소 발자취 수가 나온다. from collections import deque dx=[1,-1,0,0] dy=[0,0,-1,1] def bfs(x,y): queue = deque() queue.append((x,y))#현재 노드 방문처리 while(queue): x, y= queue.popleft() #큐에서 좌표를 꺼냄 for i in range(4):#상하좌우 네방향 확인 nx=x+dx[i] ny=y+dy[i] if nx=N or ny=M..
2022. 7. 13.
탐색 알고리즘 - DFS
DFS (Depth-First Search, 깊이 우선 탐색) 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. def dfs(graph, v, visited): visited[v] = True print(v,end=' ') for i in graph[v]: if not visited[i]: dfs(graph,i,visited) #각 노드가 연결된 정보를 2차원 리스트로 표현 graph=[ [],#1번 [2,3,8], [1,7,], [1,4,5], [3,5], [3,4], [7], [2,6,8], [1,7] ] #각 노드의 방문이력을 저장할 1차원리스트 visited=[False]*9 dfs(graph,1,visited) def dfs(graph, v, visited): visited[v] = T..
2022. 7. 12.
