본문 바로가기

dfs8

[백준|파이썬] 21736: 헌내기는 친구가 필요해(DFS/BFS 풀이) (실버2) 문제 https://www.acmicpc.net/problem/21736 21736번: 헌내기는 친구가 필요해 2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 www.acmicpc.net 🐍파이썬 BFS import sys from collections import deque def bfs(x, y): global cnt queue = deque() queue.append((x, y)) sch[x][y] = 'X'#방문처리 while queue: x, y = queue.popleft() for i in range(4): nx = x + dx[i] ny = y + .. 2023. 4. 11.
[백준|파이썬] 2667: 단지번호붙이기(DFS/BFS 풀이) (실버1) 문제 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 🐍파이썬 DFS import sys sys.setrecursionlimit(10**6) n = int(sys.stdin.readline()) house = [] danzi = [] for _ in range(n): house.append(list(map(int, sys.stdin.readline().rstrip()))) dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] def.. 2023. 4. 11.
[백준|파이썬] 11724: 연결 요소의 개수 (실버2) 문제 https://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.net 🐍파이썬 import sys sys.setrecursionlimit(10**6)#최대 재귀깊이를 조절하여 런타임에러 해결 n, m = map(int, sys.stdin.readline().split()) graph = [[] for _ in range(n+1)] for _ in range(m): a, b = map(int, sys.. 2023. 4. 10.
[백준|파이썬] 6186: Best Grass (실버5) 문제 https://www.acmicpc.net/problem/6186 6186번: Best Grass Bessie is planning her day of munching tender spring grass and is gazing out upon the pasture which Farmer John has so lovingly partitioned into a grid with R (1 2023. 4. 10.
[백준|파이썬] 2644: 촌수계산 (실버2) 문제 https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 🐍파이썬 import sys n = int(sys.stdin.readline()) a, b = map(int, sys.stdin.readline().split()) m = int(sys.stdin.readline()) chon = [[] for _ in range(n+1)] for _ in range(1, m+1): c, d = map(int, sys.stdin.readl.. 2023. 4. 7.
[백준|파이썬] 2606: 바이러스 (실버3) 문제 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 🐍파이썬 import sys com = int(sys.stdin.readline()) ssang = int(sys.stdin.readline()) graph = [[] for _ in range(com + 1)] visited = [False] * (com + 1) global answer#dfs함수 내에서도 사용할 수 있도록 전역변수 선언 answer = 0 for _ in range(ssang.. 2023. 4. 5.
[백준|파이썬] 1260: DFS와 BFS (실버2) 문제 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 🐍파이썬 import sys N, M, V = map(int,sys.stdin.readline().split()) graph = [[] for _ in range(N + 1)] for i in range(M): a, b = map(int,sys.stdin.readline().split()) graph[a].append(b) graph[b].append(a.. 2023. 4. 5.
BFS / DFS 참고용 블로그 https://yabmoons.tistory.com/99 [ 순열과 조합 구현 ] - 재귀를 통한 구현(1 - 조합) (C++) 브루트포스 알고리즘에서 가장 많이 사용되는 방법이 순열과 조합등으로 모든 경우의 수를 모두 계산해본 뒤에 원하는결과 값을 찾는 방식이다. 이 글에서는, 순열과 조합을 STL을 사용하지 않 yabmoons.tistory.com https://blog.naver.com/kks227/220786417910 백트래킹(Backtracking) (수정 2019-10-09) 탐색 중에서는 가장 마지막으로 쓰는 글이 아닐까 싶습니다. 이제 DFS와 BFS도 익혔으니, 백트래킹(b... blog.naver.com https://foameraserblue.tistory.com/m/188 PS를 .. 2023. 4. 1.
반응형

티스토리툴바