백준 10451 순열 사이클 (파이썬)
2022. 9. 25. 13:19
백준
풀이 및 해설(주석) import collections; import sys sys.setrecursionlimit(10**6) for tc in range(int(input())): N = int(input()) nums = list(map(int, input().split())) graph = collections.defaultdict(list) # graph에 간선의 정보를 넣어줌 for i in range(1, N+1): graph[i].append(nums[i-1]) # traced 는 현재의 진행 상황, 간선을 타고 가다 traced안에 있으면 result를 1증가 traced = set() # visit은 중복처리 방지용, 후위 순회로 정점을 순회한 뒤 return할 때 증가 visited ..
백준 1182 부분수열의 합 (파이썬)
2022. 9. 24. 22:57
백준
아이디어 재귀를 이용해 모든 부분 수열을 만들고 S가 되는 집합을 찾자 풀이 및 해설(주석) N, S = map(int, input().split()) arr = list(map(int, input().split())) result = [] # dfs를 사용하여 모든 부분 수열을 만들어서 result에 저장 def dfs(index, path): global result result.append(path) for i in range(index, N): dfs(i+1, path+[arr[i]]) dfs(0, []) ans = 0 for i in range(len(result)): # 부분 수열이 []으로 빈 리스트도 포함되어서 sum([])은 0이 되어버림 그래서 조건 추가 if len(result[i])..
리트코드 207 Course Schedule (파이썬)
2022. 9. 24. 22:24
리트코드
풀이 import collections class Solution(object): def canFinish(self, numCourses, prerequisites): graph = collections.defaultdict(list) for x, y in prerequisites: graph[x].append(y) traced = set() visited = set() def dfs(i): # 순환 구조이면 False if i in traced: return False # 이미 방문했던 노드이면 True if i in visited: return True traced.add(i) for y in graph[i]: if not dfs(y): return False traced.remove(i) visit..
리트코드 332 Reconstruct Itinerary (파이썬)
2022. 9. 24. 21:57
리트코드
풀이 import collections class Solution(object): def findItinerary(self, tickets): """ :type tickets: List[List[str]] :rtype: List[str] """ graph = collections.defaultdict(list) for a, b in sorted(tickets, reverse=True): graph[a].append(b) route = [] def dfs(a): while graph[a]: dfs(graph[a].pop()) route.append(a) dfs('JFK') return route[::-1]
SWEA 2105 디저트 카페 (파이썬)
2022. 9. 24. 20:11
SWEA
풀이 import sys; sys.stdin = open('input_디저트카페.txt', 'r') dr = [1, 1, -1, -1] dc = [1, -1, -1, 1] def lets_go(answer, r, c, start, way): global result if (r, c) == start: result = max(result, answer) return if r = N or c >= N: return if visited[desert[r][c]]: return else: visited[desert[r][c]] = 1 lets_go(answer + 1, r + dr[way], c + dc[way], start, way) if way + 1 < 4: lets_go(..
백준 1759 암호 만들기
2022. 9. 24. 20:08
백준
풀이 ahdma = 'aeiou' def solve(depth): if depth == K: # 모음, 자음 숫자 확인 a, b = 0, 0 for _ in range(K): if ans[_] in ahdma: a += 1 else: b += 1 # 모음과 자음 개수가 안맞다면 return if not (a >=1 and b >= 2): return print(''.join(ans)) return for i in range(N): if visited[i]: continue # ans에 값이 담겨 있고, ans의 마지막 원소의 아스키 코드값이 현재 넣을 요소의 아스키 코드 값보다 크면 다시 돌아가 if len(ans) > 0: if ord(ans[-1]) > ord(code[i]): continue ans..
백준 2146 다리 만들기 (파이썬)
2022. 9. 24. 19:05
백준
풀이 import sys; from collections import deque; # sys.stdin = open('다리.txt', 'r') sys.setrecursionlimit(10**6) def bfs(r, c): my_color = map[r][c] Q = deque() Q.append((r, c)) visit2[r][c] = 1 while Q: r, c = Q.popleft() for di, dj in [[1, 0], [0, 1], [-1, 0], [0, -1]]: nr, nc = r + di, c + dj if 0
리트코드 733 Flood Fill
2022. 9. 24. 15:02
리트코드
https://leetcode.com/problems/flood-fill/ Flood Fill - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 2차원 배열이 주어지고, 시작점의 좌표와 바꿀 color를 입력받는다. 시작점에서 이어지는 같은 숫자들을 바꾸면 된다. 풀이 class Solution(object): def floodFill(self, image, sr, sc, color): N = len(image) M = len(image[0]) visit ..