bit가 눈 앞에서 왔다갔다

https://programmers.co.kr/learn/courses/30/lessons/1844 코딩테스트 연습 - 게임 맵 최단거리 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1 programmers.co.kr 카페 영업시간 다 돼서 쫓겨나는 중이라 내일 이어서)) 0. 입출력 1. 김예고리즘 1-1. 알고리즘 1) 최단 경로를 검색한다고 하기에 bfs라고 생각함 2) 1을 만나게 되면 큐에 넣어줌 3) 끝까지 간 다음에 결과를 저장하고, 큐에 들어있는 경로로 그 시점부터 다시 탐색, 결과 저장을 반복 1-2. 코드..

https://programmers.co.kr/learn/courses/30/lessons/67259 코딩테스트 연습 - 경주로 건설 [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[ programmers.co.kr 1. 내 접근 가능한 모든 경우의 수를 전부 체크해야겠다고 생각했다. 완전 탐색에도 이..

DFS : 현재 정점에서 갈 수 있는 점들까지 (끝까지) - 모든 노드를 방문해야할 때 - 경로에 특징을 저장해둬야 하는 문제 - 검색 대상 그래프가 클 경우 - (BFS보다 간단하지만 느림) BFS : 현재 정점에서 연결된 가까운 점들부터 - 재귀적으로 동작하지 않음 - 최단거리, 임의의 경로 문제 - 규모가 작고 원하는 대상이 멀지 않을때 - 큐 사용, FIFO 원칙 둘 다 - 어떤 노드를 방문했는지 여부 검사 반드시! (or 무한루프,,)

https://programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr from collections import deque def solution(n, edge): answer = 0 graph = [[] for _ in range(n+1)] visited = [-1]*(n+1) # 방문 확인 # edge에서 a, b를 뽑아내서 그래프 생성 for a, b in edge: graph[a].append(b) graph[b].append(a) # 방문 예정 노드 설정, 방문 처리 deq = deque([..

DFS(Depth First Search) 깊이 우선 탐색: 시작 노드를 방문처리 하고 방문처리 되지 않은 노드로 진행 선택된 노드는 방문처리 되고 새로운 시작 노드가 되어 같은 방법을 반복하다가 방문처리 되지 않은 노드가 없을 경우 되돌아 감 BFS(Breadth First Search) 너비 우선 탐색: 시작 노드로부터 가까운 노드를 먼저 방문하고 멀리 떨어져 있는 노드를 나중에 방문. 시작 노드에서 인접한 노드들을 방문하고 그 노드들과 인접한 노드들을 방문 DFS-구현 가능한 방법 또는 활용하는 자료구조: 1. 순환호출(재귀함수) 2. 스택(Stack)- 순환호출 이용 def dfs(graph, v, visited): visited[v] =True print(v, end=' ') for i in g..