Marryakirise's coding

문제 Point ✨ bfs 문제에서 상하좌우로 노드를 탐색하고, 최단경로를 찾는문제인데, 이 문제의 포인트는 "1일 때만 이동할 수 있기 때문에 중심이 되는 노드에서 상하좌우로 탐색한 노드가 1이면, 중심이 되는 노드의 최소 칸 수에 1을 더한 값으로 그 탐색한 노드의 값을 바꾼다." 이다. import sys from collections import deque # 최단 경로를 찾는 문제 def bfs(start, end): queue = deque([(start,end)]) visited = [[0] * m for _ in range(n)] visited[start][end] = 1 dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] cnt = 0 while queue: x, y = ..

문제 설계 ✨ 처음 수빈이의 위치 N 에서 동생의 위치 K로 가는 최단 시간을 찾는 것이다. 최단 시간을 찾는 것이기에 DFS, BFS를 먼저 생각할 수 있다. 기존 위치에서 이동하는 위치는 3가지 X - 1, X + 1, 2 x X 로 총 3가지가 있다. 즉 노드가 3개로 펼쳐져 나갈 수 있다. 하나의 노드가 얼마나 깊이까지 가는지 모두 확인해서 최단시간을 찾으려면 모든 경로를 다 탐색해야하므로 비효율적이다. 즉 DFS 보다는 BFS 임을 생각한다. BFS로 문제를 풀기로 했으니, 기존 BFS 코드를 작성한다. 다음 노드로 펼쳐져 가는 것이 3가지가 있으니 Queue에 append할 아이템이 3가지이다. X - 1, X + 1, 2 x X 값이 범위를 넘어가지 않도록 조건문을 사용해준다. 방문 위치를 ..

문제 설계 ✨ +, - 를 그래프에 넣어야하나 하면서 트리를 구성해봤는데 불필요하게 노드를 많이 추가해야하기 때문에 다른 방법을 생각해보았다. 그렇다면, 값을 누적시키는 방법은 어떨까? 하고 고민하게 되었고, 현재 원소에서 다음 원소를 더한 값을 왼쪽 노드에 넣고, 현재 원소에서 다음 원소를 뺀 값을 오른쪽 노드에 넣는 방식을 떠올리게 되었다. 즉. 트리에서 작대기가 +, - 역할을 하도록 트리를 구성한 것이다. 예제 2번을 설명한 대로 트리로 구현해본 것이다. 루트 노드는 0으로 설정했다. 코드는 해당 값에 다음 값을 더한 값을 큐에 추가하고, 해당 값에 다음 값을 뺀 값을 큐에 추가해서 값을 누적시켜 leaf 노드까지 왔을 때 target값과 일치하는지 확인하는 방식으로 설계했다. 다시 한번 정리하자..