---

백준 1325 : 문제링크

• 문제유형 :

  • 그래프 탐색

  • BFS

• 설명

  • DFS, BFS를 수행할 때마다 방문하게 되는 노드의 개수를 계산
  • 가장 노드의 개수가 크게 되는 시작 정점을 출력

• 풀이

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

  from collections import deque n, m = map(int, input().split()) adj = [[] for _ in range(n + 1)] for _ in range(m): x, y = map(int, input().split()) adj[y].append(x) def bfs(v): q = deque([v]) visited = [False] * (n + 1) visited[v] = True count = 1 while q: v = q.popleft() for e in adj[v]: if not visited[e]: q.append(e) visited[e] = True count += 1 return count result = [] max_value = -1 for i in range(1, n + 1): c = bfs(i) if c > max_value: result = [i] max_value = c elif c == max_value: result.append(i) max_value = c for e in result: print(e, end = " ")

Comment and share

---

백준 1697 : 문제링크

• 문제유형 :

  • 그래프 탐색

  • BFS

• 설명

  • 특정 위치까지 이동하는 최단 시간을 계산
  • 이동 시간이 모두 1초로 동일, BFS를 이용하여 해결

• 풀이

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

  from collections import deque MAX = 100001 n, k = map(int, input().split()) array = [0] * MAX def bfs(): q = deque([n]) while q: now_pos = q.popleft() if now_pos == k: return array[now_post] for next_pos in (now_pos - 1, now_pos + 1, now_pos * 2): if 0 <= next_pos < MAX and not array[next_pos]: array[next_pos] = array[now_pos] + 1 q.append(next_pos) print(bfs())

Comment and share