[ 알고리즘 ]/DFS, BFS

[백준] 2178. 미로 탐색

📌문제 https://www.acmicpc.net/problem/2178 🎖️난이도 ✔️풀이 # 정답 - bfs (visited, queue) from collections import deque n, m = map(int, input().split()) miro = [list(map(int, list(input()))) for _ in range(n)] visited = [[0]*m for _ in range(n)] # ~까지의 이동 횟수(방문한 칸 수) dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] # bfs q = deque() q.append([0, 0]) # 시작 위치 visited[0][0] = 1 # 시작 위치까지의 방문 칸 수 1칸 # 큐가 빌 때까지 반복 while ..

[백준] 1260. DFS와 BFS

📌문제 https://www.acmicpc.net/problem/1260 🎖️난이도 ✔️풀이 # sol1) 인접 행렬 & 재귀(dfs) & 큐(bfs) from collections import deque import sys sys.setrecursionlimit(1000000) # 파이썬 기본 재귀 깊이 제한 늘리기 (런타임 에러 방지) n, m, v = map(int, input().split()) # 정점 개수, 간선 개수, 탐색 시작 노드 graph = [[0] * (n+1) for _ in range(n+1)] # 인접 행렬로 그래프 저장 (0으로 초기화) visited_dfs = [False] * (n+1) # list에서 append 후 in으로 체크하는 것보다 빠름 visited_bfs =..

[프로그래머스] 타겟 넘버

📌문제 https://programmers.co.kr/learn/courses/30/lessons/43165 🎖️난이도 Level 2 ✔️풀이 # sol1 (더 빠름, itertools의 product 사용 => 중복순열) from itertools import product def solution(numbers, target): tuple_list = [(x, -x) for x in numbers] sum_list = list(map(sum, product(*tuple_list))) return sum_list.count(target) # sol2 (dfs => 재귀, 전역변수 이용) cnt = 0 def dfs(numbers, i, tmp_sum, target): global cnt # 전역변수 if..