BFS

[Goorm/Python] 통신망 분석 || 구름톤 챌린지 (union, bfs)

구름톤 챌린지 통신망 분석 파이썬 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io 더보기 ❏ 문제 설명 ❍ 문제 이 세상에는 수많은 컴퓨터들이 통신망을 통해 서로 연결되어 정보를 교류하고 있다. 오늘 플레이어는 이 거대한 통신망 중 한 구역을 조사하고자 한다. 플레이어가 조사할 구역에는 N개의 컴퓨터가 있고, M개의 통신 회선이 있다. 각 컴퓨터는 1번부터 N번까지 번호가 붙어 있고, 통신 회선은 서로 다른 두 컴퓨터를 양방향으로 연결하고 있다. 컴퓨터들은 연결 여부에 따라 여러 개의 컴포넌트로 나뉜다. 어떤 두 컴퓨터가 통신 회선만을 이용해서 연결되어 있다면 두 컴퓨터는 같은 컴포넌트에 속한다. 플레이어는 여러 개의 컴포넌트 중, 가장 밀..

[Goorm/Python] 발전기 (2) || 구름톤 챌린지 (DFS, BFS)

구름톤 챌린지 발전기 (2) 파이썬 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io 더보기 ❏ 문제 설명 ❍ 문제 구름 심시티를 하고 있는 플레이어는 한 변의 길이가 N인 정사각형 모양의 마을 M을 만들고 있다. 마을의 모든 칸에는 건물이 하나씩 있고, r번째 행, c번째 열에 해당하는 칸에는 정수 $M_{r, c}$가 적혀 있다. $M_{r, c}$는 해당 칸에 있는 건물의 유형의 번호를 의미한다. 건물의 유형이 동일하면서, 서로 상하좌우 인접한 칸에 위치한 건물끼리는 서로 전력을 공유할 수 있다. 전력을 공유할 수 있는 관계에 속한 건물의 개수가 K개 이상이면 이를 단지라고 한다. 플레이어는 발전기를 설치해 각 단지에 전력을 공급하고자 ..

[BOJ/Python] 경쟁적 전염 || BFS

백준 경쟁적 전염 파이썬 18405 18405번: 경쟁적 전염첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치www.acmicpc.net더보기❍ 문제NxN 크기의 시험관이 있다. 시험관은 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 바이러스가 존재할 수 있다. 모든 바이러스는 1번부터 K번까지의 바이러스 종류 중 하나에 속한다.시험관에 존재하는 모든 바이러스는 1초마다 상, 하, 좌, 우의 방향으로 증식해 나간다. 단, 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다. 또한 증식 과정에서 특정한 칸에 이미 어떠한 바이러스가..

[BOJ/Python] 특정 거리의 도시 찾기 || DFS, BFS

백준 18352 특정 거리의 도시 찾기 파이썬 18352번: 특정 거리의 도시 찾기첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개www.acmicpc.net더보기❍ 문제어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다.이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다.예를 들..

[Algorithm] DFS와 BFS || Depth-First & Breadth-First Search

❕ 인접 행렬 인접 행렬은(Adjacency Matrix)로 2차원 배열을 이용하여 그래프의 연결 관계를 표현하는 방식이다. INF = 999999999 graph = [ [0, 7, 5], [7, 0, INF], [5, INF, 0] ] print(graph) ❕ 인접 리스트(Adjacency List) 리스트로 그래프의 연결 관계 표현하는 방식 graph = [ [] for _ in range(3)] # 노드와 거리 graph[0].append((1, 7)) graph[0].append((2, 5)) graph[1].append((0, 7)) graph[2].append((0, 5)) print(graph) 메모리 : 인접 리스트 win 속도 : 인접 행렬 win 📌DFS (스택) DFS(Depth-..

[백준_python] 연결 요소의 개수 || 11724 (시간초과, 런타임에러(recursionerror)

www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주www.acmicpc.netDFS를 이용할까 했는데, BFS로 해주기 시작했다. 코드를 짜면서 바로 전에 풀었던 DFS, BFS 관련 문제들과 다를게 없는 것 같아서 다행이라고 생각하면서 풀어주었다. 똑같이 큐로 시작 정점을 저장해주며, 방문하지 않고 간선이 이어준 곳을 방문 체크를 해주며 큐에 값을 넣어주는 방식으로 함수를 작성을 해주었다. 그 후, 연결 요소를 세어주는 것이다보..

[백준_python] 바이러스 || 2606

www.acmicpc.net/problem/2606 2606번: 바이러스첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어www.acmicpc.net알고리즘 분류에 깊이 우선 탐색과 너비 우선 탐색이 있었는데, 나는 네트워크라는 단어를 읽자마자 DFS보다는 BFS로 구현을 하고 싶다는 생각을 하게 되었다.!1260을 풀면서 사용했던 bfs를 참고하면서 문제를 풀었는데, 무한 루프에 빠져서 한동안 헤어나올 수가 없었다.. 정말 똑같이 적었는데 왜 무한 루프에 빠졌는지 모르겠다. 다시 지우고 작성을 해서 빠져나오긴 했지만,, 아직도 이유를 모르겠다 ㅠ 다음에도 무한 루프..

[백준_python] DFS와 BFS || 1260

www.acmicpc.net/problem/1260 1260번: DFS와 BFS첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사www.acmicpc.net깊이 우선 탐색(DFS_Depth-First Search): 루트 노드를 모두 완벽하게 탐색을 한 후 다음 분기로 넘어가는 방법 모든 노드를 방문 하고자 하는 경우에 이용 순환 호출 혹은 스택 이용너비 우선 탐색(BFS_Breadth-First Search): 루트 노드에서 인접한 노드부터 먼저 탐색하는 방법두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용 재귀적..