set2 [python]1012_유기농 배추 사용한 자료구조 및 개념 : bfs, dictionary, set 💡 문제풀이 아이디어 및 어려웠던 점 💫 아이디어 1️⃣ 2차원 배열판을 만들 필요없이 배추 위치 입력값들로 바로 확인한다! 2️⃣ 배추 좌표를 키로하고 인덱스를 값으로 저장하는 딕셔너리를 만든다. ⇒ 지금 현재 배추 위치에서 상,하,좌,우에 해당 하는 값들의 인덱스를 빠르게 조회를 하기 위함이다. ✅ 딕셔너리는 해시 테이블을 기반으로 하므로 키를 사용한 값의 조회가 평균 O(1)의 시간 복잡도로 매우 빠르다. 이를 활용하면 특정 (x, y) 좌표가 존재하는지와 그에 해당하는 인덱스를 매우 빠르게 찾을 수 있다. 3️⃣ 배추 딕셔너리의 모든 키(배추 좌표)들을 가지고와 set으로 만든다. ⇒ 지금 현재 배추 위치에서 상,하,좌,우에 해당 .. 2023. 10. 8. [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 다음