dfs

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

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

[BOJ/Python] 연산자 끼워 넣기 || DFS

백준 연산자 끼워 넣기 파이썬 14888 14888번: 연산자 끼워넣기첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱www.acmicpc.net더보기❍ 문제N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.예를 들어, 6개의 수로..

[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이라고 가정한다.예를 들..

[BOJ/Java] 16173_점프왕 쩰리 (Small) || DFS

16173번: 점프왕 쩰리 (Small)쩰리는 맨 왼쪽 위의 칸에서 출발해 (행, 열)로 나타낸 좌표계로, (1, 1) -> (2, 1) -> (3, 1) -> (3, 3)으로 이동해 게임에서 승리할 수 있다.www.acmicpc.net문제 설명더보기‘쩰리’는 점프하는 것을 좋아하는 젤리다. 단순히 점프하는 것에 지루함을 느낀 ‘쩰리’는 새로운 점프 게임을 해보고 싶어 한다. 새로운 점프 게임의 조건은 다음과 같다.‘쩰리’는 가로와 세로의 칸 수가 같은 정사각형의 구역 내부에서만 움직일 수 있다. ‘쩰리’가 정사각형 구역의 외부로 나가는 경우엔 바닥으로 떨어져 즉시 게임에서 패배하게 된다.‘쩰리’의 출발점은 항상 정사각형의 가장 왼쪽, 가장 위의 칸이다. 다른 출발점에서는 출발하지 않는다.‘쩰리’가 이동..

[BOJ/Python] 16173_점프왕 쩰리 (Small) || DFS

16173번: 점프왕 쩰리 (Small)쩰리는 맨 왼쪽 위의 칸에서 출발해 (행, 열)로 나타낸 좌표계로, (1, 1) -> (2, 1) -> (3, 1) -> (3, 3)으로 이동해 게임에서 승리할 수 있다.www.acmicpc.net문제 설명더보기‘쩰리’는 점프하는 것을 좋아하는 젤리다. 단순히 점프하는 것에 지루함을 느낀 ‘쩰리’는 새로운 점프 게임을 해보고 싶어 한다. 새로운 점프 게임의 조건은 다음과 같다.‘쩰리’는 가로와 세로의 칸 수가 같은 정사각형의 구역 내부에서만 움직일 수 있다. ‘쩰리’가 정사각형 구역의 외부로 나가는 경우엔 바닥으로 떨어져 즉시 게임에서 패배하게 된다.‘쩰리’의 출발점은 항상 정사각형의 가장 왼쪽, 가장 위의 칸이다. 다른 출발점에서는 출발하지 않는다.‘쩰리’가 이동..

[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): 루트 노드에서 인접한 노드부터 먼저 탐색하는 방법두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용 재귀적..