No. 1697
1. Problem
2. My Solution
- BFS 알고리즘을 이용해 문제 해결
- 답이 확실히 정해진 경우 나머지 bfs 연산은 불필요하므로 사전에 판단
- bfs 의 depth 를 저장하고 있기 위해서 queue 에 depth 정보 또한 저장
- bfs 이므로 k 를 만나는 순간이 바로 최소 경로가 됨
import sys
import math
from collections import deque
def bfs(pos):
global res
queue = deque()
queue.append((pos,0))
position[pos] = -1 # 방문 표시
while(queue):
pos, move_cnt = queue.popleft()
position[pos] = -1
move = [-1,1,pos]
if pos == k
res = move_cnt # 현재 res 보다 move_cnt 가 작다면
for dx in move:
next_pos = pos + dx
if 0 <= next_pos <= 100000 and position[next_pos] != -1:
queue.append((next_pos, move_cnt+1))
position[next_pos] = -1
n,k = map(int,sys.stdin.readline().rstrip().split())
position = [False] * (100001)
res = math.inf
if n == k:
print(0)
exit()
elif n+1 == k or n-1 == k or 2*n ==k:
print(1)
exit()
bfs(n)
print(res)No. 2250
1. Problem
2. Others' Solutions
- 중위 순회를 이용하여 문제 해결
- 노드와 자식을 저장하기 위해 dict 자료형 이용
- 하나의 열에는 하나의 노드만 저장되기 때문에 중위순회를 수행하면 행은 깊이를 나타내고 열은 탐색되는 순서를 나타냄
import sys
# 중위 순회 함수
def inorder(node, level):
global order
left,right = graph[node].values()
if left != -1:
inorder(left,level+1)
order += 1
level_distance[level].append(order)
if right != -1:
inorder(right,level+1)
# 너비가 가장 큰 레벨과 너비를 찾는 함수
def find_level_distance():
width = 0
for i in range(1,n+1):
if level_distance[i]:
temp = max(level_distance[i]) - min(level_distance[i]) + 1
if temp > width:
level = i
width = temp
return level, width
n = int(sys.stdin.readline())
graph = {}
parent_check = [False] * n
level_distance = [[] for _ in range(n+1)]
order = 0
for _ in range(n):
node,left,right = map(int,sys.stdin.readline().rstrip().split())
graph[node] = {'l': left, 'r':right}
# 해당 조건문을 적용하지 않으면 parent_check[-2]는 무조건 True
if left != -1:
parent_check[left-1] = True
if right != -1:
parent_check[right-1] = True
# 부모가 없는 노드 = root 노드
root = parent_check.index(False) + 1
inorder(root,1)
print(*find_level_distance())
3. Learned
- dict 에서 value 로 dict 를 저장하면 .values() 를 통해 value만 접근 가능
ex)
graph[node] = {'l': left, 'r':right}
left,right = graph[node].values() -> left, right 값 출력
No. 1167
1. Problem
2. Others' Solutions
- 모든 정점에서 dfs 또는 bfs 수행하여 깊이를 판단 -> 시간초과
- 임의의 노드에서 dfs 를 수행한 뒤 가장 거리가 먼 노드에서 다시 한 번 dfs 수행
- 첫 번째 방법
- pop(0) 함수를 수행하면 O(N) 시간복잡도 -> 7000ms
import sys
sys.setrecursionlimit(10**8)
def dfs(node, distance, visited):
global max_distance
global max_distance_node
visited[node] = True
if max_distance < distance:
max_distance = distance
max_distance_node = node
for u,d in tree[node]:
if visited[u] == False:
dfs(u,distance + d, visited)
n = int(sys.stdin.readline())
tree = [[] for _ in range(n+1)]
visited = [False] * (n+1)
max_distance_node = None
max_distance = 0
for _ in range(1,n+1):
inf = list(map(int,sys.stdin.readline().rstrip().split()))
idx = inf.pop(0)
while len(inf) != 1:
v = inf.pop(0)
d = inf.pop(0)
tree[idx].append((v,d))
dfs(1,0,visited.copy())
dfs(max_distance_node,0,visited.copy())
print(max_distance) - 두 번째 방법
- collections 모듈의 deque 자료형 이용하여 popleft() 수행
- popleft() 함수는 O(1) 시간복잡도 -> 700ms
import sys
from collections import deque
sys.setrecursionlimit(10**8)
def dfs(node, distance, visited):
global max_distance
global max_distance_node
visited[node] = True
if max_distance < distance:
max_distance = distance
max_distance_node = node
for u,d in tree[node]:
if visited[u] == False:
dfs(u,distance + d, visited)
n = int(sys.stdin.readline())
tree = [[] for _ in range(n+1)]
visited = [False] * (n+1)
max_distance_node = None
max_distance = 0
for _ in range(1,n+1):
inf = deque(list(map(int,sys.stdin.readline().rstrip().split())))
idx = inf.popleft()
while len(inf) != 1:
v = inf.popleft()
d = inf.popleft()
tree[idx].append((v,d))
dfs(1,0,visited.copy())
dfs(max_distance_node,0,visited.copy())
print(max_distance)
3. Learned
- 트리에서 임의의 노드를 선택하여 dfs 또는 bfs 를 수행한 뒤 가장 거리가 먼 노드를 구한 다음, 해당 노드에서 다시 dfs 또는 bfs 를 수행하면 트리에서 거리가 가장 먼 노드와 노드 사이의 거리 (트리의 지름)를 구할 수 있음 (참고 블로그)
- 입력이 클 때 O(N) 만큼의 시간이 걸리는 함수는 for 문 안에서 피하는 게 좋음
