ULISIA's Developer Life

출처 : 숨바꼭질 문제해석 BFS를 탐색을 통해서 큐에 들어갈 분기를 세가지로 나눈다. 현재좌표+1, 현재좌표-1, 현재좌표*2 다음좌표가 경계체크를 벗어나지 않고 한번도 방문한적이 없다면 이전좌표까지의 방문시간+1을 다음좌표까지의 방문시간에 갱신한다. 현재좌표가 K가 될때까지 걸리는 시간의 최적해를 구한다. 해답코드 #숨바꼭질 from collections import deque n, k = map(int, input().split()) MAX = 10 ** 5 isVisited = [0] * (MAX+1) def bfs(startX): q = deque() q.append(startX) while q: x = q.popleft() if x==k: return isVisited[x] for nx in ..

출처 : 내리막 길 문제해석 입력받은 맵을 (0,0)좌표에서 DFS탐색을 시작한다. 4방탐색을 통해 다음에 이동할 좌표의 인덱스가 경계를 벗어나지 않으면서 현재좌표값보다 높이가 더 낮을때만 dfs 함수를 재귀 호출한다. 최종적으로 (n-1,m-1)좌표에 도달했을때마다 ans값을 1씩 더해준다. 모든 dfs 탐색이 끝난 이후 최종적으로 나온 ans값을 출력한다. 처음엔 여기까지 해서 풀어본 결과 시간초과가 나왔다. (0,0)에서 시작해 dfs로 가능한 곳을 모두 탐색하였기에 너무 많은 경우의 수가 있기때문에 시간초과라는 결과가 나왔다. 따라서 시간초과를 줄이기 위한 핵심은 DFS에 DP 방식을 결합하는 것이다. isVisited 리스트에 -1, 0, n으로 구분하여 각각 미방문,방문한경우,경로완성수로 구분..

출처 : 영역 구하기 문제해석 모눈종이 전체 눈금을 0으로 초기화 한 뒤 사각형을 이루고 있는 부분을 1로 초기화해준다. 모눈종이 전체 눈금 한칸한칸을 탐색하는 기준으로 (0,0)부터 시작해서 흰색(0)을 이루고 있는 부분을 만나면 BFS/DFS 탐색을 시작함과 동시에 영역개수를 증가시킨다. 해당영역내에서 흰칸을 이루고 있는 부분만큼 영역넓이를 구해서 반환해준뒤 해당 넓이를 저장하는 리스트에 추가해준다. 최종적으로 구해진 영역 개수와 영역 넓이 리스트의 값들을 출력한다. 해답코드 import sys from collections import deque input = sys.stdin.readline n, m, k = map(int, input().split()) maps = [[0]*m for _ in ..

출처 : 미로 탐색 문제해석 대표적인 미로 탐색 유형의 쉬운 난이도 문제 미로 문제는 기본적으로 이동방향을 제어할 수 있는 배열이 자주 쓰인다. (2차원 기준 2방,4방,8방 등) y와 x좌표에 대한 변화량을 나타내는 dy,dx를 선언하여 각 방향별 인접배열 값을 탐색할 수 있다. dy = [-1,1,0,0] dx = [0,0,-1,1]주의할 점은 이동조건이 있는 미로탐색 등의 문제에서 항상 경계체크와 이동조건을 잊지 말아야 한다. 다음으로 탐색할 인덱스가 전체 맵 배열의 최소와 최대 인덱스 범위를 벗어나지 않는지, 해당 문제에서는 배열값이 1로 되어 있는곳에서만 이동이 가능하므로 해당 조건 또한 동시에 만족해야 한다. for d in range(4): ny, nx = y+dy[d], x+dx[d] if 0

출처 : 트리 문제해석 제거하고자 하는 입력값을 dfs 함수에 넘겨준다. 넘겨준 입력값을 인덱스로 하는 배열값을 제거한다는 의미로 -2로 변경한다.(-1은 루트 노드이므로) 제거한 인덱스를 부모노드로 가지고 있는 노드를 찾아 제거하기 위해 dfs함수를 재귀 호출한다. 재귀가 종료되고 삭제될 노드들은 전부 -2를 배열값으로 지니고 있다. -2가 아니면서, 다른 노드의 부모노드도 아닌 원소(초기 배열 초기화 단계에서 포함되지 않은)를 찾을 때마다 ans를 1씩 늘린다. 해답코드 #트리 import sys input = sys.stdin.readline n=int(input()) vList = list(map(int,input().split())) delete = int(input()) ans=0 def df..

출처 : 5639번 이진 검색 트리 문제해석 전위 순회 결과 50 30 24 5 28 45 98 52 60 첫 원소가 루트 노드(전위 순회) 왼쪽 서브 트리는 루트 노드보다 작은 원소 오른쪽 서브 트리는 루트 노드보다 큰 원소 전위 순회이므로 루트 노드보다 큰 원소가 나오는 지점이 왼쪽 서브 트리와 오른쪽 서브 트리를 나누는 지점과 같다. 50 /30 24 5 28 45/ 98 52 60 50=루트 노드, 3045=왼쪽 서브트리, 9860= 오른쪽 서브트리 위 결과를 활용하여 후위 순회를 해주면 된다. 해답코드 #이진 검색 트리 import sys sys.setrecursionlimit(10**9) input = sys.stdin.readline pre = [] while True: try: pre.ap..

출처 : 링크텍스트 문제해석 시간 가중치가 0과 1 둘로 나누어진다. 걷기 : x+1, x-1은 1초가 걸리고 순간이동 : 2*x는 0초가 걸린다. 단계가 이루어진다는 점으로 큐를 2개로 나눠 구현하는 방법이나 양방향 큐인 deque를 활용하여 2개를 별도로 만들지 않고, 순간이동할 경우 맨 앞에 추가, 걷기를 할 경우엔 뒤에 추가한다. 해답코드 #숨바꼭질 3 import sys from collections import deque MAX = 100001 isVisited = [False] * MAX time = [-1] * MAX input = sys.stdin.readline n, k = map(int,input().split()) q = deque() q.append(n) isVisited[n] =..

출처 : 링크텍스트 문제해석 버스 비용을 '거리'(dist)라고 생각하면, 최단 경로를 구하는 문제로 환원된다. 즐 최단경로를 구하는 문제이다. 특정 지점으로부터의 최단 거리 계산은 다익스트라 알고리즘으로 구할 수 있다. 해답코드 #최소비용 import sys #우선순위 큐 구현을 위함 import heapq input = sys.stdin.readline # 입력 n = int(input()) #정점 개수 m = int(input()) #간선 개수 graph = [[] for _ in range(n+1)] for _ in range(m): parent, child, gain = map(int, input().split()) graph[parent].append((child,gain)) #도착지, 가중치..

출처:1197번 최소 스패닝 트리 문제해석 최소 신장 트리 (minimum spanning tree) 전체 요소들을 연결할때 사용한다. Kruskal 알고리즘, Prim 알고리즘이 있다. Kruskal 간선들을 정렬 간선이 잇는 두 정점의 root를 찾는다. 다르다면 하나의 root를 바꾸어 연결 시켜준다. Prim 임의의 정점을 선택 해당 정점에서 갈 수 있는 간선을 minheap(최소힙)에 넣는다. 최소값을 뽑아 해당 정점을 방문하지 않았다면 선택한다. Kruskal 알고리즘은 간선들을 정렬해야하기 때문에 간선이 적다면 Kruskal, 많다면 Prim을 선택한다. 비슷한 알고리즘으로 다익스트라 알고리즘이 있다. 다익스트라는 전체 요소를 연결하는 것이 아닌 한 정점에서 다른 정점으로 가는 가장 짧은 방..