[ 알고리즘 ]/DFS, BFS

[프로그래머스] 단어 변환

📌문제 https://school.programmers.co.kr/learn/courses/30/lessons/43163 🎖️난이도 Level 3 ✔️풀이 # bfs..? from collections import deque def isPossible(word1, word2): cnt = 0 for a1, a2 in zip(word1, word2): if a1 != a2: cnt += 1 return True if cnt == 1 else False def solution(begin, target, words): cnt = 0 queue = deque([[begin]]) # [["hit"], ["hot"], ["dot", "lot"], ["hot", "dog", "lot", ~~~], []] if tar..

[프로그래머스] 네트워크

📌문제 https://school.programmers.co.kr/learn/courses/30/lessons/43162 🎖️난이도 Level 3 ✔️풀이 # dfs def solution(n, computers): visited = [False] * n stack = [] cnt = 0 for i in range(len(visited)): if visited[i] == False: cnt += 1 stack.append(i) while stack: now = stack.pop() if visited[now] == False: visited[now] = True for i in range(n): if computers[now][i] == 1 and i != now: stack.append(i) retur..

[프로그래머스] 게임 맵 최단거리

📌문제 https://school.programmers.co.kr/learn/courses/30/lessons/1844 🎖️난이도 Level 2 ✔️풀이 from collections import deque def solution(maps): dx = [0, 0, 1, -1] # 동서남북 dy = [1, -1, 0, 0] #visited = [[0]*len(maps[0])]*len(maps) # error!!! (얕은 복사) visited = [[0]*len(maps[0]) for _ in range(len(maps))] # 최단거리 누적 queue = deque([[0, 0]]) visited[0][0] = 1 # bfs while queue: x, y = queue.popleft() for i in ..

[개념 정리] DFS, BFS

[220601][스터디준비] - DFS DFS와 BFS란? wise-soybean-8bd.notion.site

[프로그래머스] 여행경로

📌문제 https://programmers.co.kr/learn/courses/30/lessons/43164 🎖️난이도 Level 3 ✔️풀이 # sol1) dfs(재귀) from collections import defaultdict answer = [] # answer에 경로 누적, answer[-1]을 src로 재귀 graph = defaultdict(list) visited = defaultdict(list) n = 0 def dfs(src, tmp_route): print(tmp_route, dict(visited)) if len(tmp_route) == n+1: # tmp_route가 이제 최종 답! global answer answer = tmp_route return if answer: #..