나의 개발일지

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/84512 🔑 DFS로 완전 탐색 A ~ UUUUU까지 만들 수 있는 dfs 함수를 생성 원하는 단어를 찾을 때까지 answer 올리고 찾았으면 계속 리턴만해서 빠져나오기 def dfs(w, word, words): global answer, flag if word == w: flag = True return if len(w) != 5: for i in range(len(words)): if flag: return answer += 1 dfs(w+words[i], word, words) answer = 0 flag = False def solution(word): words = ['A', 'E..

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/42892 🔑 DFS) 왼쪽 트리, 오른쪽 트리를 나누자 사전 작업 : 노드 번호가 없기 때문에 노드 번호를 추가, y값 기준 내림차순 정렬 순회 함수 진입 부모 노드의 x 값 보다 자식 노드의 x 값이 작으면 left 리스트에 추가 반대면 right 리스트에 추가해서 왼쪽, 오른쪽 트리를 구분 전위는 재귀 들어가기 전에 부모 노드의 번호를 저장 후위는 재귀 나오고 나서 부모 노드의 번호를 저장 left 리스트에 노드가 있으면 left 리스트를 가지고 재귀 진행 가지고간 left 리스트에 대해서도 left, right 리스트로 나눈다 left 리스트에 노드가 없으면 right 리스트로 재귀 진..

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/86971 🔑 완전 탐색, DFS 전선 연결 지점 한 곳을 끊고 탐색 (끊긴 곳이면 가지 않음) 이를 위해 양방향 그래프로 표현하고 해당하는 지점이면 continue | 방문 한 곳 - 안 한 곳 | 이 가장 적은 값으로 정답을 계속 업데이트해 주면 끝 ✨ from collections import defaultdict def solution(n, wires): answer = 1000 graph = defaultdict(list) for i in wires: # 양방향 그래프 graph[i[0]].append(i[1]) graph[i[1]].append(i[0]) def dfs(node, r..

문제 : https://www.acmicpc.net/problem/24479 🔑 visit 리스트에 방문했으면 1 대신 방문 순서를 저장 시작 노드가 가장 첫 방문 순서이기 때문에 1로 설정하고 cnt 변숫값을 2부터 시작 import sys input = sys.stdin.readline sys.setrecursionlimit(1000000) n, m, r = map(int, input().split()) graph = {i : [] for i in range(1, n+1)} for i in range(m): p, c = map(int, input().split()) graph[p].append(c) graph[c].append(p) for i in graph: graph[i].sort() visit ..

문제 : https://www.acmicpc.net/problem/11725 🔑 DFS 양방향 그래프로 트리를 표현 1번 노드부터 출발 자식 노드에 도착하면 자식 노드 인덱스에 부모 노드 번호 저장 (answer 리스트) DFS 끝나면 answer [2]부터 출력 from collections import defaultdict import sys input = sys.stdin.readline sys.setrecursionlimit(1000000) n = int(input()) tree = defaultdict(list) for i in range(n-1): p, c = map(int, input().split()) tree[p].append(c) tree[c].append(p) answer = [0] ..

문제 : https://www.acmicpc.net/problem/6443 🔑 DFS, 백트래킹 딕셔너리에 알파벳 개수를 저장한다 ex) {a : 2, b : 1, c: 1} 알파벳이 있으면(값이 0이 아니면)문자열에 추가, 딕셔너리에서 값을 내리고 다음 재귀로 간다. 1. a 2. aa 3. aab 4. aabc 알파벳 다 썼으니까 출력하고 리턴 후 사용했던 알파벳 개수 다시 증가 (다른 순서로 다시 사용해봐야 함) 2. aa 3. aac 4. aacb 반복 .... n = int(input()) def dfs(dict_s, l, s): if l == len(s): print(s) return for i in dict_s: if dict_s[i]: dict_s[i] -= 1 dfs(dict_s, l, ..

문제 : https://www.acmicpc.net/problem/2251 🔑 물통의 이동 경우의 수 6가지 C → A C → B B → A B → C A → B A → C one, two, three = map(int, input().split()) answer = [] m = max(one, two, three) chk = [[[0] * (m+1) for _ in range(m+1)] for _ in range(m+1)] def dfs(a, b, c): if chk[a][b][c] == 1: return if a == 0: answer.append(c) chk[a][b][c] = 1 if c > (one - a): # C -> A dfs(one, b, c - (one - a)) else: dfs(a ..

문제 : https://www.acmicpc.net/problem/26170 🔑 DFS, 백트래킹 사과가 있는 위치면 사과 개수를 더해서 다음 칸으로 이동 사과가 없는 위치면 그냥 이동 사과 세 개를 먹으면 짧은 거리로 업데이트 세 개를 못 먹는 경우 -1 출력 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 = [0, 0, 1, -1], [1, -1, 0, 0] answer = 100 def dfs(r, c, d, apple): global answer if apple == 3: ans..