나의 개발일지

문제 : https://www.acmicpc.net/problem/12919 dfs 🔑 마지막이 A일 때, 처음이 B일 때 t[-1]이 "A"일 때 마지막 "A"빼고 재귀 호출 t[0]이 "B"일 때 뒤집은 후 마지막 "B"빼고 재귀 호출 각각 if 조건으로 두 가지 분기로 나눈다. s = input() t = input() def dfs(t): if len(s) == len(t): if s == t: print(1) exit() else: return 0 if t[-1] == "A": dfs(t[:-1]) if t[0] == "B": dfs(t[::-1][:-1]) dfs(t) print(0)

문제 : https://www.acmicpc.net/problem/1068 DFS 부모 노드를 지우면 자식 노드로 갈 길이 없어지기 때문에 제거해야 할 노드만 지우면 자식 노드들을 다 지울 필요 없다. import sys from collections import defaultdict input = sys.stdin.readline tree = defaultdict(list) n = int(input()) nodes = list(map(int, input().split())) remove_node = int(input()) for i in range(n): if i != remove_node: # 제거해야 할 노드 제외하고 추가 tree[nodes[i]].append(i) if remove_node in..

문제 : https://www.acmicpc.net/problem/11724 DFS 파이썬으로 풀이 할 경우 재귀 깊이 한계가 정해져 있어 새롭게 지정 필요 sys.setrecursionlimit(10**9) from collections import defaultdict import sys sys.setrecursionlimit(10**9) # 재귀 깊이 한계 지정 input = sys.stdin.readline n, m = map(int, input().split()) # 정점, 간선 graph = defaultdict(list) for i in range(m): u, v = map(int, input().split()) graph[u].append(v) graph[v].append(u) visit ..

문제 : https://www.acmicpc.net/problem/26169 dfs, 백트레킹 Map = [list(map(int, input().split())) for _ in range(5)] r, c = map(int, input().split()) # 행, 열 visit = [[0] * 5 for _ in range(5)] visit[r][c] = 1 mx, my = [1, -1, 0, 0], [0, 0, 1, -1] def dfs(r, c, d, apple): # 행, 열, 깊이, 사과 갯수 if d > 3: # 4번 이동하면 돌아가 return if apple >= 2: # 사과 2개 먹었으면 나가 print(1) exit() for i in range(4): # 상하좌우 네 방향 탐색 nx..

문제 : https://www.acmicpc.net/problem/1260 from collections import defaultdict n, m, v = map(int, input().split()) graph = defaultdict(list) for i in range(m): # 양방향 그래프 구현 x, y = map(int, input().split()) graph[x].append(y) graph[y].append(x) def dfs(n): print(n, end=" ") visit[n] = 1 graph[n].sort() # 숫자가 작은 노드부터 방문하기 위해 정렬 for i in graph[n]: if visit[i] == 0: dfs(i) def bfs(n): q = [graph[n]] ..

문제 : https://school.programmers.co.kr/learn/courses/15008/lessons/121684 dfs, 재귀 각 종목 별로 대표를 뽑고 능력치 합을 계산해 최댓값을 찾는다. answer = 0 def dfs(d, sum, ability, ck): global answer n = len(ability) # 학생 수 m = len(ability[0]) # 종목 수 if d == m: # 깊이가 최대 종목 수에 도달하면 answer = max(answer, sum) # 더 큰 능력치 합으로 업데이트 return else: # 아니면 for i in range(n): # 학생 수 만큼 반복 if ck[i] == 0: # 종목 대표로 안 나간 학생이면 ck[i] = 1 # 대표..

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/92343 2022 KAKAO BLIND RECRUITMENT 카카오 해설 사이트 : https://tech.kakao.com/2022/01/14/2022-kakao-recruitment-round-1/ 🔑 : DFS def solution(info, edges): answer = [] visit = [0] * len(info) visit[0] = 1 def dfs(sheep, wolf): if sheep > wolf: answer.append(sheep) else: return for p, c in edges: if visit[p] and not visit[c]: # 부모 노드는 방문했고 자..

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/43164 스택을 활용한 DFS를 사용 def solution(tickets): answer = [] graph = {i[0] : [] for i in tickets} for i in tickets: graph[i[0]].append(i[1]) for i in graph: graph[i] = sorted(graph[i], reverse=True) stack = ["ICN"] # 출발 위치 while stack: top = stack[-1] # 스택의 가장 위 요소(출발지) if top not in graph or not graph[top] : # 출발지가 없거나, 도착할 곳이 없으면 answe..