BFS 썸네일형 리스트형 [백준] 7569번: 토마토 (파이썬) https://www.acmicpc.net/problem/7569저번 x,y축만 있던 토마토 문제에서 z축이 추가된 문제이다. #시작할 때 익은 토마토 위치 queue에 담기for i in range(h): for j in range(m): for k in range(n): if graph[i][j][k] == 1: queue.append((i,j,k))count = 0while queue: bfs() count += 1우선 시작할 때 익은 토마토의 위치를 queue에 담는다.이후 queue가 빌 때 까지 bfs를 반복한다. bfs의 코드를 살펴보겠다. def bfs(): temp = deque([]) while que.. 더보기 [백준] 1389번: 케빈 베이컨의 6단계 법칙 https://www.acmicpc.net/problem/1389 문제를 읽고 BFS라고 생각하고 문제 유형을 확인했는데, BFS로 푸는게 맞지만, '플로이드-워셜'이라는 알고리즘으로도 풀 수 있었다.플로이드-워셜 알고리즘이 뭔지 궁금해져서 이것으로 풀어보기로 했다.우선 플로이드-워셜 알고리즘은 노드가 적을 경우에 최단 거리를 구할 수 있는 알고리즘이다.시간 복잡도 무려 O(n^3)이기 때문에 문제 조건을 잘 확인하고 사용해야 할 것 같다. [플로이드 워셜 알고리즘]INF = int(1e9) #무한을 의미하는 값으로 10억을 설정N,M = map(int,input().split()) #N:유저 수, M:간선의 수graph = [ [INF]*(N+1) for _ in range(N+1)]#자기 자신으로 가.. 더보기 [백준] 11724번: 연결 요소의 개수 (파이썬) https://www.acmicpc.net/problem/11724 연결된 노드의 모임(?)이 몇 개인지 출력하는 문제였다.dfs로 풀었다.n,m = map(int,input().split())count = 0 #연결 요소의 개수def dfs(graph, v, visited): visited[v] = True #방문 처리 for i in graph[v]: if visited[i] == False: #방문하지 않았으면 재귀로 반복 dfs(graph, i, visited) graph = [[] for _ in range(n+1)]visited = [False] * (n+1)for i in range(m): #m번 반복 node, next_node = ma.. 더보기 이전 1 다음
