백준/그래프탐색(dfs, bfs)

[백준 2178] (bfs)미로탐색 - python

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제풀이 미로탐색처럼 최소한의 경로로 이동해야하는 경우는 bfs를 이용해 문제를 푸는 것이 효율적 dx와 dy로 상하좌우를 탐색할 수 있도록 했고, visited를 이용해 지나온 경로는 탐색하지 않도록 했습니다 저는 bfs함수를 만들어 사용했는데 다른 사람 코드를 보니 함수를 짜지 않은게 더 눈에 잘 보였습니다 나의 풀이 # 최소를 찾는 문제 = bfs # 나의 풀이 dx = [0, 0, 1, -1] dy = [1, -1, 0,..

[백준 1352] (bfs)효율적인 해킹 - python

https://www.acmicpc.net/problem/1325 a인 단방향 그래프로 만들어줘야했다 그리고 해킹 당하는 컴퓨터를 한 번 한 번 확인해야하기 때문에 for문 안에서 dfs함수를 실행했다 (i가 계속 바뀌도록) 그 외엔 일반적인 DFS방법으로 풀이했다 그리고 result를 컴프리헨션 방식으로 value가 max_value값과 같은 값들만 list에 담아내도록 했다 Asterisk(*)를 사용하여 result에 있는 값을 풀어냈다 def dfs(computers, v, count, visited, point): visited[v] = 1 count[point] += 1 for i in computers[v]: if visited[i] == 0: # print(i, end=' ') dfs(co..

[백준 11725] (bfs)트리의 부모 찾기 - python

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 풀기 트리의 부모를 찾는 문제. 너비 탐색인 bfs를 사용하는 것이 맞다고 생각하고 풀이했다 parent[1]은 0만 아니게 초기화 해주면 된다 # 부모에 있는 자식들을 구하는 것은 bfs from collections import deque n = int(input()) graph = [[] for _ in range(n+1)] parent = [0] * (n+1) for _ in range(n-1): a, b = map(int, input().spli..

[백준 1206] DFS와 BFS - python

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제풀이 DFS와 BFS의 기본을 학습할 수 있는 문제였다 from collections import deque n, m, v = map(int, input().split()) graph = [[] for _ in range(n+1)] visited_dfs = [0] * (n+1) visited_bfs = [0] * (n+1) for _ in range(m):..

[백준 2606] (bfs)바이러스 - python

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net tip 그래프 탐색 문제에 앞서 bfs와 dfs를 언제 써야하는지에 대한 팁을 적어보겠습니다 bfs문제는 최단경로 탐색할떄 유용 (시작정점에서 주어진 정점까지 최단경로 찾기, 방문하지 않는 노드가 있어도 될때, 일부 경로만 탐색하는 경우, 미로찾기 문제) dfs는 전체중 일부경로만 정답인 경우 (성공적인 결론을 내릴 때까지 트리 탐색, 모든 경우를 방문해야하는 경우, 모든 경우를 구한 후 일부만선택(완..