컴공생의 다이어리

백준 16948번 : 데스 나이트 (문제 바로가기) 내 코드 import sys from collections import deque input = sys.stdin.readline n = int(input()) r1, c1, r2, c2 = map(int, input().split()) cnt = 0 arr = [[-1] * n for _ in range(n)] # -1로 초기화 arr[r1][c1] = 0 # 시작 지점을 0으로 세팅 queue = deque([(r1, c1)]) directions = [(-2, -1), (-2, 1), (0, -2), (0, 2), (2, -1), (2, 1)] while queue: # bfs 수행 r, c = queue.popleft() for rr, cc in..

[프로그래머스] 가장 먼 노드 - 파이썬(Python) from collections import deque def bfs(graph, start, n): visited = [0] * (n + 1) visited[start] = 1 queue = deque([start]) while queue: node = queue.popleft() for i in graph[node]: if visited[i] == 0: visited[i] = visited[node] + 1 queue.append(i) return visited.count(max(visited)) def solution(n, vertex): graph = [[] for _ in range((n + 1))] for a, b in vertex: gra..

백준 14502번 : 연구소 (문제 바로가기) 내 코드 import sys from collections import deque from itertools import combinations def bfs_and_count_zero(graph, virus_pos, n, m): # 너비 우선 탐색 & 빈칸 수 구하기 directions = [(1, 0), (-1, 0), (0, 1), (0, -1)] visited = [[False] * m for _ in range(n)] for i, j in virus_pos: visited[i][j] = True queue = deque(virus_pos) while queue: # 바이러스 전파하기! x, y = queue.popleft() for i in rang..

너비 우선 탐색(BFS, Breadth First Search) BFS는 가까운 노드부터 우선적으로 탐색하는 방식이며 레벨(level) 순서대로 접근한다. BFS는 최단 경로를 찾아준다는 점에서 최단 길이를 보장해야 할 때 많이 사용된다. 큐를 활용해서 구현한다. 장점 노드 수가 적고 깊이가 얕은 해가 존재 할 때 유리 너비를 우선으로 탐색하기 때문에 답이 되는 경로가 여러 개인 경우에도 최단 경로임을 보장 최단 경로가 존재한다면, 어느 한 경로가 무한히 깊어진다 해도 최단 경로를 반드시 찾을 수 있음 단순 검색 속도가 DFS보다 빠름 단점 재귀호출을 사용하는 DFS와 달리 큐를 이용해 다음에 탐색 할 노드들을 저장하기 때문에 노드의 수가 많을 수록 필요없는 노드들까지 저장해야 하기 때문에 더 큰 저장공..