Save my data

BFS 문제이다. 부끄럽지만 계속 메모리 초과가 나서 구글링해서 올바른 해답을 찾은 문제이다. 실전에서는 이런 일이 발생하지 않도록 더 실력을 키워야겠다. 우선 문제가 트리 구조를 떠올리면 쉽게 풀 수 있을것이라고 생각은 했다. 어떤 입력 v 가 시작값으로 주어지면, 그 입력 v 에 대해 v - 1, v + 1, v * 2 가 v 의 자식 노드로 생겨나면서 노드의 값이 k 와 일치할 때, 그 노드가 속해있는 레벨을 구하면 되는 문제였다. DFS와 BFS에 대해 얼마 전에도 포스팅 한 적이 있는데, BFS는 트리의 각 레벨에 있는 모든 노드를 queue에 넣고 앞에서부터 pop 하면서 너비 우선으로 탐색하는 방식이다. 여기서 처음에 아이디어를 얻은 것은, queue에 각 층의 마지막 계산값들을 넣고 그 뒤..

기초적인 탐색 문제이다. 이 문제는 BFS와 DFS 모든 방법으로 풀 수 있는 문제인데, 나는 어제 BFS를 활용한 탐색 문제를 풀었으니 오늘 이 문제는 DFS로 풀기로 했다. import sys apart = [] N = int(sys.stdin.readline()) for _ in range(N): apart.append([*map(int, sys.stdin.readline().strip())]) total = 0 cnt = 0 res = [] def dfs(x, y): global cnt if x = N or y = N: return False if apart[x][y] == 0: return False if apart[x][y] == 1: cnt += 1 apa..

BFS 를 이용한 탐색 문제이다. 미로의 탈출 가능한 최단 경로를 찾는 문제인데, 사방 탐색은 여러 가지 구현 문제를 풀었던 경험으로 쉽게 떠올릴 수 있었지만 탐색 후 올바른 경로에 대해 BFS를 적용하려고 하니 난해했다. 코드를 완성시킨 후 다시 리뷰하면서 파악해보니 눈에 좀 익으면서 어느 정도 파악이 되었는데, 정해진 범위 내에서 탐색을 진행하며 현재 보고있는 정점과 인접한 정점 중 이어진 곳 따라 탐색을 진행하면서 자신이 왔던 길이 아닌 앞으로 가야할 길의 좌표, 즉 자기가 왔던 곳을 제외한 인접정점들을 for 문을 통해 순서대로 queue 에 넣고 그 인접정점의 값에는 기존의 1 이라는 값 대신 (인접 정점의 기존 값 + 자기 자신의 값) 을 새로 넣어준다. queue 의 왼쪽에서 하나씩 꺼내며 ..

깊이 우선 탐색과 너비 우선 탐색 기초문제이다. 깊이 우선 탐색 - Depth First Search 트리나 그래프에서 임의의 분기를 마주칠 때 마다 어떤 노드에 어떤 형태의 분기가 있다는 것을 기억만 해 놓고 계속 내려간다. 그러다가 막다른 곳(자식 노드가 없는 노드 == 리프 노드) 을 마주하게 되면 전에 기록해놓았던 분기로 되돌아가서 그 분기부터 다시 파고들어가는 것을 그 그래프의 모든 노드를 방문할 때 까지 계속 반복한다. 말 그대로 깊이를 우선해서 탐색하는 방법이다. 너비 우선 탐색 - Breadth First Search 트리나 그래프에서 임의의 분기를 마주치면 분기 하위의 자식 노드들을 너비 방향으로 방문해간다. 어떤 분기에서 그 분기의 뿌리가 되는 부모 노드의 형제 노드들을 우선적으로 방문..