💡Algorithm31 [python]14940_쉬운 최단거리 사용한 자료구조 및 개념 : bfs 💡 문제풀이 아이디어 및 어려웠던 점 💫 아이디어 1️⃣ 거리를 체크하기 위한 새로운 이차원리스트 distance를 만든다. 2️⃣ 원래 갈 수 없는 곳은 0 그대로 출력해야하고 갈 수 있는 땅(1)이나 목표지점까지 도달할 수 없는 위치는 -1을 출력해야하기 때문에 갈 수 있는 땅은 distance에서 초기값을 -1로 설정한다. 3️⃣ 목표지점에서 출발한다! 4️⃣ 이동 가능한 범위 내에서 갈 수 있는 곳이고, 방문하지 않았던 곳이라면 이동한다. Solution Code & 주석 import sys from collections import deque input = sys.stdin.readline def bfs(x, y): queue = deque([(x, y)]) .. 2023. 9. 14. [python]16918_붐버맨 사용한 자료구조 및 개념 : 이차원리스트 💡 문제풀이 아이디어 및 어려웠던 점 💫 아이디어 1️⃣ 기존 폭탄 위치를 참고하기 위해 폭탄이 터진 결과를 새로운 이차원 배열에 기록한다. 2️⃣ 이후 원래 폭탄 배열을 새로 기록한 폭탄 배열로 바꾼다. 3️⃣ 짝수번째 타임에는 무조건 모든 폭탄이 설치되어 있으니 짝수 번째라면 바로 모든 폭탄이 설치된 배열을 출력한다. 4️⃣ 원하는 시간이 될 때까지 반복한다. ✅ 이 문제는 첫 번째 폭탄이 터진 결과와 그 다음 폭탄이 터진 결과가 반복되는데 반복된다는 것을 활용하여 조건처리를 따로 진행해 연산을 훨씬 줄일 수 있다! Solution Code & 주석 import sys input = sys.stdin.readline def boom(x, y): temp[x][.. 2023. 9. 13. [python]1325_효율적인 해킹 사용한 자료구조 및 개념 : bfs 💡 문제풀이 아이디어 및 어려웠던 점 💫 아이디어 1️⃣ maxCnt 변수를 설정하여 감염시킨 노드와 maxCnt값을 비교하여 최대로 많이 감염시킬 수 있는 노드를 찾는다. 2️⃣ bfs를 사용하는데 감염시킨 노드의 수를 알아야하므로 cnt를 설정하여 해킹했다면 +1을 해주고 비교를 위해 cnt 값을 return한다. 👻 어려웠던 점 🚨 단방향이라는 점을 놓쳤었다…@@ Solution Code & 주석 import sys from collections import deque input = sys.stdin.readline def bfs(v): cnt = 1 infected = [0] * (n + 1) infected[v] = 1 queue = deque([v]) whi.. 2023. 9. 8. [python]11725_트리의 부모 찾기 사용한 자료구조 및 개념 : 재귀, bfs 💡 문제풀이 아이디어 및 어려웠던 점 💫 아이디어 1️⃣ 부모가 누구인지 기록할 리스트 parent를 만든다. 2️⃣ parent의 초기 설정을 0으로 하여 이 값을 활용해 방문한 노드인지 아닌지도 같이 판단한다. 재귀와 deque를 사용한 bfs 버전으로 풀었는데 bfs가 시간과 메모리 측면에서 더 효율적이었다! 👻 어려웠던 점 🚨 런타임 에러(재귀ver) ❓이유 : 재귀 버전으로 풀었을 때 재귀 호출 깊이 제한을 초과하였다. 파이썬에서는 기본적으로 재귀 호출 깊이가 제한되어 있고, 대부분 시스템에서 1000으로 설정해놓았기 때문에 트리의 최대 크기가 100.000일 수 있는 이 문제에서는 깊이 제한을 늘려줘야 했다. ❗해결 : sys.setrecursionl.. 2023. 9. 7. [python]1260_DFS와 BFS 사용한 자료구조 및 개념 : DFS, BFS, deque 💡 문제풀이 아이디어 및 어려웠던 점 💫 아이디어 1️⃣ dfs를 재귀로 구현한다. 2️⃣ bfs를 deque을 사용하여 구현한다. 👻 어려웠던 점 🚨 문제 틀림 ❓이유 : 문제의 요구사항에서 낮은 번호를 우선으로 방문해야 한다는 것을 놓쳤다..! ❗해결 : graph = [sorted(g) for g in graph] 를 추가하였다! Solution Code & 주석 import sys from collections import deque input = sys.stdin.readline def dfs(graph, start, visited): visited[start] = True result = [start] for next_node in gr.. 2023. 9. 7. [python]2060_바이러스 사용한 자료구조 및 개념 : bfs, deque 💡 문제풀이 아이디어 및 어려웠던 점 💫 아이디어 1️⃣ bfs와 deque을 사용한다. 2️⃣ 노드를 queue에 추가하여 노드와 연결된 노드들을 순회한다. 3️⃣ next_v 노드가 감염되지 않았다면 감염시키고 next_v 노드의 연결된 노드들을 확인할 수 있게 queue에 추가한다. 4️⃣ queue가 빌 때까지 반복하여 감염된 컴퓨터 수를 확인한다. Solution Code & 주석 import sys from collections import deque def bfs(v): result = 0 infected[v] = True queue = deque([v]) while queue: v = queue.popleft() for next_v in gr.. 2023. 9. 6. 이전 1 2 3 4 5 6 다음